Author: Vincent Diepeveen
Date: 11:30:40 09/15/01
Go up one level in this thread
On September 15, 2001 at 11:14:36, Sune Fischer wrote:
>Hi
>
>When I discovered that Crafty had some neat assembler rutines, I decided to test
>if they where faster than my humble rutines.
>I have up until now used a "raytracing" or boardtracing rutine to find the legal
>moves for the sliding pieces. And for the knights, pawns and king I simply check
>if the board has an allied piece on that square.
>It's a simple way of generating the legal moves.
>I still generate the attack bitboards to get the legal king moves though.
>
>I then tried to find all the moves directly from the bitboards by using one of
>Crafty's assember functions.
>This part of my program is only a minor part, but none the less it runs a full 8
>percent slower than my previous raytracing algorithm!!
>
>This is what I have now:
>
>void FindMovesQueen(..loads of pointers...)
>{
> int to_square;
> BITBOARD bb=(~allied.occupied) & allied.attack[board.id[from_square]];
>
> while (bb)
> {
> to_square=63-FirstOne(bb); // get a bit
the slow part is of course the 'firstone' function, though
it appears there is a trick on the K7 to speed it up quite a
bit in assembly. Nevertheless all the 64 bits overhead in total
slow down the thing.
> bb ^= mask[to_square]; // remove the bit
>
> movelist[++counter].from=from_square;
> movelist[counter].to=to_square;
> movelist[counter].piece=QUEEN;
> movelist[counter].capturedpiece=enemy.piece[board.id[to_square]];
this looks ugly. Using a pointer here would be way faster.
> }
> return;
>}
>
>(movelist, counter, from_square etc. are passed in the argument)
>
>I know why it is slow too.
>First I have to form the bb, that's 2 bitboard operations.
>Then I need to run an algorithm, FirstOne from crafty, to find the first bit.
>Then I need to mask out that found bit.
>Both of these run several time pending on the while loop.
>Next is 4 lines I always have, no matter how I do it, so we can safely ignore
>those.
>The while loop is a conditional much like the if's I use when raytracing, so
>probably the if's and while almost cancel out.
>
>All in all I have added a lot of operations to my program, I am not surprized it
>is a lot slower. Given that the entire program suffer a slowdown by about 8.1
>percent, I estimate that this technique is more than twice as slow as the
>raytracing.
>The upside of things is that I reduce my code by about 1000 lines or so, but is
>this worth 8 percent in speed?
Why not speed it up a factor of 2 if not more (depending upon what
processor we talk about) and just get rid of all code and rewrite it
till you have about a line or 50 in total, including EP and castling?
that's always faster than 1000 lines of C++ code.
The problem of too big code is that when testing it a few million time
a second it might seem fast, but things change completely when they are
integral part of the program. After some years of programming your program
won't fit inside L1 cache anymore and then the suffering starts!
Note that the small trace cache size of the P4 gives thoughts on thinking
too here. With DIEP where the ENGINE part takes many hundreds of kilobytes
of codesize from the L1+L2 caches, i definitely always go for the smallest
code. Where smallest code is defined as:
min( (whitecode + blackcode) , (general code) )
Sometimes writing things general is taking up more code than tot total
of writing it for black & white out (certain eval patterns for example).
In case of move generation that isn't the case in DIEP, but the bitboard
code for example already has been written down out for every piece seperate.
Bitboards are a big disaster here IMHO.
>I know the use of 64 bit processors will give a nice boost to this method and I
>probably can't expect anything like that for my tracing function, but frankly
>I'm not sure it would be enough to catch up.
>
>Am I mistaken, are the big boys doing something else?
>Is there an even faster way?
>I need to know :D :D
>
>Thanks,
>Sune
This page took 0.02 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.