Implement branchless Bloom filters with various degree of "branchlessness"

FastFilter / fastfilter_cpp

Fast Approximate Membership Filters (C++)

Apache License 2.0

261 stars 24 forks source link

Open lemire opened 5 years ago

lemire commented 5 years ago

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

thomasmueller commented 5 years ago

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.