goankur opened a new pull request, #16806: URL: https://github.com/apache/lucene/pull/16806
### Problem Before each search, `HnswGraphSearcher` clears its visited set. The graph builders use a `FixedBitSet` sized to the graph, so each clear writes `numNodes / 8` bytes. A builder searches once per level of each inserted node. A merge creates the graph with the merged vector count, so `maxNodeId()` returns the final size from the first insertion, and every insertion clears a set sized to the whole merged segment, even though a search visits only a few thousand nodes. In a profile of a merge into a segment of about 167M vectors (64 merge workers), `Arrays.fill` from these clears took 62% of the graph workers' time. With this change it took about 1%. ### Change `TrackingVisitedBitSet` (package-private in `util.hnsw`) wraps a `FixedBitSet`, records the bits a search sets, and clears only those. If a search sets more than `max(256, numWords / 16)` bits, it clears every word instead. Sets of fewer than 2M bits do not track and clear in full, because a full clear is cheaper there. `HnswGraphBuilder` and `HnswConcurrentMergeBuilder` use it. Query-time search does not change, and the graph is the same. ### Benchmark New JMH benchmark `HnswGraphInsertBenchmark`: time to insert one node into a graph created for `graphCapacity` nodes, as a merge creates it. Setup inserts 20K nodes, each operation inserts 2,000 more. 32-dim random unit vectors, dot product, M=16, beamWidth=100, 3 forks x 5 iterations, AMD EPYC 7R13 (8 cores), Corretto 25.0.4. Microseconds per insertion (+/- is the 99.9% confidence interval): | graphCapacity | main | this PR | main with SparseFixedBitSet | |---|---|---|---| | 100K | 189.9 +/- 4.8 | 184.7 +/- 8.3 | 192.0 +/- 5.8 | | 1M | 200.2 +/- 4.2 | 198.1 +/- 8.1 | 194.5 +/- 8.1 | | 10M | 285.1 +/- 12.4 | 205.1 +/- 4.2 | 199.2 +/- 4.6 | | 100M | 1128.9 +/- 76.5 | 216.6 +/- 8.9 | 269.9 +/- 5.2 | On main, an insertion gets 5.6x slower from 1M to 100M. With this PR it stays flat. A first version that tracked at every size was about 5% slower than main at 100K and 1M, hence the 2M threshold. To run: `./gradlew :lucene:benchmark-jmh:assemble`, then `java --module-path lucene/benchmark-jmh/build/benchmarks --module org.apache.lucene.benchmark.jmh HnswGraphInsertBenchmark -f 3`. ### Alternatives considered - `SparseFixedBitSet` (last column, a local change to main, not in this PR): `clear()` writes 64x less than `FixedBitSet`, but the cost still grows with capacity, and after each clear the first bit in each block allocates a new `long[]`. - Tracking inside `FixedBitSet`: adds a field and a branch to `set()` and `getAndSet()` for every user of a widely used final class. - Tracking in `HnswGraphSearcher` with a bulk clear on `FixedBitSet`: every path that sets a visited bit (base, merge, filtered and seeded searchers) must record it, and a missed one leaves stale bits. The wrapper keeps this in one place. - An epoch array (`int[]` or `short[]` marks, as in hnswlib): free clears, but 16 to 32x the memory of a bit set per merge worker. ### Tests - `TestTrackingVisitedBitSet.testSameAsFixedBitSet`: random sets, clears and growth against a `FixedBitSet`, with tracking on from the start, on after growth, or off. - `TestTrackingVisitedBitSet.testClearAtTheLimit`: exactly 255, 256 or 257 distinct bits, where the clear switches from per-bit to all words. - `HnswGraphTestCase.testTrackingVisitedSetBuildsSameGraph` (float, byte, float16): a graph built with the tracking set equals one built with a `FixedBitSet`. Each test runs in under 0.4 s. Removing either clear path from `TrackingVisitedBitSet` makes both the bit set tests and the graph test fail. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
