Subject: Re: more Q&D results [hash for use in the kernel]
To: matthew green <mrg@eterna.com.au>
From: David Laight <David.Laight@btinternet.com>
List: tech-kern
Date: 11/29/2001 13:00:33
How good are these hash functions on non-random binary data?
Hashing random data is (should be) trivial.

Say hash a 64 byte buffer containing 1 32bit integer that is incremented
each time (the rest of the data being unchanged random - or zero - bytes).

This is probably nearer to what (NFS certainly) is trying to hash.

    David 


----- Original Message ----- 
From: matthew green <mrg@eterna.com.au>
To: <thorpej@wasabisystems.com>
Cc: <tech-kern@netbsd.org>; <tech-perform@netbsd.org>; ozan s. yigit <oz@zonzorp.canada.sun.com>
Sent: Wednesday, November 28, 2001 11:58 PM
Subject: re: more Q&D results [hash for use in the kernel] 


>    
>     > i added the "perl" hash function that was posted here; it is a variant
>     > of the bernstein's k=33 hash, and the multiplication can be eliminated.
>    
>    Indeed, GCC does eliminate the multiplication in the targets I checked.
> 
> amusingly, `gcc -mv8' on the sparc generates a call to smul, rather than
> the handful of shift/add's, for the FNV hash.  the perl hash has fewer
> shift/adds IIRC.  i wonder which is actually faster :-)