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