Speedup with bitboards on 64-bit CPUs

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Speedup with bitboards on 64-bit CPUs

Post by Tord Romstad » Fri Apr 27, 2007 8:39 am

I've been using bitboards for a while, and I am somewhat disappointed with the performance. On my 32-bit Core Duo, they are about 20-30% slower than my old mailbox board, it is therefore tempting to revert to the old board representation. Before I do so, I would like to know: How much of a speedup do bitboard programs usually see when running on a 64-bit CPU? Can I expect bitboards to be competitive with a mailbox board for my program if I upgrade to the 64-bit Core 2 Duo?

Tord

mjlef
Posts: 1420
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Speedup with bitboards on 64-bit CPUs

Post by mjlef » Fri Apr 27, 2007 9:34 am

I think it has been reported here Rybka, which Vasik says uses bitboards, runs about 60% faster on a 64 bit processor. I think the speed difference will depend greatly on what is being represented with 64 bit values.

Lately, I have kept my mailbox move generation, but use some incrementally update bitboards too. In this hybrid approach, pawn attacks, knight attacks and king attacks can easily be update with a could of simple XORs. I have a bit for each pawn position, so detection of isolated and passed pawns is very fast (not much faster than the older array poitning to the least advanced pawn on each file though). I then OR in other attacks for sweep pieces for mobility/space control and so on. Of course my program is very slow anyway.

Mark

User avatar
hgm
Posts: 23479
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Speedup with bitboards on 64-bit CPUs

Post by hgm » Fri Apr 27, 2007 10:20 am

I would not expect any speedup from bitboards compaired to mailbox, even in 64-bit mode, if you jsut use them to replace the move generator. For bulk move generation bitboards cannot beat mailbox. They are very much faster than mailbox for generating moves selectively (e.g. only captures, only checks), though. But if your program should be doing that a lot in order to see any benefits.

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Speedup with bitboards on 64-bit CPUs

Post by Tord Romstad » Fri Apr 27, 2007 11:04 am

mjlef wrote:I think it has been reported here Rybka, which Vasik says uses bitboards, runs about 60% faster on a 64 bit processor. I think the speed difference will depend greatly on what is being represented with 64 bit values.
60% is a lot, but of course we don't know exactly what Rybka is doing. Does anyone have any numbers for Crafty, SmarThink or other bitboard engines?
Lately, I have kept my mailbox move generation, but use some incrementally update bitboards too. In this hybrid approach, pawn attacks, knight attacks and king attacks can easily be update with a could of simple XORs. I have a bit for each pawn position, so detection of isolated and passed pawns is very fast (not much faster than the older array poitning to the least advanced pawn on each file though). I then OR in other attacks for sweep pieces for mobility/space control and so on. Of course my program is very slow anyway.
So is mine. My program with a material only eval is slower than Crafty with a full eval.

Tord

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Speedup with bitboards on 64-bit CPUs

Post by Tord Romstad » Fri Apr 27, 2007 11:13 am

hgm wrote:I would not expect any speedup from bitboards compaired to mailbox, even in 64-bit mode, if you jsut use them to replace the move generator. For bulk move generation bitboards cannot beat mailbox. They are very much faster than mailbox for generating moves selectively (e.g. only captures, only checks), though. But if your program should be doing that a lot in order to see any benefits.
I do generate moves incrementally with bitboards, and have separate move generation functions for captures, checks, non-captures and check evasions. But move generation doesn't consume a significant fraction of the CPU time in my program in any case, neither with bitboards nor with mailbox. The places where bitboards seem to be significantly slower are king safety evaluation, scanning for attacks in a single direction, and making and unmaking moves.

Tord

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Speedup with bitboards on 64-bit CPUs

Post by Pradu » Fri Apr 27, 2007 11:15 am

