Author: Johan de Koning
Date: 23:12:05 08/19/03
Go up one level in this thread
On August 19, 2003 at 17:04:44, Dieter Buerssner wrote: >On August 19, 2003 at 16:52:43, Sune Fischer wrote: > >>If you swear this is faster, I will take your word for it, but off hand I don't >>see why it should be the case. >>You still need to plow through every single hash entry, with latency and all >>that comes with it. Streaming is faster than random access, but why is clearing >>one bit faster than memsetting the whole thing? >>Clearing one bit is actually more complicated, requiring loops (with >>conditionals) and logic, unless of course you have very big entries. > >First I thought: don't clear the bits. With every new search, toggle the >"current_age_bit". Add little logic to Probe/Store functions (it should not >decrease efficiency much, because we need a slow memory look-up anyway), that >just assumes the entry is empty, when the bit does not fit. > >But at second thought, this would not really help. Because the new search might >not touch one entry, and the second new search would assume, that the entry is >current. So, there is again an influence of the history of the game due to TTs, >something that Johan wanted to avoid from the start. Exactly my thoughts. Unfortunately I posted after first but before second thought. :-) So let's forget about this cheapo 1-bit age counter. >Another approach would be, to have the age bits in one seperate small table. >Assuming you have 64 Mb hash, with 16 bytes each entry, this would be 4 million >bits, or 1/2 Mb of RAM. Something that probably would stay in second level cache >most of the time on a modern computer. Clearing would use practically no time, >but accessing the second table would mean some overhead. I'm currently using this method, with 1 bit per 4 entries. Whether the extra table implies overhead or underhead is hard to tell, since it depends on an awful lot of things (CPU, RAM, cache, OS). Remember the latency thread from a couple of weeks ago? :-) It seems impossible to model the behaviour of random access, except that on average bigger means slower. But then again, The King is a slow searcher. TT related latencies take up less than 0.02 of run time. So I don't care too much really. ... Johan
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.