Performance improvement in `SimHashIterator`
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 38/100
- Issue type
- Refactor
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- rust
- Domain
- performance
Research direction
Start by locating SimHashIterator, BitChunks, and SIM_BUCKET_SIZE in the repository, then read how buckets are currently formed. Investigate how BitChunks can skip zero ranges and how a bucket spanning multiple chunks would be handled. Done means reducing empty-range mixing without changing SimHash bucket results.
Written by the indexing model from the issue text.
Description
The current SimHashIterator works by finding the most significant active bit, and then calculating the number of SimHash buckets that will exist from that bit to the end of the filter. This means we are iterating (most_significant_bit / SIM_BUCKET_SIZE) + SIM_BUCKETS buckets.
The problem here is that in the higher order bits the sparsity is very high, meaning that there will potentially be many buckets where the values we're mixing into our SimHashes will just be zeros, and given any value XOR 0 is just that value this is wasted computation.
We could move to use the BitChunks iterators which batch up our chunks into a u64 and an index of that block of bits, skipping ranges full of zeros. This will introduce issues where if our SimHash bucket straddles multiple BitChunks, which can be solved by peeking the next chunk, making sure that the index is contiguous with our current chunk.
Right now SIM_BUCKET_SIZE is always 6 bits but if we allowed fully arbitrary SimHash bucket sizes this could get slightly gnarly because we'd need to be able to peek an arbitrary number of BitChunks ahead of the current position.
The following is a line chart plot of the proportion of empty bit_ranges mixed into the SimHashes using pseudorandomly generated geofilters with 0..100_000 items added to them.
The ratio reduces very sharply after a couple of inserts but remains relatively high since newly added items have some chance of landing in a very significant bucket which introduces a load of zero gaps before the next one bit.
- Dominant language
- Rust
- Stars
- 134
- Forks
- 24
- Avg merge
- 16h 27m
- Merged PRs (30d)
- 11
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from github/rust-gems
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
-
Difficulty 5/5 Over a week Newbie friendliness 30/100
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
All issues in github/rust-gems
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Eynzof/Hermes-CN-Desktop#610 ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
gitbutlerapp/gitbutler#15998 · 1 comment ·
-
bug triage:deciding
Difficulty 1/5 Under an hour Newbie friendliness 88/100
open-telemetry/otel-arrow#4132 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100