Need helps with left-shift for combining integers

[phhnguyen]

For my draughts library, I have written a general C++ class template int_set<N> that is very similar to the C++ std::bitset<N> class template, except that it uses set-like naming of member functions (insert, erase, find; instead of set, reset, test) and that it has a for_each member function that allows efficient loops over all 1 bits using CPU intrinsics to scan for bits. You can also easily initialize it using struct like syntax with the squares that are occupied.

Your shift-code is almost identical to what I use, except that my code works for arbitrary arrays of bitboards (with only a special case for 1 bitboard). This code is also almost identical to what gcc uses for it's std:;bitset<N> class template. I have tested this using the same unit tests that Boost uses for dynamic_bitset.

Thanks Rein Halbersma, I have a look into your shift code. You make me feel a bit more confident about my code

[Gerd Isenberg]

I would go with 2x64-bits.

Further, I would implement the shift functions with integer template parameter of shift amount, so that there are known at compile time, and the compiler can eliminate conditional code for 1,7,8,9,10,11 ... and multiples ...

// 128-bit rdx:rax shl 11
shld rdx, rax, 11
shl rax, 11

// 128-bit rdx:rax shl 66
mov rdx, rax
xor rax, rax
shl rdx, 2

[Rein Halbersma]

I would go with 2x64-bits.

Further, I would implement the shift functions with integer template parameter of shift amount, so that there are known at compile time, and the compiler can eliminate conditional code for 1,7,8,9,10,11 ... and multiples ...

// 128-bit rdx:rax shl 11
shld rdx, rax, 11
shl rax, 11

// 128-bit rdx:rax shl 66
mov rdx, rax
xor rax, rax
shl rdx, 2

Gerd, would you have a table for all possible shift lengths? Or only for the shifts that can occur during the particular game & board layout?

[Gerd Isenberg]

I would go with 2x64-bits.

Further, I would implement the shift functions with integer template parameter of shift amount, so that there are known at compile time, and the compiler can eliminate conditional code for 1,7,8,9,10,11 ... and multiples ...

// 128-bit rdx:rax shl 11
shld rdx, rax, 11
shl rax, 11

// 128-bit rdx:rax shl 66
mov rdx, rax
xor rax, rax
shl rdx, 2

Gerd, would you have a table for all possible shift lengths? Or only for the shifts that can occur during the particular game & board layout?

You call the generic C++11 template function with a constant expression or a template paramter of a caller template function, which is called with some constants as well. Finally, for each occuring constant, your usual shift code is instantiated for special cases, should be inlined and optimized by the compiler for that particular constant, hopefully for 2x64 bit yielding in some x86-64 assembly given above .. so even if you have 128 left or right shifts, the code expansion is rather negligible for shifts.

i.e. template<int n> auto& operator<<=() as usual

[Rein Halbersma]

My experience is that calling a function with a constexpr argument / literal number will generally lead to constant propagation within that function. On -O3 things usually simplify automatically. Making the shift a template paramter is a nice idea however, especially witn the c++17 if constexpr extension!

[Gerd Isenberg]

My experience is that calling a function with a constexpr argument / literal number will generally lead to constant propagation within that function. On -O3 things usually simplify automatically. Making the shift a template paramter is a nice idea however, especially witn the c++17 if constexpr extension!

Not sure what __shiftleft128 generates with const shift amount, which however is modulo 64 - I guess it wraps a shld shl pair, hopefully with immediate parameter instead of cl if passing const:
https://msdn.microsoft.com/en-us/library/szzkhewe.aspx

Edit: __shiftleft128 only returns the high 64-bit word, so it only wraps shld.

Code: Select all

bb128[1] = __shiftleft128(bb128[0], bb128[1], 11);
bb128[0] <<= 11;

[hgm]

Does anyone have same experience?

That is also my experience. For perft mailbox is much faster than bitboard. Some eval terms, like detectig passed Pawns in Chess, can be done much faster with bitboards, though. (But you won't notice that in the overall speed when you use Pawn hash.)