Something like this? 64-bit hash, 9 bits to address all the bits in a 64-byte cache line, so 7 hash functions addressing the bits in a cache line can be extracted from a 64-bit hash?
NB: You're trading non-negligible space efficiency here, which gets worse as you lower the false positive rate. Partitioning means uneven occupancy rates across partitions, and either you accept low occupancy (increased filter size overall) or you're pretty much guaranteed to have hot blocks (increased false positive rate for specific partitions).
You are describing "blocked" bloom filters here (i.e., the k hash functions are evaluated in a single block which is initially chosen by the hash). "Partitioned" bloom filters (i.e., each hash function is evaluated in a separate partition) don't have the imbalance problem you describe.
I hadn’t seen that one hash paper before. This is a really cool optimization over Miztenmacher. Do you have benchmark numbers with different input sizes you can share?
I’ll have to read the paper and code more, but it seems like this would be amenable to supporting filter merges as well (as long as the new size doesn’t exceed the filters’ capacity).
While much cheaper than going to disk, computing k independent hashes per key is still a bit expensive for very high performance systems.
Depends how big the bloom filter is. Most hashes are big and their bits are independent.
You don't actually have to do this - you can stick with a power of 2 sized table and just gently mix the hash value to get each additional bit index.
(source - I wrote MurmurHash/SMHasher and have used the above in my own bloom filters and cuckoo hash tables)
Something like this? 64-bit hash, 9 bits to address all the bits in a 64-byte cache line, so 7 hash functions addressing the bits in a cache line can be extracted from a 64-bit hash?
yeah. You also don't need complete independence. You can use partially overlapping bits to get semi-independent hashes.
NB: You're trading non-negligible space efficiency here, which gets worse as you lower the false positive rate. Partitioning means uneven occupancy rates across partitions, and either you accept low occupancy (increased filter size overall) or you're pretty much guaranteed to have hot blocks (increased false positive rate for specific partitions).
You are describing "blocked" bloom filters here (i.e., the k hash functions are evaluated in a single block which is initially chosen by the hash). "Partitioned" bloom filters (i.e., each hash function is evaluated in a separate partition) don't have the imbalance problem you describe.
I hadn’t seen that one hash paper before. This is a really cool optimization over Miztenmacher. Do you have benchmark numbers with different input sizes you can share?
I’ll have to read the paper and code more, but it seems like this would be amenable to supporting filter merges as well (as long as the new size doesn’t exceed the filters’ capacity).
Great post!