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