Author: Robert Hyatt
Date: 20:46:27 01/21/99
Go up one level in this thread
On January 21, 1999 at 19:04:21, KarinsDad wrote: >On January 21, 1999 at 12:37:32, Heiner Marxen wrote: > >[snip] > >> >>Another method (which I happen to use) to avoid bucket overlaps >>is ``quadratic rehashing´´. Instead of using a constant increment, >>we linearly increase the steps: inc=1,2,3,4,5,... >> >>XX.X..X...X....X >>.YY.Y..Y...Y....Y >>..ZZ.Z..Z...Z....Z >> >>Also, the slots of a bucket are still somewhat nearby, which is good >>for cache locality. >> >>Knuth seems to not mention this method, and I do not remember where >>I found it, so I cannot give a reference. >> >>Heiner > >I like this. I think I'll try this out. However, I think it needs a modification >due to the following possiblity: > >XX.X..X......... >YY.Y..Y...Y..... >ZZ.Z..Z...Z....Z > >Thanks Heiner :) :) > >KarinsDad Just note this will kill a PC. Because it fetches 32 byte lines from memory in a burst cycle. for best performance you should use all those 32 bytes since you had to wait on them. If you do anything else, you will end up hitting one line per probe with a big cache miss penalty for each probe. This only works on architectures like the Cray where memory is organized a lot differently with no cache of any kind... just high sustained thruput..
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.