Subject: Re: New hash algorithm - FNV - for use in the kernel
To: , <>
From: David Laight <>
List: tech-kern
Date: 11/28/2001 10:45:44
> You can think of the problem as "how likely is it that the data I am
> running the CRC over will collide with the cache line the part of the
> lookup table I need to look at is in"?  You need to know a surprising
> amount about the hardware to get it right.

No - most caches are (at least) 2-way set associative, so a clash
between the table and buffer doesn't really matter.

It is the time taken to load a line into the cache that matters.

Do some quick sums - anyone off hand know how long a 32 byte burst
read from SDRAM takes?  My guess is around 100ns - more if the page
isn't open.

For a 1GHz cpu 100ns is 100 cycles, probably more than 100 (simple)
instructions.  You can iterate a few times aound a simple loop
for the cost of a single cache miss.

Throws the cat among the pidgeons when looking at algorithms for
CRCing short buffers, finding the first set bit etc...