[Freeciv-Dev] Re: Better string hashing function

[David Pfitzner <dwp@xxxxxxxxxxxxxx>]

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

> 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 :)

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).

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

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.

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

Regards,
-- David