use slice-based visited list instead of map
@@ -90,7 +90,7 @@ func (h *hnsw) knnSearch(queryNodeID uint64, k int, ef int) ([]uint64, error) {
func (h *hnsw) searchLayerByVector(queryVector []float32,
entrypoints binarySearchTreeGeneric, ef int, level int,
allowList helpers.AllowList) (*binarySearchTreeGeneric, error) {
- visited := newVisitedList(entrypoints)
+ visited := h.newVisitedList(entrypoints)
candidates := &binarySearchTreeGeneric{}
results := &binarySearchTreeGeneric{}
distancer := h.distancerProvider.New(queryVector)
@@ -148,10 +148,15 @@ func (h *hnsw) searchLayerByVector(queryVector []float32,
return results, nil
}
-func newVisitedList(entrypoints binarySearchTreeGeneric) map[uint64]struct{} {
- visited := map[uint64]struct{}{}
+func (h *hnsw) newVisitedList(entrypoints binarySearchTreeGeneric) []bool {
+ h.RLock()
+ size := len(h.nodes) + defaultIndexGrowthDelta // add delta to be add some
+ // buffer if a visited list is created shortly before a growth operation
+ h.RUnlock()
+
+ visited := make([]bool, size)
for _, elem := range entrypoints.flattenInOrder() {
- visited[elem.index] = struct{}{}
+ visited[elem.index] = true
}
return visited
}
@@ -204,16 +209,17 @@ func (h *hnsw) currentWorstResultDistance(results *binarySearchTreeGeneric,
func (h *hnsw) extendCandidatesAndResultsFromNeighbors(candidates,
results *binarySearchTreeGeneric, connections []uint64,
- visited map[uint64]struct{}, distancer distancer.Distancer, ef int,
- level int, allowList helpers.AllowList, worstResultDistance float32) error {
+ visited []bool, distancer distancer.Distancer, ef int,
+ level int, allowList helpers.AllowList, worstResultDistance float32,
+) error {
for _, neighborID := range connections {
- if _, ok := visited[neighborID]; ok {
+ if ok := visited[neighborID]; ok {
// skip if we've already visited this neighbor
continue
}
// make sure we never visit this neighbor again
- visited[neighborID] = struct{}{}
+ visited[neighborID] = true
distance, ok, err := h.distanceToNode(distancer, neighborID)
if err != nil {
