4 ms·

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 performa

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.

csense 5y ago
> I'm really suspicious about whether this would really work out in most workloads. What kinds of workloads are those? Workloads where the Bloom filter itself fits in cache? > On modern architectures, it's the random memory reference that kills performance Yeah, the whole point of the article is that moving from a traditional Bloom filter to a block Bloom filter is to improve from N random accesses per query/update to 1 random access per query/update. > Ultimately it depends on cache pressure and how over-subscribed the cache is The unspoken assumption in the article is that the Bloom filter is much bigger than cache. If your Bloom filter fits in cache, or you're writing for something with superfast RAM like a GPU or a Xeon Phi or something, block Bloom filters are wasteful for you. But I'm pretty sure the common case is writing normal applications running on reasonable general-purpose CPU's with Bloom filter sizes in the hundreds of MB or more. [1] [2] [1] If the Bloom filter's smaller than hundreds of MB, your data's probably small enough that you decide Bloom filters aren't worth the hassle and just use a HashMap or language equivalent. [2] If you're using a Bloom filter to do some sort of network stuff, like figuring out the set difference of two peers' objects in some p2p protocol, you probably don't care too much about block Bloom filters, because in this application memory access time is probably going to be dominated by network latency.
- becurious 5y ago
  If you had many lookups to do, then an approach with a coroutine that issues a prefetch instruction then yields to other lookups while the data is fetched in memory might be effective. Similar to this: http://www.vldb.org/pvldb/vol11/p1702-jonathan.pdf http://www.vldb.org/pvldb/vol11/p1702-jonathan.pdf
- a1369209993 5y ago
  > to improve from N random accesses per query/update to 1 random access per query/update. I think their concern is that N (nondependent) random accesses can happen in parallel not much more slowly than 1 random access (assuming good speculation and sufficient memory bandwidth).
  - HelloNurse 5y ago
    The N accesses don't need to happen in parallel; they are faster whenever they take place because they need one block in cache rather than the equivalent of k>1 blocks together to be fast (executed from cache) and it is unconditionally much better, even without assumptions about hot and cold keys.
gopalv 5y ago
> whether this would really work out in most workloads > just because it keeps the cache-lines hotter and less likely to be evicted. Okay, so keeping cache for a bloom filter problem is real - but the real force evicting memory out of the cache line is the next row-group you read + all the other stuff you have to do when you implement this in a database product. Memory bandwidth is contested heavily and the caches will get knocked out every 1024 rows. So the two things I work with, Apache Hive and Apache Impala switched to a blocked bloom filter at different points in time. Hive BloomKFilter - https://github.com/apache/hive/blob/master/storage-api/src/java/org/apache/hive/common/util/BloomKFilter.java#L35 https://github.com/apache/hive/blob/master/storage-api/src/j... Impala/Kudu one - https://github.com/apache/impala/blob/master/be/src/kudu/util/block_bloom_filter.h#L66 https://github.com/apache/impala/blob/master/be/src/kudu/uti... The C++ one also has an AVX specialization, while the Java one relies on the JVM to do it (not always) - https://github.com/apache/impala/blob/master/be/src/kudu/util/block_bloom_filter_avx2.cc#L72 https://github.com/apache/impala/blob/master/be/src/kudu/uti... We ran a lot of trivial benchmarks and several benchmarks where the shuffle-join+network (not sort-merge, this is just a partitioned hash join) generates a bloom filter (a semijoin) before sending rows out and the 1-cache line version won out when the bloom filter went slightly over the 1 Million + 5% rate [1]. The regular bloom filter went from (38ns -> 108ns for 1k -> 1m items), while the BloomK stuck at (27ns) despite making room for a million times more items in the bloom. The bloom-1 (which is the 64bit version) underperformed on accuracy (was ~2x faster at 16ns per op, but worse at filtering out items). [1] - https://github.com/prasanthj/bloomfilter/tree/master/benchmarks https://github.com/prasanthj/bloomfilter/tree/master/benchma...
trevor7 5y ago
If you're still a part of this site can i ask a few questions about my RSU's and how to handle them ?

