Author: Tijs van Dam
Date: 03:11:27 02/04/00
Go up one level in this thread
On February 04, 2000 at 01:10:57, Michael Neish wrote: ... > >Well thanks to those who replied to my initial question. I can see >now that bitboards are still not universally acknowledged as "superior". >From what little experience I have, I think their performance depends >critically on the speed of the FirstOne() routine, or equivalent, for >extracting the most or least significant 1-bit. In my case I do this: > >int GetBits(BITBOARD a) > >{ > >/* > test is a Bitboard of value 0xFFFFFFFF00000000 which allows half of > Bitboard a to be tested. If there are no 1's in that half, a is > shifted 32 bits and tested again. >*/ > > if (a & test) return(63 - __cntlzw((a>>32))); > else return (31 - __cntlzw(a)); > >} > >If anyone has a suggestion that would work faster, I would appreciate it if you >could let me know. There is no intrinsic function on the Mac (as far as I know) >which will allow trailing bits to be counted, hence I count the leading zeroes >and subtract the value of _cntlzw from 63 or 31. Obviously this slows the >routine down quite a bit. And also, _cntlzw cannot be applied directly to >unsigned long long integers, hence the split. > >Interesting discussion. Obviously I was naive to expect my program to run like >a cheetah after putting Bitboards in. Looks like it's going to be a struggle. > >Cheers, > >Mike. Clearly you have a 32 bit machine. You may speed up more if you treat the 64 bits as two words of 32 bits. This way, you directly access the 32 bits of the bitboard, avoiding the 64 bits AND and shift. Try this: int GetLeftBit(BITBOARD a) { union { unsigned int lower; unsigned int upper; /* might want to swap this, i don't know macs */ } *b; b=&a; // now, treat a as two ints if(b->upper)return (63-__cntlzw(b->upper)); else return(32-__cntlzw(b->lower)); } A good optimizing compiler will skip the assignment of b, but otherwise you could write something like ((unsigned *)(&a))[0] for the lower 32 bits and ((unsigned *)(&a))[1] for the upper part. Yesterday I implemented bitboard routines with assembly. That sped it up another 5-10%! Another tip: download Crafty source, I believe there are some MAC routines in it.
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.