Author: Vincent Diepeveen
Date: 11:31:30 10/18/02
Go up one level in this thread
On October 18, 2002 at 14:04:17, Uri Blass wrote: >On October 18, 2002 at 13:54:50, Vincent Diepeveen wrote: > >>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. > >In the last version I have an array of all the 64 bit hash keys. > >I assume that games are not of more than 1000 plies so the array is of 1000 >entries. >I also use an array of 1000 entries to remember all the moves of the game. > >Movei already had a game that could be more than 600 plies but I never had games >of more than 1000 plies. > >The longest game of it is a draw against Ant that was adjudicated by Leo after >297 moves(almost 600 plies) in a drawn KRR vs KRB position. > >Uri 2048 ply in diep it is. of course vaste majority of games it doesn't even get filled for 5% of that :)
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.