csense 5y ago

> I'm really suspicious about whether this would really work out in most workloads. What kinds of workloads are those? Workloads where the Bloom filter itself fits in cache? > On modern architectures, it's the random memory reference that kills performance Yeah, the whole point of the article is that moving from a traditional Bloom filter to a block Bloom filter is to improve from N random accesses per query/update to 1 random access per query/update. > Ultimately it depends on cache pressure and how over-subscribed the cache is The unspoken assumption in the article is that the Bloom filter is much bigger than cache. If your Bloom filter fits in cache, or you're writing for something with superfast RAM like a GPU or a Xeon Phi or something, block Bloom filters are wasteful for you. But I'm pretty sure the common case is writing normal applications running on reasonable general-purpose CPU's with Bloom filter sizes in the hundreds of MB or more. [1] [2] [1] If the Bloom filter's smaller than hundreds of MB, your data's probably small enough that you decide Bloom filters aren't worth the hassle and just use a HashMap or language equivalent. [2] If you're using a Bloom filter to do some sort of network stuff, like figuring out the set difference of two peers' objects in some p2p protocol, you probably don't care too much about block Bloom filters, because in this application memory access time is probably going to be dominated by network latency.

becurious 5y ago
If you had many lookups to do, then an approach with a coroutine that issues a prefetch instruction then yields to other lookups while the data is fetched in memory might be effective. Similar to this: http://www.vldb.org/pvldb/vol11/p1702-jonathan.pdf http://www.vldb.org/pvldb/vol11/p1702-jonathan.pdf
a1369209993 5y ago
> to improve from N random accesses per query/update to 1 random access per query/update. I think their concern is that N (nondependent) random accesses can happen in parallel not much more slowly than 1 random access (assuming good speculation and sufficient memory bandwidth).
- HelloNurse 5y ago
  The N accesses don't need to happen in parallel; they are faster whenever they take place because they need one block in cache rather than the equivalent of k>1 blocks together to be fast (executed from cache) and it is unconditionally much better, even without assumptions about hot and cold keys.

gopalv 5y ago

> whether this would really work out in most workloads > just because it keeps the cache-lines hotter and less likely to be evicted. Okay, so keeping cache for a bloom filter problem is real - but the real force evicting memory out of the cache line is the next row-group you read + all the other stuff you have to do when you implement this in a database product. Memory bandwidth is contested heavily and the caches will get knocked out every 1024 rows. So the two things I work with, Apache Hive and Apache Impala switched to a blocked bloom filter at different points in time. Hive BloomKFilter - https://github.com/apache/hive/blob/master/storage-api/src/java/org/apache/hive/common/util/BloomKFilter.java#L35 https://github.com/apache/hive/blob/master/storage-api/src/j... Impala/Kudu one - https://github.com/apache/impala/blob/master/be/src/kudu/util/block_bloom_filter.h#L66 https://github.com/apache/impala/blob/master/be/src/kudu/uti... The C++ one also has an AVX specialization, while the Java one relies on the JVM to do it (not always) - https://github.com/apache/impala/blob/master/be/src/kudu/util/block_bloom_filter_avx2.cc#L72 https://github.com/apache/impala/blob/master/be/src/kudu/uti... We ran a lot of trivial benchmarks and several benchmarks where the shuffle-join+network (not sort-merge, this is just a partitioned hash join) generates a bloom filter (a semijoin) before sending rows out and the 1-cache line version won out when the bloom filter went slightly over the 1 Million + 5% rate [1]. The regular bloom filter went from (38ns -> 108ns for 1k -> 1m items), while the BloomK stuck at (27ns) despite making room for a million times more items in the bloom. The bloom-1 (which is the 64bit version) underperformed on accuracy (was ~2x faster at 16ns per op, but worse at filtering out items). [1] - https://github.com/prasanthj/bloomfilter/tree/master/benchmarks https://github.com/prasanthj/bloomfilter/tree/master/benchma...

trevor7 5y ago

If you're still a part of this site can i ask a few questions about my RSU's and how to handle them ?