Author: Eugene Nalimov
Date: 10:05:51 01/22/99
Go up one level in this thread
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. 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. 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. 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.