[Freeciv-Dev] Re: Better string hashing function

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

On Sat, 1 Apr 2000, David Pfitzner wrote:

> On Sun, 26 Mar 2000, Vasco wrote:
> 
> > I've been making some tests...
> 
> > == 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
> >  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

> Notice the time spent in hash_lookup_data which is _not_ spent
> in the subfunction hash_fval_string has actually increased:
> 
> 1.43-.77 = .66 new, vs 3.06-2.81 = .25 old, if I'm interpreting 
> these correctly.
> This suggests to me that there are more collisions: the new 
> function is calculating much faster hashes, but they are not
> as "good".  I put in some more code to check this, and indeed
> the new function triggers the i++ in internal_lookup() about 
> 5 times more (364072 vs 75689, cumulated for all hashes used
> loading a 93K savefile).

Yes, i had already noticed the new function increased the number of
colisions.  That is most likely caused by the fact that the function only
uses the first 31 chars of the strings to calculate the hash.  This
increases the speed on long strings however.

> Of course the faster time for hash_lookup_data overall means 
> the new hash function is an overall win nevertheless...

It's twice faster on lookups! nothing to be sneered at....

> According to my tests the practical speedup is quite small.  
> For my 93K test savegame, the loadtime (reported by --debug 2) 
> improved from:
> 
>   3.8  to 3.7 using gcc -O  
>   3.14 to 3.1 using gcc -O2 
> 
> (Rough averages over several runs, omitting the first few.)
> (By default I use gcc -O in my "development" tree, because 
> it compiles faster, and I re-compile freeciv alot :-)
> 
> Ie, a fraction of a second or a few percent.

True, but little by little you get a considerable improvement, especially
considering the improvement is more noticeable on larger savegames.

> So I guess the time spent within hash_fval_string/hash_lookup_data
> is not currently a bottleneck when loading savegames.

Aparently it's not much of a problem, yes.  But i noticed on my profiling
runs that using the old hash function, it was the hash function which
constituted the main bottleneck.

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