Subject: Re: New hash algorithm - FNV - for use in the kernel
To: None <tech-perform@netbsd.org, tech-kern@netbsd.org>
From: Simon Burge <simonb@wasabisystems.com>
List: tech-perform
Date: 11/29/2001 15:39:08
I fired up my sparc10 (with a 40MHz sun4m cpu) and tried tests with and
without hardware multiplication (ie the -mv8 cc option).

For the "perl" hash, it resolved the *33 to a shift and add both with
and without -mv8, but the "fnv" hash uses the "smul" instruction with
-mv8.

Here's some results, first without -mv8:

	./hashtest.sparc s 65536 < flist.2
	total items:  92383
	hash dumb         used   7201   max     63   time 1.392sec
	hash fnv          used  49711   max      9   time 2.704sec
	hash lennart      used  49509   max      8   time 1.937sec
	hash crc          used  46967   max     80   time 2.025sec
	hash perl         used  49413   max      9   time 1.853sec
	hash mouse        used  49138   max      9   time 2.031sec

and now with -mv8:

	./hashtest.sparc s 65536 < flist.2
	total items:  92383
	hash dumb         used   7201   max     63   time 1.394sec
	hash fnv          used  49711   max      9   time 2.542sec
	hash lennart      used  49509   max      8   time 1.938sec
	hash crc          used  46967   max     80   time 2.194sec
	hash perl         used  49413   max      9   time 1.852sec
	hash mouse        used  49138   max      9   time 2.031sec

So fnv is ~10% faster with hardware multiply on my sparc10.

The "crc" hash seems consistantly slower by ~5%, but a disassembly shows
that only a couple of instructions we reordered - "ldub, srl, sll" gets
reordered to "srl, sll, ldub" with -mv8.

Simon.
--
Simon Burge                            <simonb@wasabisystems.com>
NetBSD CDs, Support and Service:    http://www.wasabisystems.com/