Comments on: Not Always Lovely Blooms… http://rusty.ozlabs.org/?p=20 Stealing From Smart People Thu, 19 Aug 2010 18:12:38 +0000 http://wordpress.org/?v=2.9.2 hourly 1 By: rusty http://rusty.ozlabs.org/?p=20&cpage=1#comment-7 rusty Thu, 29 Oct 2009 10:47:34 +0000 http://rusty.ozlabs.org/?p=20#comment-7 Tridge says we're down a factor of 100x at 100,000 strings. That means we need log(n) to grow by a factor of 100, which is for all intents infinite. Note that for unaligned strings and cache line size 128, qsort will almost always take a single cacheline per string, bloom filter 2 cachelines about 100/128 times. That's probably the real killer here (why he saw it get worse as the number of strings gets bigger). Also, the Bloom filter size grows linearly with the number of elements (for constant false-positive probability). If you can't sort in place, the sort solution grows by one pointer per element too. If you can, it's a lose for Bloom. Hope that helps! Tridge says we’re down a factor of 100x at 100,000 strings. That means we need log(n) to grow by a factor of 100, which is for all intents infinite.

Note that for unaligned strings and cache line size 128, qsort will almost always take a single cacheline per string, bloom filter 2 cachelines about 100/128 times. That’s probably the real killer here (why he saw it get worse as the number of strings gets bigger).

Also, the Bloom filter size grows linearly with the number of elements (for constant false-positive probability). If you can’t sort in place, the sort solution grows by one pointer per element too. If you can, it’s a lose for Bloom.

Hope that helps!

]]> By: Anonymous http://rusty.ozlabs.org/?p=20&cpage=1#comment-6 Anonymous Thu, 29 Oct 2009 09:50:07 +0000 http://rusty.ozlabs.org/?p=20#comment-6 Presumably if you had a *lot* more strings (enough that log(n) becomes bigger than the average string length), bloom filters might start to prove faster. Presumably if you had a *lot* more strings (enough that log(n) becomes bigger than the average string length), bloom filters might start to prove faster.

]]> By: Robert Collins http://rusty.ozlabs.org/?p=20&cpage=1#comment-5 Robert Collins Tue, 27 Oct 2009 11:20:05 +0000 http://rusty.ozlabs.org/?p=20#comment-5 We've found that bloom filters are really marginal much of the time - its a very clever idea, but you have to have rather precise circumstances for them to be really useful. We’ve found that bloom filters are really marginal much of the time – its a very clever idea, but you have to have rather precise circumstances for them to be really useful.

]]>