Make bloom filter more effective. #193
Merged
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
Mix the hash's upper 16bits with the lower 16bits as a different hash for the bloom filter. This means bloomfilter hits don't necessarily align with occupied hashtable entries, possibly avoiding multiple hashtable probes to detect a hashtable miss.
Add and use tmask attribute for getting the hashtable index from a hash. Add and use bshift attribute for getting the bloomfilter bit index from a hash. This means we use the upper bits of the hash instead of bit-mixing and masking.
For a minimum of 1 and an empty file, the mask is empty, resulting in a bshift with as many bits as unsigned hash. In C shifting by all the bits is undefined.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
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.
Use the upper bits of the hash as the bloom filter index instead of using the lower bits used for the hashtable index.
This means we don't use the same index for the bloom filter and hashtable which ensures we don't always start probing the hashtable after bloom-filter hits at known non-empty entries. This is similar to using a "different hash" for each "k" of a bloom filter. The hashtable probes have a chance of immediately hitting an empty entry, significantly reducing the number of weaksum compares.
Also add tmask and bshift attributes to hashtable_t so we don't need to recalculate them for every probe.