[Freeciv-Dev] Re: Better string hashing function

[Vasco Alexandre Da Silva Costa <vasc@xxxxxxxxxxxxxxxxxxxxx>]

On Sun, 26 Mar 2000, Vasco Alexandre Da Silva Costa wrote:

> Hello,
> i saw the string hashing function in hash.c and since in the function
> comment it said "Anyone know a good one?" here is one:
 
 
unsigned int hash_fval_string(const void *vkey, unsigned int num_buckets)
{
  register const char *key = (const char *)vkey;
  register unsigned result=0;
  register int i;

  for(i=0; *key && i<32; i++)
    result = result * 33U + *key++;

  return (result % num_buckets);
}
 
 
> It's been ripped off from Perl.

I've been making some tests...

One test consists of the server loading a 23K save file. here are the results:

== old function
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 22.73      0.05     0.05    25246     1.98     1.98  hash_fval_string
  0.00      0.22     0.00    15089     0.00     1.98  hash_lookup_data

== new function
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
  7.69      0.05     0.01    25246     0.40     0.40  hash_fval_string
  0.00      0.13     0.00    15089     0.00     0.79  hash_lookup_data



With a 70K save file:

== old function
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 35.48      0.11     0.11    39192     2.81     2.81  hash_fval_string
  0.00      0.31     0.00    24618     0.00     3.06  hash_lookup_data


== new function
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 12.00      0.03     0.03    39192     0.77     0.77  hash_fval_string
  4.00      0.17     0.01    24618     0.41     1.43  hash_lookup_data


Speedups calculated with Amdahl's Law from the 70K case:

speedup = old time
          --------
          new time

 2.14 speedup on hash_lookup_data
 3.65 speedup on hash_fval_string


I guess the improvements are quite clear :)

---
Vasco Alexandre da Silva Costa @ Instituto Superior Tecnico, Lisboa