Author: Vincent Diepeveen
Date: 10:54:50 10/18/02
Go up one level in this thread
On October 17, 2002 at 14:32:41, Uri Blass wrote: >On October 17, 2002 at 12:01:37, Vincent Diepeveen wrote: > >>On October 17, 2002 at 06:20:11, Uri Blass wrote: >> >>>Today my repetition detection is not done based on hash tables and I plan to do >>>it faster by hash tables. >> >>Why would this be faster, taking x86 cpu architecture into account? >> >> >>>After every makemove I calculate the new hash key for the hash tables >> >>You don't incrementally calculate the zobrist hashing yet by just >>xor-ing the pieces you moved to the hashkey? > >I incrementally calculates the zobrist key. excellent. >> >>>but I do not have an array of all the hash keys and I use a global varaible >>>__int64 zob to have the hash key. >> >>i'm using for the x86 architecture 2 x 'unsigned int' for the hashkey. >>The reason is that it was faster than a single 'unsigned _int64'. >> >>Compilers not so efficient yet, though intel c++ might be doing this >>more efficient than others :) >> >>>I plan to add an array zobkey[max_plies_of_game] for hash keys >>>My question is what is faster: >> >>>1)Doing all the calculation on zob and after finishing them to do >>>zobkey[hply]=zob; >> >>this is by far fastest of course. >> >>>2)Doing all the calculations on zobkey[hply] >> >>extra array references cause extra instructions such as >>indirect accessing the array by [EAX]. >> >>Way faster is all operations onto a single register. >> >>>I guess that I am going to choose 1 because it is more simple and I guess that >>>the difference in speed is less than 0.1% but I am interested to know what is >>>faster. >> >>Well it should take very little system time in total anyway, but >>working on 1 global variable is always faster than doing it by using >>arrays. > >I understood from Hyatt that it is better to use a local varaible and only after >I finish updating the hash key to give the number to array of global varaibles. that's a better idea than directly working with the arrays. you asked about 2 evils, so i gave the lesser evil :) see my other posting about diff between local and global. there is no real diff except if you already write in other cache lines. however this cpu architecture is from after Bob's time, so he doesn't know much about it. >> >>>Doing all the calculations on zobkey[hply] seems to have one less arithmetic >>>calculation but more array calls. >> >>Arithmetic is very cheap (exception: BSF and BSR vector instructions) >> >>In general you should assume in the future that processors (take the >>mckinley as example) will do more instructions in either a bundle or >>within a single clock. Memory will get slower. So instructions that >>act upon a single register will be very slow unless it is complex >>instructions like BSF. Even multiplying i am using scrupuleous above >>adding a single small local array! >> >>a hashtable is way slower because it eats more memory than a single >>array [hply]. That O(1) lookup is of course way slower than doing >>a lookup in that array with hashnumbers which is already inside >>perhaps even your L1 cache already. >> >>Also in order to get a hashtable correctly to work you need a linked >>list hashtable. At paper that sounds cool perhaps, but it is hell slow. > >I do not have a linked list in movei. you need one for a repetition hashtable or you will miss possible repetitions. >Uri
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.