Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 18 Sep 2015 14:05:27 +0300
From: Solar Designer <>
Subject: Re: larger bitmaps and hash tables

On Fri, Sep 18, 2015 at 03:53:20AM -0700, Fred Wang wrote:
> On Sep 18, 2015, at 3:49 AM, Solar Designer <> 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?

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.


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.