Subject: Re: New hash algorithm - FNV - for use in the kernel
To: , <email@example.com>
From: David Laight <David.Laight@btinternet.com>
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
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...