New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Implement branchless Bloom filters with various degree of "branchlessness" #2

Open

lemire opened this issue Dec 6, 2018 · 1 comment

Member

lemire commented Dec 6, 2018

The design space between fully branchy and fully branchless Bloom filters is wide open. This should be explored.

Contributor

thomasmueller commented Dec 7, 2018

Yes. This is already partially implemented in the Bloom class:

Bloom8/12/16: there is a branch after each bit tested.
Branchless Bloom8/12/16: the first 3 bits are combined (that is, 87.5% of all the "Not Found" cases are combined in this one case). After that, there is a branch after each bit tested. The algorithm name is misleading, this isn't "branchless" (no branching), but just "branch less" (less branching).
Other cases are not implemented currently.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment