Help on optimizing

[ericlangedijk]

First I'm going to try and optimize the movegenerator which takes most of the time.
It's in delphi and written for win32.
Is this a reasonably fast way to do the BSF?

Code: Select all

function BSF(var Bitboard: TBitboard; var Q: Byte): Boolean;
// eax --> BitBoard
// edx --> Q
// result --> eax
asm
  bsf ecx, [eax]
  jz @scanhi
  btc [eax], ecx
  jmp @found
  @scanhi:
  bsf ecx, [eax+4]
  jz @notfound
  btc [eax+4], ecx
  add ecx, 32
  @found:
    mov [Q], cl        // assign Q = mov[edx], cl
    mov al, 1          // return true
    jmp @exit          // ret
  @notfound:
    xor al, al         // return false
  @Exit:
end;


  PieceBitBoard := PieceBitBoards[WhiteBishop];
  while BSF(PieceBitBoard, Q) do
  begin
    MoveBitBoard := GetBishopAttacks(Q) and not ColorBitBoards[cWhite];
    while BSF(MoveBitBoard, T) do
      aMoves.Add(WhiteBishop, Q, T, BoardArray[T]);
  end;

[Gerd Isenberg]

First I'm going to try and optimize the movegenerator which takes most of the time.
It's in delphi and written for win32.
Is this a reasonably fast way to do the BSF?

On most (all?) x86 processors btc via indirect memory operand might be a bottleneck, since it is able to work on vectors with indices far greater 31, it has (much) worse latency even for indices <= 31. May be better to spend an extra register for the bsf-btc pair. I suggest to use a precondition and bsf without reset and notfound always called with none empty bitboards, otherwise likely the same condition is asked twice, inside and outside BSF. Instead of btc or btr, X "and" (X-1) might be faster (but does not work for bsr instead of bsf).

Code: Select all

function bsf(var Bitboard: TBitboard): Integer;
// eax --> BitBoard
// result --> eax
asm
  bsf ecx, [eax]
  jnz @found
  @scanhi:
  bsf ecx, [eax+4]
  add ecx, 32
  @found:
    mov eax, ecx
  @Exit:
end; 


  PieceBitBoard := PieceBitBoards[WhiteBishop];
  while ( PieceBitBoard != 0 ) do
  begin
    Q := bsf ( PieceBitBoard );
    MoveBitBoard := GetBishopAttacks(Q) and not ColorBitBoards[cWhite];
    while ( MoveBitBoard != 0 ) do
    begin
      T := bsf ( MoveBitBoard );
      aMoves.Add(WhiteBishop, Q, T, BoardArray[T]);
      MoveBitBoard := MoveBitBoard and (MoveBitBoard - 1);
    end;
    PieceBitBoard := PieceBitBoard and (PieceBitBoard - 1);
  end;