Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 14 Sep 2015 15:46:35 +0300
From: Solar Designer <>
Subject: Re: Judy array


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!


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.