Author: Heiner Marxen
Date: 13:12:20 01/22/99
Go up one level in this thread
On January 21, 1999 at 23:46:27, Robert Hyatt wrote: >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. You are right, of course. I originally dicided to use quadratic rehashing in order to compensate for my not so good hash function (the hash table did not fill up so well). When I tried a Zobrist hash, that filled the hash table pretty well, but where slower overall for some non-trivial reason I omit here. Also, my hash table entries are 40 bytes large (since it is a problem solving program, the complete board must be there, not just a good hash code). That could become better, if I would separate my cache entries into two parts (two separate arrays), where the first part would contain what is mostly sufficient for the probing. But that introduces some complexity to the data structure and code, only based on assumptions about the hardware cache architecture... what I dislike somewhat. It is not uncommon that I let my program compute several hours on one position. The computation done last night generated over 64M entries while there where just 1.7M hash table entries. And since I prefer entries with larger depth (i.e. first throw out results with smaller depth), this may lead to a situation where the complete hash table is mostly filled with deep entries, and the normal ones are thrown out too fast to have a chance to get a hit. Here I felt that it is a good thing to have hash buckets that do not overlap so much. But I may be misguided, here. Anyhow, everyone could/should just try the alternatives, and measure speed, and then decide (as always). These alternatives are not that hard to code. >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.. Yes. So, please: give me a Cray :-)
This page took 0 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.