Author: Michael Henderson
Date: 14:58:32 09/16/04
Go up one level in this thread
On September 16, 2004 at 16:43:18, Stuart Cracraft wrote: >On September 16, 2004 at 16:00:30, Dann Corbit wrote: > >>On September 16, 2004 at 15:49:42, Stuart Cracraft wrote: >> >>>I am thinking of upgrading my mailbox-based move generator and incheck/attack >>>detector to 0x88 because with small pctwise increase in time my test results are >>>better. >>> >>>What kind of a speedup, holding all else the same, can I expect, or do the >>>modern larger cache like the P3 I use substantially lessen the improvement? >> >>It will depend on the implementation. Some of the fastest commercial engines >>are 0x88 (or variant) types. E.g. Chess Tiger is of that genre. > >I'm talking vanilla, i.e. compare > > if (board[H8+OFFSET] == OFFBOARD) <== mailbox > >vs. > > if (((H8+OFFSET) & 0x88))) <== 0x88 method > >We're trading a memory reference for an AND, right? >If memory items are pre-fetched in cache it becomes >a cache lookup vs. an in-register logical operation >for the basic off-board question. > >More importantly, for the attack / incheck detector, to see >if there is any point in checking for an attack from >a piece to a square (or enemy king), ignore if square not reachable >due to no ray between, based on auxillary table single lookup (not >available in mailbox so >=N ops) otherwise go to each square (comparable >to mailbox.) Looks like one could avoid N operations here since the >check along the ray can be completely avoided by prior knowledge. >One could do that with an auxillary array for mailbox as well. >I.e. RAYS[64][64] would say 1 if RAYS[a8][h1] is on same array. >Spin it differently with a varying value based on N/W/E/S direction >of array to know exactly which direction. > >Just looking for what others have found when they converted their >program from mailbox to 0x88. I can add the ray idea to my mailbox >version and it will probably result in a nice speedup as right now >I blindly go out from the square in question in all directions until >I hit a piece without checking whether the ray makes any sense >for the pieces involved. > >Having ray prior knowledge will skip all that. > >I guess I really want to eliminate the ray part from the original >question as I suspect it is the major gain of 0x88 over mailbox -- >but mailbox can get that same thing with ray lookup. It cannot get >the same thing as square & 0x88 telling whether off board instead >of a memory reference. > >So it really comes down to just the memory reference vs. cache compared >to a logical. I did a check in a simple test program and it is about >20% faster for the logical when varying across the entire board for >a million iterations. > >Thanks, > >Stuart When I used 0x88, scanning the board and looking up attack possibility was slower than doing kingsquare-out method. King-out method is fast because pawn/knight detection is easy and scanning for bishops/queens from a definite square not as much instructions as scanning the entire board. Piece list may be faster to use. Michael
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.