Subject: Re: more Q&D results [hash for use in the kernel]
To: None <tech-kern@netbsd.org>
From: David Laight <David.Laight@btinternet.com>
List: tech-kern
Date: 11/29/2001 12:15:05
> > 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 :-)
Probably depends on the implementation of the architecture in the cpu...
Multiply is surprisingly quick on modern cpus - 3 clocks on the strongArm.
Additionally 'multiply and accumulate' is as fast as 'multiply' if the
architecture designers bothered to include the instruction! So you
may save another instruction as well.
If you can order the instructions so that the result of the multiply
isn't needed immediately it is almost certainly faster still...
FYI multiply on a 286 took 21 clocks, the 386 has a max of 21, the 68020
takes about the same (these are 16x16 multiplies). I guess these are
all microcoded loops - not an array of add cells.
David