You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "mikemccand (via GitHub)" <gi...@apache.org> on 2025/06/09 10:31:54 UTC

[I] Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets? [lucene]

mikemccand opened a new issue, #14763:
URL: https://github.com/apache/lucene/issues/14763

   ### Description
   
   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]
   
   ```


-- 
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: issues-unsubscribe@lucene.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [I] Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets? [lucene]

Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir commented on issue #14763:
URL: https://github.com/apache/lucene/issues/14763#issuecomment-2955413359

   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.


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [I] Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets? [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14763:
URL: https://github.com/apache/lucene/issues/14763#issuecomment-2956919778

   > "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.


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [I] Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets? [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14763:
URL: https://github.com/apache/lucene/issues/14763#issuecomment-2956754534

   @mikemccand https://github.com/apache/lucene/pull/14765


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [I] Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets? [lucene]

Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir commented on issue #14763:
URL: https://github.com/apache/lucene/issues/14763#issuecomment-2955397732

   > 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


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [I] Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets? [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14763:
URL: https://github.com/apache/lucene/issues/14763#issuecomment-2956287088

   ```
   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.


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [I] Are we spending too much CPU in HNSW `ramBytesUsed`, and clearing bitsets? [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on issue #14763:
URL: https://github.com/apache/lucene/issues/14763#issuecomment-2956263657

   > 13.12%        581719        org.apache.lucene.util.hnsw.NeighborArray#ramBytesUsed() [Inlined code]
   
   This is new, I know the cause. I will fix it.


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org