Word-Aligned Bloom Filters • Hacker News Board

Re: Word-Aligned Bloom Filters

#31

Post by devwastaken » Sun, Oct 03, 2021, 5:38 PM UTC

blondin wrote: post #30

Rendello wrote: post #8

I find these optimizations fascinating. Anyone familiar with Lemire likely knows about this, but I listened to a podcast episode[1] with him a few days ago and learned about `simdjson`, the tool he authored that parses JSON at 25x the speed of the standard C++ library.[2][3] It's worth looking at if you're into this sort of thing. 1. https://corecursive.com/frontiers-of-performance-with-daniel... 2. https://www.youtu…

yep, great fan of his work here. thanks for sharing that podcast. that kind of optimization requires you to know your machine architecture quite well. SIMD optimizations aren't new. but it's always amazing to see these performance increases on a single machine! our CPUs and GPUs are quite amazing. we have decided, as a field, that we can get enough virtual CPUs, GPUs, or RAM on-demand. and that we shouldn't concern o…

Simd convinced me to take college courses in algorithms and to learn higher maths. Things like image decoding rely heavily on doing transformations, and you just have to know the math behind it to an exact point to be able to effectively turn scalar math to vector effectively.

Ontop of this you have to identify what can and cannot be vectorized and how it can be integrated.

Working in simd isn't too hard In itself once you get down to the assembly and toss out all the extra stuff compilers add. If you look at how ffmpeg does it, they just assemble the hand written assembly as the C function itself. Arm64 is very nice to do this in because it has an elegant way in defining vectors and instructions for them.

Re: Word-Aligned Bloom Filters

#32

Post by bqmjjx0kac » Sun, Oct 03, 2021, 6:01 PM UTC

bugzz wrote: post #26

marginalia_nu wrote: post #3

This seems a bit like a solution in search of a use case. There are simpler solutions for this particular usecase. Let's take an extreme case: You have 250 million paying customers you want to cache access to. Yeah, that's way more than you probably have, but the point is that you can keep 250 million integers in memory no problem what so ever. It fits in a gigabyte. There are raspberry pis with eight times that amou…

The main use case I've always seen is to use bloom filters on the client side to reduce traffic to the server looking things up. As you said, you could cache 250 million integers in a gigabyte - but you don't want to bloat your client side implementation by a gigabyte for every bloom filter you use. Also, many times the items are a lot larger than an integer. For example, storing a list of malicious URLs, a common us…

I'm so confused by this use case (the traffic-saving one, not the malicious URL classifier). Why not store the "is-paying-customer" bit in a cookie?

What are we using as the user identifier? Where does it come from, if not a cookie?

Also, this client-side bloom filter kind of leaks your user database, supposing it's keyed on email addresses and your adversary has a gigantic list of email addresses, or is patient enough to enumerate them.

Re: Word-Aligned Bloom Filters

#33

Post by a11r » Sun, Oct 03, 2021, 6:03 PM UTC

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

The original paper by Burton H. Bloom is only 5 pages and very readable. https://dl.acm.org/doi/10.1145/362686.362692

Re: Word-Aligned Bloom Filters

#34

Post by colmmacc » Sun, Oct 03, 2021, 6:05 PM UTC

I'm really suspicious about whether this would really work out in most workloads.

On modern architectures, it's the random memory reference that kills performance. Predictive pre-fetching in the pipeline has a impossible time figuring out what to get ready in the caches with random lookups; it's not like a linear sweep. This style of bloom-filter needs to be quite large, and it pulls only one cache-line in per key lookup, both of these properties make any opportunistic (non-prefetched) caching less effective.

I wonder if real-world benchmarks would prefer a more memory dense lookup that pulls in multiple lines; just because it keeps the cache-lines hotter and less likely to be evicted. On the other hand, writes to this kind of bloom filter invalidate only one cache-line, so that's good. So I'd guess it's all very very workload dependent. Ultimately it depends on cache pressure and how over-subscribed the cache is and the ratio of writes to reads, and the distribution of keys; an implementation might also fare very differently on a system like Graviton2 (which has huge caches) than on a small Xeon.

