Re: An interesting performance thing ?

["J. Bruce Fields" <bfields@fieldses.org>]

On Wed, Dec 14, 2005 at 12:22:38PM -0600, Iozone wrote:
>     Then the hash_long function would have done a nice job.  Since
>     one is not converting the network neutral IP address into a 
>     host binary format, here is an example of the hash distribution
>     that, I believe via experimentation, is currently being seen on 
>     Little Endian 64 Bit systems....

A little bit of fiddling about with pencil and paper shows what's
happening:  suppose longs are 64 bits and let x be a long.  Then
hash_long operates on x by multiplying it by

	 1 - 2^18 - 2^51 + 2^54 - 2^57 + 2^61 + 2^63

and then taking the high bits.

You can think of that as adding and subtracting a bunch of left-shifts.
Note that the last four terms are all shifts by at least 51 bits, so
wipe out all but the lowest 13 bits.  So if those low 13 bits are all
constant, then the only variation is from multiplication by (1 - 2^18).
But if the input is small (say the top 32 bits are all zero...) then
multiplying by (1 - 2^18) doesn't affect the high bits of the output at
all.

So in our case, where the 32 high bits are zero and we're only asking
for the top 8 bits, it looks like all but the bottom 13 bits of x (the
top 13 bits of the IP address) are ignored.

--b.


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs