diskann: search() allocates an O(n) VisitedSet per query — the pre-allocated reusable set is never used

[ohdearquant]

Summary

DiskAnnIndex::search() allocates a fresh VisitedSet on every query, and the set it pre-allocates at build time is unreachable dead weight. At 1M vectors this is roughly 8 MB of zero-filled heap allocation per query, which caps QPS on native and is even more expensive under wasm's dlmalloc (relevant to the #675 / #676 wasm path, where memory churn never returns to the OS).

Verified at main c55e9e89.

Details

• build() pre-allocates a reusable set: self.visited = Some(VisitedSet::new(n)) (index.rs:157-158), with the comment "Reusable visited set for search (avoids per-query allocation)" (index.rs:73-74).
• But search(&self, ...) (index.rs:169) takes a shared reference, so it can never hand out &mut self.visited. It calls the public graph.greedy_search (index.rs:183), which is documented as "allocates its own VisitedSet" and does exactly that: let mut visited = VisitedSet::new(vectors.len()) (graph.rs:207-216).
• VisitedSet::new(n) allocates and zero-fills two vectors: bits: vec![0u64; (n+63)/64] and gens: vec![0u64; n] (distance.rs:191-196). The gens vector alone is 8n bytes, so every query pays an O(n) allocation plus an O(n) zero-fill before the first hop. The generation-counter design exists precisely to amortize this to O(1) per query via clear(), but the reuse path is never taken.

Measurable impact

• Per-query heap allocation: ~8.1 MB at n = 1,000,000 (should be 0 after the first query).
• The O(n) zero-fill makes per-query cost grow linearly with index size even when the beam search itself touches a few hundred nodes. On a sublinear-ANN index this is the dominant fixed cost at scale.
• Under wasm32 this also grows the linear memory high-water mark by one full set per in-flight query.

Suggested fix

Any of:

1. Wrap the reusable set in interior mutability (RefCell<VisitedSet> for the single-threaded/wasm case, or a small pool / thread_local! for parallel native), and route search() through greedy_search_fast(&mut visited).
2. Add a search_with(&self, query, k, visited: &mut VisitedSet) entry point and keep search() as the allocating convenience wrapper, so hot callers (and the napi/wasm bindings) can hold one set per handle.

Option 2 is fully non-breaking. We run the same generation-counter design with a reused set in khive's vamana crate (ohdearquant/khive, crates/khive-vamana) including a wrap-safe generation bump, and are happy to send a PR if you want this.

Acceptance

• Steady-state search() performs zero heap allocation attributable to the visited set (verifiable with a counting allocator in a test).
• p50/p99 search latency at n = 1M improves or is unchanged; recall is bit-identical (the set semantics do not change).