Author: Uri Blass
Date: 11:04:17 10/18/02
Go up one level in this thread
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
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.