remove allocations from lookups #793
Merged
+128
−1
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
mkeskells
commented
Aug 17, 2025
| // common prefix is the same ,then increase the depth | ||
| depth += branchNodePrefixLength; | ||
| } | ||
| //TODO - expose an API that avoids this double dipping |
Contributor
Author
There was a problem hiding this comment.
exposing this additional API (and associated initial implementation) further reduces CPU by 13% on my tests, but thought it would be better to discuss in a separate PR, but happy to include if preferred
lemire
reviewed
Aug 17, 2025
roaringbitmap/src/main/java/org/roaringbitmap/longlong/LongUtils.java
Outdated
Show resolved
Hide resolved
Member
|
This looks fine to me, please consider my suggestion (optional). |
f828ea2 to
6aa9546
Compare
…ls.java Co-authored-by: Daniel Lemire <daniel@lemire.me>
Contributor
Author
taken |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
SUMMARY
Remove the allocations in the lookup path (other than the
ContainerAndIndex, which would be removed by removing theHighLowContainerand is subject of a separate discussion)These were byte array allocations to represent a key path, which is specified as a long to the API anyway
In my tests (not checked in this PR) this reduces the CPU usage on thread by 23% (and GC overhead on other threads
Automated Checks
./gradlew testand made sure that my PR does not break any unit test.Discussion
private LeafNode findByKey(Node node, long key)looking at the profiler, but didn't want to change the API too much in this simple PR, so added some commentsfindByKey. There doesn't seem to be a 'standard' for this. - some usages are in the high 48 bits, and some are in the low 48 bits (e.g.LeafNode.getKey). Happy to change if there is a direction