Author: Robert Hyatt
Date: 14:33:54 01/22/99
Go up one level in this thread
On January 22, 1999 at 13:05:51, Eugene Nalimov wrote: >On January 22, 1999 at 08:52:52, Robert Hyatt wrote: > >>On January 22, 1999 at 00:31:40, KarinsDad wrote: >> >>>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. >>>> >>>>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.. >>> >>>Robert, >>> >>>Thanks for the input. >>> >>>I have been thinking about this method a little bit this evening and although I >>>came up with some good ideas, I keep pounding into the problem of 95% of the >>>hash is full, how can I continue to find open slots without overwriting the >>>nodes (for my program, this would currently be more preferable)? >>> >>>It may not be solvable this way, or at least not in a reasonable amount of time. >>> >>>On the other hand, each of the solutions in this thread seem to run into that >>>problem to some extent. >>> >>>KarinsDad :) >> >>You can't go very far here. Because you probe at _every_ node in the tree. If >>you make your probe 10x slower by looping, you will _really_ feel the slow-down, >>and it isn't clear that getting too cute is important, when you can buy a gig of >>memory for about $1,000 now... > >That depends. Not every chess program user can afford to buy 1Gb >of RAM. And must popular motherboards will not accept that much. I think most new ones do, as 256MB DIMMS are readily available now... But it isn't cheap of course... > >Based on my experience, all depends on how fast you can fill your >hash table. As soon as it's *totally* full, more complex replacement >schema can be better, even if it causes some nps degradation. > >As long as program has a lot of RAM, and plays mostly blitz (or fast >enough games), simple schemas must be Ok. Let's take Crafty as >example (all numbers are very crude approximations): its' current >speed is ~1Mnps. As you don't cache q-nodes, it has to store 500K >positions per second. So, when time control is "move in 10 seconds", >you have to store max 5M positions. That's only 40Mb. I think that >serious degradation will start when you'll have to store 10 times >as much positions as you have hash entries. So, on your machine you >probably will be Ok even for games with standard time controls, if >you'll allocate 128Mb for hash. > minor 'nit'... hash entry = 16 bytes... so that is 80mb. But in a game of 40/2, where I search (counting pondering) for 6-10 minutes, that turns into 10*60*500000*16 = 5 gigabytes if I counted right. But even with your 10 secs, the point is valid. Memory is cheap enough that for blitz games, such 'rehashing' isn't important at all. >Average Crafty user has much smaller hash. From the other side, >his/her nps is much less, too... > >So for current machines you can be right... But if you'll try to >play 1-to-100 match again, or run your program on WinCE (reasonable >fast CPU and 2Mb of RAM), more complex hash management will be Ok. yes... then I nee 500 gigs.. :) > >Eugene
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.