Re: Does anyone have a better scm_string_hash ?

[Roland Orre <orre@nada.kth.se>]

Thanks,
I replaced the scm_string_hash with the one below, reminding about what
Ludovic Courtès suggested. Of course it could have been preferrably to
use it as a private hash function only, but I prefer to use the
standard functions at all places, especially as I hadn't designed
around using a private hash function (it was used in many places...).

The performance increase we obtained with this hash function were
tremendous. With the problematic symbol table the average lookup
time went down from 10 ms to 9 us on this specific machine (1 GHz PIII).
The max number of collisions went down from 13856 to 7 (on a total
of 14166 strings in a table of length 8209). The number of empty
entries went down from 8201 to 909. The run time for a data mining
scan on a database went down from 5 hours to 15 minutes. The reason
I added i in the hash function was to decrease the risk that two
strings with same but permuted contents would hash to the same value.
I have not done any thorough tests on this hash function yet.

	Best regards
	Roland Orre

/* replaced by Roland Orre orre@nada.kth.se */
#define hash_mask 0x00FFFFFF
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 */
  int i;
  /* originally h=0 was suggested. orre@nada.kth.se */
  unsigned long h=177;

  for (i = len-1; i >= 0; i--)
    {
      /* h = (str[i] +i+ h*37) & hash_mask; */
      h = (str[i] + i + (h<<5) + (h<<2) + h) & hash_mask;
    }
  return h;
} /* scm_string_hash */




On Fri, 2003-11-14 at 16:51, Ludovic Courtès wrote:
> You might want to look at
> http://srfi.schemers.org/srfi-13/mail-archive/msg00112.html .
> 
> Basically, the idea there is that a hash key for string cn..c0 is:
>      h = (c0 + c1*37 + c2*37^2 + ...) % hash_size.
> I used that and it *seems* to work quite well.
> 
> This can be written as follows:
> 
>   k = 0;
>   while (*string)
>     {
>       k  = (k * 37) + (*string);
>       k %= hash_size;
>       string++;
>     }
>   return k;
> 
> Cheers,
> Ludovic.
> 
> Today, 15 minutes, 40 seconds ago, Roland Orre wrote:
> > I noticed that our data mining software run very very slow with a
> > new data base. I localized the problem to scm_string_hash.
> > 
> > A hash table in this case was loaded with 14166 strings. I have
> > a function which creates a reasonable sized hash table, in this
> > case the hash table size was 8209.
> > 
> > 13856 of these strings were hashed to the same index= 1067.
> > 303 strings got index = 8061.
> > 2 strings got the index = 754.
> > 8201 entries were empty.
> > 
> > We are running guile 1.6 but I checked the scm_string_hash from a recent
> > 1.7 CVS also and the function in hash.c there is identical.
> > 
> > I added a few of the symbols hashing to 1067 below. One can of course
> > argue that the symbols in this case should be hashed as numbers.
> > Anyway, does anyone have any hint or have a better string hash function?
> > 
> > 	Best regards
> > 	Roland Orre
> > 
> > 
> > A few strings hashing to entry 1067 for hash table length 8209:
> > "01632001" "01627301" "01626801" "01626601" "01626501" "01626401"
> > "01626301" "01626101" "01626001" "01625901" "01625801" "01625701"
> > "01625401" "01625301" "01625101" "01625001" "01624801" "01624601"
> > "01624501" "01624401" "01624301" "01624101" "01624001" "01623901"
> > "01623801" "01623701" "01623601" "01623501" "01623401" "01623201"
> > "01623101" "01622901" "01622801" "01622701" "01622601" "01622401"
> > 
> > 
> > 
> > 
> > _______________________________________________
> > Guile-user mailing list
> > Guile-user@gnu.org
> > http://mail.gnu.org/mailman/listinfo/guile-user



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user