Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets?

[mikemccand]

Peeking at the last nightly benchmark data point, I see the top CPU hotspots during indexing.

That 2nd one (13.12% in ramBytesUsed) is concerning ... I know we need to account properly for RAM so IW can flush when RAM exceeds its allowance ... but maybe we can optimize how we do that for HNSW?

8.63% spent clearing bitsets for HNSW searching is also scary -- that likely impacts search performance too (since building an HNSW graph is done by doing a search for each inserted vector)?

Also what exactly is reduceLanesTemplate? I find this name very non-intuitive :) Is it essentially a cast (like long -> int) for a vector?

Profiler for cpu:
WARNING: Using incubator modules: jdk.incubator.vector
PROFILE SUMMARY from 4433882 events (total: 4M)
  tests.profile.mode=cpu
  tests.profile.count=50
  tests.profile.stacksize=4
  tests.profile.linenumbers=false
PERCENT       CPU SAMPLES   STACK
23.57%        1M            jdk.incubator.vector.FloatVector#reduceLanesTemplate() [Inlined code]
                              at jdk.incubator.vector.Float256Vector#reduceLanes() [Inlined code]
                              at org.apache.lucene.internal.vectorization.PanamaVectorUtilSupport#dotProductBody() [JIT compiled code]
                              at org.apache.lucene.internal.vectorization.PanamaVectorUtilSupport#dotProduct() [Inlined code]
13.12%        581719        org.apache.lucene.util.hnsw.NeighborArray#ramBytesUsed() [Inlined code]
                              at org.apache.lucene.util.hnsw.OnHeapHnswGraph#updateGraphRamBytesUsed() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.OnHeapHnswGraph#addNode() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNodeInternal() [JIT compiled code]
9.51%         421729        org.apache.lucene.index.FloatVectorValues$1#vectorValue() [Inlined code]
                              at org.apache.lucene.codecs.hnsw.DefaultFlatVectorScorer$FloatScoringSupplier$1#score() [Inlined code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#searchLevel() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNodeInternal() [JIT compiled code]
8.63%         382600        java.util.Arrays#fill() [Inlined code]
                              at org.apache.lucene.util.FixedBitSet#clear() [Inlined code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#prepareScratchState() [Inlined code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#searchLevel() [JIT compiled code]
4.55%         201882        org.apache.lucene.util.FixedBitSet#getAndSet() [Inlined code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#searchLevel() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNodeInternal() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNode() [Inlined code]
3.12%         138341        org.apache.lucene.util.RamUsageEstimator#sizeOf() [Inlined code]
                              at org.apache.lucene.internal.hppc.MaxSizedIntArrayList#ramBytesUsed() [Inlined code]
                              at org.apache.lucene.util.hnsw.NeighborArray#ramBytesUsed() [Inlined code]
                              at org.apache.lucene.util.hnsw.OnHeapHnswGraph#updateGraphRamBytesUsed() [JIT compiled code]
2.60%         115254        org.apache.lucene.util.hnsw.HnswConcurrentMergeBuilder$MergeSearcher#graphSeek() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#searchLevel() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNodeInternal() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNode() [Inlined code]
2.42%         107338        org.apache.lucene.internal.hppc.MaxSizedIntArrayList#ramBytesUsed() [Inlined code]
                              at org.apache.lucene.util.hnsw.NeighborArray#ramBytesUsed() [Inlined code]
                              at org.apache.lucene.util.hnsw.OnHeapHnswGraph#updateGraphRamBytesUsed() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.OnHeapHnswGraph#addNode() [JIT compiled code]
2.36%         104842        org.apache.lucene.internal.vectorization.PanamaVectorUtilSupport#dotProductBody() [JIT compiled code]
                              at org.apache.lucene.internal.vectorization.PanamaVectorUtilSupport#dotProduct() [Inlined code]
                              at org.apache.lucene.util.VectorUtil#dotProduct() [Inlined code]
                              at org.apache.lucene.index.VectorSimilarityFunction$2#compare() [Inlined code]
2.36%         104836        org.apache.lucene.util.hnsw.OnHeapHnswGraph#updateGraphRamBytesUsed() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.OnHeapHnswGraph#addNode() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNodeInternal() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNode() [Inlined code]
2.21%         97814         org.apache.lucene.util.hnsw.OnHeapHnswGraph#getNeighbors() [Inlined code]
                              at org.apache.lucene.util.hnsw.HnswConcurrentMergeBuilder$MergeSearcher#graphSeek() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#searchLevel() [JIT compiled code]
                              at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNodeInternal() [JIT compiled code]
1.55%         68929         java.util.concurrent.locks.AbstractQueuedSynchronizer#apparentlyFirstQueuedIsExclusive() [Inlined code]
                              at java.util.concurrent.locks.ReentrantReadWriteLock$NonfairSync#readerShouldBlock() [Inlined code]
                              at java.util.concurrent.locks.ReentrantReadWriteLock$Sync#tryAcquireShared() [Inlined code]
                              at java.util.concurrent.locks.AbstractQueuedSynchronizer#acquireShared() [Inlined code]

[rmuir]

Also what exactly is reduceLanesTemplate? I find this name very non-intuitive :) Is it essentially a cast (like long -> int) for a vector?

simd-vectorized code

[rmuir]

the reduction just means vector -> scalar.

We just call reduceLanes() a single time here: https://github.com/apache/lucene/blob/main/lucene/core/src/java24/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java#L157

You can see a lot of effort is made to not call it unnecessary number of times.

[benwtrent]

13.12% 581719 org.apache.lucene.util.hnsw.NeighborArray#ramBytesUsed() [Inlined code]

This is new, I know the cause. I will fix it.

[benwtrent]

8.63%         382600        java.util.Arrays#fill() [Inlined code]
                              at org.apache.lucene.util.FixedBitSet#clear() [Inlined code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#prepareScratchState() [Inlined code]
                              at org.apache.lucene.util.hnsw.HnswGraphSearcher#searchLevel() [JIT compiled code]

The main caller for prepareScratchState is during graph building. However, we will clear the bit set between finding the best entry point and searching the bottom layer. So, it SHOULD only be called twice per segment, no matter then graph size.

The question that leaves two questions:

• "Do we need to clear the bitset between finding the entry point and search layer 0 at search time" and honestly, since we only do it twice, I think keeping it in is fine. My concern would be if we actually have to span our further due to result filtering, we might actually miss nearest neighbors that were explored on previous levels.

• "Do we need to clear the bitset during index building". This one is trickier. I think there is some optimization we can do here as by definition, the entrypoint we find at a layer is the nearest vector and all previously explored vectors at previous layers are further away.

[benwtrent]

@mikemccand #14765

[benwtrent]

"Do we need to clear the bitset during index building"...

I see a quick win here. We can likely do only two bitset clears for the majority of vectors instead of one bit-set clear per level.

This should be possible by overloading findBestEntryPoint to accept a starting & ending level. Then we can get to the best entry point for the top-most target level for node insertion. This would take only one bitset clear.

Then we clear only for the the target level(s).

This will only be beneficial on large graphs.