Re: Word-Aligned Bloom Filters

#35

Post by willvarfar » Sun, Oct 03, 2021, 6:09 PM UTC

Excellent thought provoking article, but all the times I’ve brought in a dumb cache or bloom filter it is to save calling a micro service or hitting a DB or something so fantastically expensive (in computer time) that even a staggeringly inefficient bloom filter or just keeping lists of recently-seen values etc is a massive win. So there’s no big pressing need to microoptimise the bloom filter or whatever, and all the real profile guided optimizations point at other low hanging fruit.

Re: Word-Aligned Bloom Filters

#36

Post by 6510 » Sun, Oct 03, 2021, 6:23 PM UTC

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

let me butcher the concept for you :)

say though nummerology you reduce the character values of a name to a number 0-10. Lots of names will reduce to the same number. We take 11 bits and for "jim" we set the first bit. We have only one name in our data set so all other bits are 0. Now if someone types "joe" in the search box and it reduces to 2 we look at the second bit, see it is a zero and know 100% *for sure* that this name is not in the data set. If "jack" reduces to 1 and we look him up we see 1 is set so this name *might be* there.

Re: Word-Aligned Bloom Filters

#37

Post by Gh0stRAT » Sun, Oct 03, 2021, 6:23 PM UTC

marginalia_nu wrote: post #29

Gh0stRAT wrote: post #22

Earlier quoted context omitted.

Imagine you're making a web browser plugin that blocks ads, or malicious sites. Let's assume the blocklist is a hundred megs (easily fits in ram) and your millions of users need to get the latest data at least hourly in order to keep up with the latest URLs that you want to block. Rather than distributing the entire blocklist to your userbase, you can instead send a bloom filter + an allowlist of the small handful of…

Couldn't you just send deltas if that is the case? Surely the hourly updates wouldn't be hundreds of megabytes? I just tested extracting 5 million URLs from my web crawler and it was like 150 Mb in plain text. That's ignoring how easy it is to create compression schemes for URLs that slash their memory footprint by something like 80%.

Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwidth as well. They might be on a very slow/limited data plan) Maybe you don't care about bandwidth and would prefer to avoid the complexity and maintenance overhead of adding a bloom filter.

As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently.

As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it.

Re: Word-Aligned Bloom Filters

#38

Post by dr_kiszonka » Sun, Oct 03, 2021, 6:34 PM UTC

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

I will take an imposter over a grandiose narcissist any day! (But then I am an imposter too.)

Re: Word-Aligned Bloom Filters

#39

Post by flavius29663 » Sun, Oct 03, 2021, 6:37 PM UTC

willvarfar wrote: post #35

Excellent thought provoking article, but all the times I’ve brought in a dumb cache or bloom filter it is to save calling a micro service or hitting a DB or something so fantastically expensive (in computer time) that even a staggeringly inefficient bloom filter or just keeping lists of recently-seen values etc is a massive win. So there’s no big pressing need to microoptimise the bloom filter or whatever, and all th…

Same, I was thinking about implementing a bloom filter myself, but when I put in the hit ratio and the frequencies, a simple LRU cache was going to be close enough. It's hard to justify the complexity sometimes, which is a pitty cause they are so cool.

Re: Word-Aligned Bloom Filters

#40

Post by DougBTX » Sun, Oct 03, 2021, 6:39 PM UTC

rattlesnakedave wrote: post #24

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much. Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken. So what you can do is make a bloom filter, which is basically just an array of bits of n length. L…

Usernames is a nice example. Just as a demo, we could make things simpler:

Look at all the usernames in the input, keep track of all the letters you’ve seen. When you get a new name, if you’ve seen all the letters before, you might have seen the name before. If there’s a new letter, it must be a new name.

Obviously that isn’t a great hash function, some letters are more common than others, so real Bloom filters use better ones, but it works basically the same way.