What are they running this code on?
I doubt their hardware is any faster shuffling bits in a uint32 than a uint64, and using uint64 should have a decent benefit to the false positive rate...
Two Bits Are Better Than One: making bloom filters 2x more accurate
11–20 of 36 posts
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#12Isn't this idea similar to the classic "power of 2 random choices"
https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2...
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#13It's true that a fixed size bloom filter gives better compiler performance...
But another approach is to use C++ templating so you can have say 10 different 'fixed size' implementations with no additional overhead, and at runtime select the most suitable size.
For the couple of kilobytes of extra code size, this optimisation has to be worth it assuming table size is variable and there are some stats to give cardinality estimates...
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#14Hmm, Bloom filters seem important. I'm wondering why my CS education never even touched on them and it's tbh triggering my imposter syndrome.
they're common in databases and performance instrumentation of various kinds (as are other forms of data structure "sketch" like count sketches) but not as common outside those realms.
i've gotten interview questions best solved with them a few times; a Microsoft version involved spell-checking in extremely limited memory, and the interviewer told me that they'd actually been used for that back in the PDP era.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#15What are they running this code on? I doubt their hardware is any faster shuffling bits in a uint32 than a uint64, and using uint64 should have a decent benefit to the false positive rate...
That struck me as an odd choice, too. On average there's no difference in false positives, but the smaller the blocks, the more likely they'll be saturated. Since there are 6 leftover bits in the hash anyway, there's no cost to increase the two 5-bit values to 6 bits and the block size to 64. You'll have a lot fewer hot blocks that way.
With blocks this small there's also no reason not to optimize the number of hash functions (albeit this brings back the specter of saturation). There are no cache misses to worry about; all positions can be checked with a single mask.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#16Clever. My first impression was that surely this saturates the filter too fast as we're setting more bits at once but looks like the maths checks out. It's one of those non-intuitive things that I am glad I learned today.
It works because the original filter has suboptimal settings. An optimal filter of that size and number of items would set 5 bits per item and have about a quarter of the false positive rate. The 2 bits per item in the blocked filter is still suboptimal, but it's also saving them from saturating a bunch of 32-bit blocks, at the cost of a much higher overall false positive rate.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#17Hmm, Bloom filters seem important. I'm wondering why my CS education never even touched on them and it's tbh triggering my imposter syndrome.
Unpopular opinion: They're one of these things that are popular because of their cool name. For most purposes, they're not a good fit
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#18This article is a little confusing. I think this is a roundabout way to invent the blocked bloom filter with k=2 bits inserted per element. It seems like the authors wanted to use a single hash for performance (?). Maybe they correctly determined that naive Bloom filters have poor cache locality and reinvented block bloom filters from there. Overall, I think block bloom filters should be the default most people reach…
> Overall, I think block bloom filters should be the default most people reach for.
I think this depends on how big your filters are. Most people think of Bloom filters as having to have hundreds of thousands of elements, but I frequently find them useful all the way down to 32 bits (!). (E.g., there are papers showing chained hash tables where each bucket has a co-sited tiny Bloom filter to check if it's worth probing the chain.) In the “no man's land” in-between with a couple ten thousand buckets, the blocking seems to be mostly negative; it only makes sense as long as you actually keep missing the cache.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#19Nice.
The ligature ← for And a nitpick; Finding a match in a bloom filter isn’t a false positive, it is inconclusive.
Since bloom filter are only designed to give negatives, never positives, the concept of a false positive is nonsensical. Yeah, I get what you mean, but language is important.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#20Nice. The ligature ← for And a nitpick; Finding a match in a bloom filter isn’t a false positive, it is inconclusive. Since bloom filter are only designed to give negatives, never positives, the concept of a false positive is nonsensical. Yeah, I get what you mean, but language is important.
Calling it a false positive is entirely in line with the historical use.
Back in the 1980s or earlier it was called a "false drop".
Knuth, for example, talks about it in "The Art of Computer programming", v3, section 6.5, "Retrieval on Secondary Keys", using cookie ingredients. (See https://archive.org/details/fileorganisation0000thar/mode/2u... for Tharp using the same example.)
Bloom filters are a type of superimposed coding.