[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20230422215556.GB16507@openwall.com>
Date: Sat, 22 Apr 2023 23:55:56 +0200
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Birthday paradox
On Wed, Apr 19, 2023 at 11:47:56PM +0200, magnum wrote:
> I read up on Bloom filters and tried this - indeed very trivial changes
> make it a traditional k-level Bloom filter. The performance (actual
> FP's counted by kernel) almost didn't change at all (tried both with
> sparsely and heavily populated bitmaps) and where it ever so slightly
> did, it was sometimes in favor of the original code and sometimes of the
> modified one. My conclusion is they are very near equivalent, even more
> so than I presumed.
As you've already figured out, the difference is in being able to adjust
k independently from size, and the FP rate does go further down with
some higher k.
Another difference, though, is the locality of reference becomes worse.
When it's just local memory or non-thrashed L1d cache, this shouldn't
matter. But with the separate bitmaps (or how about two Bloom filters)
you could use both local memory and L1d as different early-reject steps
(faster, gather-friendly memory first), before proceeding to the global
memory hash table. Not sure this is worth the complexity. Per what you
write below, it seems not.
> I now added code that checks if the offset + hash tables fit into local
> memory and if so, skips the bitmap completely. This happens up to about
> 5300 loaded hashes. But just like most things I tried, this performs
> just the same as using the bitmap - neither better or worse.
A complete lack of speed difference is puzzling. Can you share some
speeds you're getting by loaded hash count - e.g., 1, 100, 5300, 100k,
1M, 10M, 100M?
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