Tord Romstad wrote:
mjlef wrote:I think it has been reported here Rybka, which Vasik says uses bitboards, runs about 60% faster on a 64 bit processor. I think the speed difference will depend greatly on what is being represented with 64 bit values.
60% is a lot, but of course we don't know exactly what Rybka is doing. Does anyone have any numbers for Crafty, SmarThink or other bitboard engines?
Lately, I have kept my mailbox move generation, but use some incrementally update bitboards too. In this hybrid approach, pawn attacks, knight attacks and king attacks can easily be update with a could of simple XORs. I have a bit for each pawn position, so detection of isolated and passed pawns is very fast (not much faster than the older array poitning to the least advanced pawn on each file though). I then OR in other attacks for sweep pieces for mobility/space control and so on. Of course my program is very slow anyway.
So is mine. My program with a material only eval is slower than Crafty with a full eval.

Tord
I get 2.2x speedup for Buzz from 32-bits to 64-bits on Core2. There's an open-source version of my program so you can see exactly what I'm doing.

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Speedup with bitboards on 64-bit CPUs

Post by Pradu » Fri Apr 27, 2007 11:18 am

Tord Romstad wrote:
hgm wrote:I would not expect any speedup from bitboards compaired to mailbox, even in 64-bit mode, if you jsut use them to replace the move generator. For bulk move generation bitboards cannot beat mailbox. They are very much faster than mailbox for generating moves selectively (e.g. only captures, only checks), though. But if your program should be doing that a lot in order to see any benefits.
I do generate moves incrementally with bitboards, and have separate move generation functions for captures, checks, non-captures and check evasions. But move generation doesn't consume a significant fraction of the CPU time in my program in any case, neither with bitboards nor with mailbox. The places where bitboards seem to be significantly slower are king safety evaluation, scanning for attacks in a single direction, and making and unmaking moves.

Tord
Making and unmaking moves is slow for bitboard regardless. But perhaps you can optimize your kingsafety code with either flood-filling or specialized magic routines and have it be significantly faster than mailbox for this. I haven't looked into Glaurung to see how you do kingsafety but I suppose it is the usual way of counting the number/type of attackers to squares around the king. It is quite strange scanning for attacks in a single direction is faster for you, do you have a SEE to bench for mailbox and bitboards?

CRoberson
Posts: 1989
Joined: Mon Mar 13, 2006 1:31 am
Location: North Carolina, USA
Contact:

Re: Speedup with bitboards on 64-bit CPUs

Post by CRoberson » Fri Apr 27, 2007 1:45 pm

Telepath (bitboard) is slower than NoonianChess in NPS by about 2x using a 32 bit complier (g++) for both on a Core2Duo and an AMD 4400+.
Both machines using a 32 bit version of windows.

When I went to the newer version of MSVC, Telepath gained a 33% speedup and it still was a 32 bit compile running on a 32 bit OS.

When I recompiled Telepath with g++ (64 bit version) and ran on the AMD with a 64 bit version of Linux, Telepath was 20% faster than NoonianChess was.

Telepath is bitboard (nonrotated) and NoonianChess uses a 64 element array and two piecelists.

jdart
Posts: 3804
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Speedup with bitboards on 64-bit CPUs

Post by jdart » Fri Apr 27, 2007 6:25 pm

Arasan uses bitboards extensively (including rotated). The 64-bit version is faster but not by much (10-25%). I am not sure why.

--Jon

Michael Sherwin
Posts: 3040
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Speedup with bitboards on 64-bit CPUs

Post by Michael Sherwin » Fri Apr 27, 2007 11:32 pm

jdart wrote:Arasan uses bitboards extensively (including rotated). The 64-bit version is faster but not by much (10-25%). I am not sure why.

--Jon
Rotated bitboards use lots and lots of multidimentional look-ups which is great for 32 bit processors, because it keeps 64 bit access to a minimum. However, when compiled for 64 bits all the same array indexing must be done and 64 bit access is still minimized. There are other bitboard methods that minimize look-ups and maximize 64 operations that run much faster on 64 bit processors when compiled to 64 bit code.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Post Reply