4 ms·
> so that you essentially only pay the cost of a single random read for the entire lookup Why would you ever pay more than that for a bloom filter lookup? I me
by bjornsing 1y ago
> so that you essentially only pay the cost of a single random read for the entire lookup
Why would you ever pay more than that for a bloom filter lookup? I mean, I don’t see how that has anything to do with parallelism in memory subsystems. But I may be missing something.
- Tuna-Fish 1y agoA bloom filter needs to multiple loads from different memory locations for each single lookup. (7, in the example 1.2GB filter.) But unlike, say, with a tree, it knows all the addresses after computing the hashes, without having to wait for results from the previous loads. So it can start all of them in parallel.
- bjornsing 1y agoYeah, sorry. I was thinking of a single hash function bloom filter, which is of course the exception. My bad.