4 ms·
I'm not really convinced by this article. His complaint is that bloom filters are too slow for his purpose, and the cause is the large memory requirements and r
by the_gorilla 2y ago
I'm not really convinced by this article. His complaint is that bloom filters are too slow for his purpose, and the cause is the large memory requirements and random memory accesses causing constant cache misses. So, he has 40 million lines and 600 MB of data and it takes 12 seconds for his bloom filter to work. I'd have to dig into it a lot more but my instincts are telling me this is user error because these numbers don't really make sense even on older hardware.
- bborud 2y agoDid you try to repeat the experiment?
- limit499karma 2y ago> "64 GiB of memory" & "1-error-per-10k" entries. That's the size of the BF that gives that error rate (per his calcs - didn't check). So that definitely busts the cache.
- the_gorilla 2y agoI didn't say it would fit in the cache.
- limit499karma 2y agoCorrect. You mentioned your instincts.
- majke 2y agoRandom memory access is really slow (compared to CPU speed). Therefore it's strictly faster to do exactly one random memory fetch (hashtable) than many (bloom filter).