Bitboard data structure

[Hamfer]

1/
Consider the folowing date structure :
typedef struct {
uint64_t w_bitboard[6];
uint64_t b_bitboard[6];
...
} BB;
With
- w_bitboard[1] for white pawn bitboard
- w_bitboard[2] for white knight bitboard
- w_bitboard[3] for white bishop bitboard
- w_bitboard[4] for white rook bitboard
- w_bitboard[5] for white queen bitboard
- w_bitboard[6] for white king bitboard
- and the same for black

2/
and this one
typedef struct {
uint64_t w_pawn;
uint64_t w_knight;
uint64_t w_bishop;
uint64_t w_rook;
uint64_t w_queen;
uint64_t w_king;
...
} BB;

What is the better data structure for performance?

[Richard Vida]

What is the better data structure for performance?

Performance-wise they are equivalent. For convenience IMO it is best to use an union of both.

[CDaley11]

I also wonder if using the corresponding "fast" integer types would boost performance?

[lucasart]

What is the better data structure for performance?

I don't like ANY of them. IMO this is much better:

Code: Select all

uint64_t b[NB_COLOR][NB_PIECE];

You can use b[WHITE][KNIGHT] for instance. The whole point is that you can write generic code without having to treat white and black differently every time. Duplicating code is a hugh source of bugs...

As for performance none of them is either faster or slower. Yours are just more error prone, and force you to duplicate a lot of code. Whether you write

Code: Select all

w_knight
w_pieces[Knight]
b[White][Knight]

the compiler knows the adress of that variable, and no more or less computation is done at runtime.

[User923005]

Speaking of performance:
1. First make it correct.
2. Then make it fast.

Don't try to out-think the compiler unless you have some incredible and certain reason for doing that.

To accomplish step 2, profile your application.
When you find out where the slow spots are, use a better algorithm in those places.
If you cannot find a better algorithm, invent one.
If you cannot invent one, then it is time to try tweaky things.
Tweaky things like inline assembly will never give more than a constant speedup anyway.
It's O(f(N)) changes that will make your program a lot better.

IMO-YMMV.

[Hamfer]

lucasart, for you time-acces is the same for array of 1-dimension, array of 2-dimension and direct variable.

But, I think that using variable KNIGHT_white is faster than b_white[KNIGHT] and b[WHITE][KNIGHT].

[lucasart]

lucasart, for you time-acces is the same for array of 1-dimension, array of 2-dimension and direct variable.

But, I think that using variable KNIGHT_white is faster than b_white[KNIGHT] and b[WHITE][KNIGHT].

There is no performance difference. As I explained the offset is computed at compile time, when you write b[White][Knight], it is equivalent to writing *(b+6*White+Knight), and as b (adress) is a known offset at compile time, there is no computation done and the quantity (pointer) b+6*White+Knight is hardcoded into the executable.

But you're focusing on what is irrelevant. What is far more relevant is:
- avoid bugs, and duplicating your code everywhere is certainty of bugs
- shorter code is faster, because access to the general memory is much slower than the CPU cache, so with bloated code you slow down your program considerably due to cache misses

You should consider the union solution proposed by Richard, which is the smartest I think (you can the three solutions and make them coexist with union, if you really want to, but if you should choose only one b[color][piece] is best IMO).

[User923005]

I like the solution of lucasrt because it is the most clear.
Premature optimization is almost always a mistake.
I guess that there is almost zero chance that choosing something less clear will make a measurable improvement in Elo performance.
On the other hand, having a clear and understandable board representation will make the rest of the program more clear and understandable.
I think that some underlying data structure choices are important (e.g. bitboards give 64 bit CPU/OS systems a small advantage)
But esoteric choices that make the code less clear in an attempt to outguess the compiler are a bad idea.

IMO-YMMV

[Gerd Isenberg]

The issue with a structure of elements of the same type versus an array is to index the array by variables, i.e. in move generation by side to move and piece type, or one-dimensional with piece-index including both color and type, to utilize the array in a branchless way. See f.i. Beowulf with switch/case to conditionally access struct elements for a counter approach. Lucas' approach is perfectly ok. Another common approach is to use the denser

Code: Select all

U64 pieceBB[8];

with two color and six piece-type bitboards. For the union of struct and array - one should ovoid that IMO. There might be portability and alias issues.