Author: Stuart Cracraft
Date: 13:43:18 09/16/04
Go up one level in this thread
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
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.