[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 14 Sep 2015 15:46:35 +0300
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Judy array
Fred,
On Sun, Sep 13, 2015 at 08:28:08PM -0700, Fred Wang wrote:
> For the most part (and in particular, when Bloom filters are very sparse), they are always a win for "our" type of lookup. In cracking, the vast majority of hashes will fail, and that is what I optimized for.
Do you mean a Bloom filter is always a win over a simple bitmap for the
same limited RAM usage? If so, that's no surprise. Or do you mean it's
always a win regardless of RAM usage, when optimizing for speed only?
If so, that's unexpected to me except when a significant portion fits in
a cache or when you optimize the order in which you perform the lookups
to achieve a higher cache hit rate (or when you manage to use multiple
bits per lookup at application level, but that's probably not what you
meant above yet).
> A Judy array on its own is already faster than what John is doing. Fronting this with a Bloom filter vastly improves performance. Regretfully, I did not keep my bitmap timing - but it was not impressive.
Maybe you were limiting its size "too much"? (I understand and agree
there isn't always more RAM to throw at the task.)
Thank you for your advice!
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.
