Author: Vincent Diepeveen
Date: 09:01:37 10/17/02
Go up one level in this thread
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? >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. >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. >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.