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.