[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <68FFBC79-9547-4981-A05F-39B42B89C94E@gmail.com>
Date: Fri, 18 Sep 2015 04:08:17 -0700
From: Fred Wang <waffle.contest@...il.com>
To: john-dev@...ts.openwall.com
Subject: Re: larger bitmaps and hash tables
On Sep 18, 2015, at 4:05 AM, Solar Designer <solar@...nwall.com> wrote:
> On Fri, Sep 18, 2015 at 03:53:20AM -0700, Fred Wang wrote:
>> On Sep 18, 2015, at 3:49 AM, Solar Designer <solar@...nwall.com> wrote:
>>> I would also like to give Fred a chance to contribute Judy before we
>>> would have invested much time into a hash table rework. So adjusting
>>> the bitmap sizes is fine to be done now, but changing how the bitmap and
>>> hash table interact might be premature. I suspect that having a full
>>> 32-bit partial hash easily available would be beneficial for possible
>>> alternatives to hash tables as well. Fred, any comments on this?
>>
>> You are correct. There is no need for a hash table with Judy, and it will continue to offer long term benefits.
>
> Sounds good. How many bits would you need to input to Judy? And would
> it be best to minimize their overlap with what had been used for bitmap?
As many as possible. Ideal for 64 bit architectures is 64 bits, for 32 bit, 32 bits.
Judy does strings, too, which is useful for salt processing.
>
> Would it be helpful to have 32 bits, many of which (up to 30 maybe) had
> been used for bitmap, or is it not enough anyway?
>
> I'm afraid we don't consistently have more than 32 bits readily computed
> by the time we start hash comparisons. Computation may be finished
> (when needed) in cmp_one() or/and cmp_exact(), but these are normally
> beyond the point where we do hash tables or would do Judy.
Traditional linked lists are all that is required after that.
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.
