perf(core): simplify bloom bucket computation #40489
Closed
Conversation
This file contains 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
JoostK
added
area: performance
area: core
The injector system uses a bloom filter to determine if a token is possibly defined in the node injector tree, which is stored across multiple bloom buckets that each represent 32 bits of the full 256-bit wide bloom hash. This means that a computation is required to determine the exact bloom bucket which is responsible for storing any given 32-bit interval, which was previously computed using three bitmask operations and three branches to derive the bloom bucket offset. This commit exploits the observation that all bits beyond the low 5 bits of the bloom hash are an accurate representation for the bucket offset, if shifted right such that those bits become the least significant bits. This reduces the three bitmask operations and three branches with a single shift operation, while additionally offering a code size improvement.
…re handled correctly This commits adds additional expectations to verify that the bloom filter is able to correctly handle token IDs that exceed the size of the bloom filter (which is currently 256 bits).
JoostK
force-pushed
the
optimize-bloomhash
branch
from
6c5582c
to
017eee3
Compare
|
Sexy <3 |
mhevery
approved these changes
Jan 19, 2021
| // Each bloom bucket in `tData` represents `BLOOM_BUCKET_BITS` number of bits of `bloomHash`. | ||
| // Any bits in `bloomHash` beyond `BLOOM_BUCKET_BITS` indicate the bucket offset that the mask | ||
| // should be written to. | ||
| (tView.data as number[])[injectorIndex + (bloomHash >> BLOOM_BUCKET_BITS)] |= mask; |
There was a problem hiding this comment.
Ok, that is clear! I can't believe I did not think of that! 😊
pullapprove
bot
requested review from
AndrewKushnir,
IgorMinar,
jelbourn and
jessicajaniuk
JoostK
added
the
action: review
jessicajaniuk
approved these changes
Jan 19, 2021
IgorMinar
approved these changes
Jan 20, 2021
AndrewKushnir
added
action: presubmit
jessicajaniuk
pushed a commit
that referenced
this pull request
Jan 21, 2021
The injector system uses a bloom filter to determine if a token is possibly defined in the node injector tree, which is stored across multiple bloom buckets that each represent 32 bits of the full 256-bit wide bloom hash. This means that a computation is required to determine the exact bloom bucket which is responsible for storing any given 32-bit interval, which was previously computed using three bitmask operations and three branches to derive the bloom bucket offset. This commit exploits the observation that all bits beyond the low 5 bits of the bloom hash are an accurate representation for the bucket offset, if shifted right such that those bits become the least significant bits. This reduces the three bitmask operations and three branches with a single shift operation, while additionally offering a code size improvement. PR Close #40489
|
This issue has been automatically locked due to inactivity. Read more about our automatic conversation locking policy. This action has been performed automatically by a bot. |
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
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.
The injector system uses a bloom filter to determine if a token is
possibly defined in the node injector tree, which is stored across
multiple bloom buckets that each represent 32 bits of the full 256-bit
wide bloom hash. This means that a computation is required to determine
the exact bloom bucket which is responsible for storing any given 32-bit
interval, which was previously computed using three bitmask operations
and three branches to derive the bloom bucket offset.
This commit exploits the observation that all bits beyond the low 5 bits
of the bloom hash are an accurate representation for the bucket offset,
if shifted right such that those bits become the least significant bits.
This reduces the three bitmask operations and three branches with a
single shift operation, while additionally offering a code size
improvement.