[Mesa-dev] [PATCH 3/3] util: Use 32 bit integer hash function for pointers

[Thomas Helland]

It is hard finding a statement or direct quote from Thomas
on the licensing of his algorithm.
I tried the 6 shift algorithm Bob suggests this morning before work.
It seems Thomas' algorithm inlines very nicely, giving the boost.
Bob's version probably gives more collisions, as the time spent
in the insert and search functions increase.
Also there is no speedup of the hash compared to FNV-1a.
Disclaimer: It was hacked together and tested over a
bowl of cereal, so I might have messed something up.
I guess we should drop this patch for now.
On 30 Mar 2015 01:17, "Jordan Justen" <jordan.l.justen at intel.com> wrote:

> On 2015-03-29 13:28:02, Thomas Helland wrote:
> > (Forgot to send to list)
> >
> > That is indeed an issue.
> > I found the original article on the wayback machine and it
> > doesn't state anything particular wrt license.
> > However, it seems to be used in a LOT of projects.
> > (javascript, chromium, hiphop-php, kde, +++)
> >
> > I found this webpage that gives some more insight:
> > http://burtleburtle.net/bob/hash/integer.html
> > (it seems to be the website of Bob Jenkins)
> > It states the following:
> >
> > "The hashes on this page (with the possible exception
> > of HashMap.java's) are all public domain.
> > So are the ones on Thomas Wang's page.
> > Thomas recommends citing the author
> > and page when using them."
>
> Is there a reference to Thomas directly indicating this?
>
> On that same page, Bob provides some hash functions of his own, and
> directly states that they are public domain. He would probably be in a
> better position to speak for his code than Thomas's. :) He does
> indicate that Thomas's version is faster than all of his.
>
> -Jordan
>
> > So it looks like it is public domain.
> > I'll add a credit to Thomas, and link
> > to Bob Jenkins' webpage .
> > Does that sound like an acceptable solution?
> >
> > 2015-03-29 20:51 GMT+02:00 Jordan Justen <jordan.l.justen at intel.com>:
> > > On 2015-03-29 11:05:40, Thomas Helland wrote:
> > >> Since a pointer is basically just an int we can use integer hashing.
> > >> This one is taken from https://gist.github.com/badboy/6267743
> > >
> > > There doesn't seem to be a license associated with this code, nor is
> > > it indicated that it is public domain code.
> > >
> > > -Jordan
> > >
> > >> A google search seems to suggest this is a common and good algorithm.
> > >> Since it operates 32 bits at a time it is really effective.
> > >> assert that we are hashing 32bit aligned pointers.
> > >>
> > >> Signed-off-by: Thomas Helland <thomashelland90 at gmail.com>
> > >> ---
> > >>  src/util/hash_table.c | 24 ++++++++++++++++++++++--
> > >>  1 file changed, 22 insertions(+), 2 deletions(-)
> > >>
> > >> diff --git a/src/util/hash_table.c b/src/util/hash_table.c
> > >> index 24184c0..54d04ef 100644
> > >> --- a/src/util/hash_table.c
> > >> +++ b/src/util/hash_table.c
> > >> @@ -393,6 +393,15 @@ _mesa_hash_table_random_entry(struct hash_table
> *ht,
> > >>     return NULL;
> > >>  }
> > >>
> > >> +static inline uint32_t
> > >> +hash_32bit_int(uint32_t a) {
> > >> +   a = (a ^ 61) ^ (a >> 16);
> > >> +   a = a + (a << 3);
> > >> +   a = a ^ (a >> 4);
> > >> +   a = a * 0x27d4eb2d;
> > >> +   a = a ^ (a >> 15);
> > >> +   return a;
> > >> +}
> > >>
> > >>  /**
> > >>   * Quick FNV-1a hash implementation based on:
> > >> @@ -406,8 +415,19 @@ _mesa_hash_table_random_entry(struct hash_table
> *ht,
> > >>  uint32_t
> > >>  _mesa_hash_data(const void *data, size_t size)
> > >>  {
> > >> -   return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
> > >> -                                          data, size);
> > >> +   uint32_t hash = _mesa_fnv32_1a_offset_bias;
> > >> +   const uint32_t *ints = (const uint32_t *) data;
> > >> +
> > >> +   assert((size % 4) == 0);
> > >> +
> > >> +   uint32_t i = size / 4;
> > >> +
> > >> +   while (i-- != 0) {
> > >> +      hash ^= hash_32bit_int(*ints);
> > >> +      ints++;
> > >> +   }
> > >> +
> > >> +   return hash;
> > >>  }
> > >>
> > >>  /** FNV-1a string hash implementation */
> > >> --
> > >> 2.3.4
> > >>
> > >> _______________________________________________
> > >> mesa-dev mailing list
> > >> mesa-dev at lists.freedesktop.org
> > >> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150330/bb359658/attachment-0001.html>