Re: Does anyone have a better scm_string_hash ?

[Marius Vollmer]

Marius Vollmer <address@hidden> writes:

> Both should be much better than the one we have right now and I'm
> going to install the one from Roland without the hash_mask.

Ok, I have installed the following hash function into 1.7.  As a nice
side effect, guile seems to start a bit faster now.  (Although the new
function does more work than the old.  Talk about being too clever.)

    unsigned long 
    scm_string_hash (const unsigned char *str, size_t len)
    {
      /* from suggestion at: */
      /* http://srfi.schemers.org/srfi-13/mail-archive/msg00112.html */

      unsigned long h = 0;
      while (len-- > 0)
        {
          /* h = (str[i] + h*37) % 2^bits_per_long; */
          h = *str++ + (h<<5) + (h<<2) + h;
        }
      return h;
    }

I removed 'i' from the calculation since neither the glib function nor
the one from Java uses it and I'm wary of heuristical magic when it
comes to random number generation and hash functions.  Permutations of
the input will still lead to different hash values since, for example
str[0]+str[1]*37 is different from str[1]+str[0]*37.

Just for kicks, I'm now going to see what kind of code GCC generates
for h*37 as compared to (h<<5) + (h<<2) + h...

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405