C vs ASM

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Rein Halbersma
Posts: 749
Joined: Tue May 22, 2007 11:13 am

Re: C vs ASM

Post by Rein Halbersma »

C++11 style iteration over raw 64-bit integers (i.e. not wrapped inside a class)

Code: Select all

#include <cstddef>
#include <cstdint>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <ios>
 
template<typename> class bit_iterator;
template<typename> class bit_reference;
 
template<typename T>
std::size_t safe_ctzll(T mask)
{
     return mask? __builtin_ctzll(mask) : (8 * sizeof(T));
}
 
template<typename T>
class bit_iterator
:
    public std::iterator<
        std::input_iterator_tag,
        std::size_t, std::ptrdiff_t,
        bit_iterator<T>, bit_reference<T>
    >
{
public:
     bit_iterator(): mask_(0) {}
     bit_iterator(T const& m): mask_(m) {}
     bit_reference<T> operator*() const { return bit_reference<T>(mask_); }
     bit_iterator& operator++() { mask_ &= mask_ - 1; return *this; }
     bit_iterator operator++(int) { auto old = *this; ++*this; return old; }
 
     friend bool operator==(bit_iterator const& lhs, bit_iterator const& rhs)
     { return lhs.mask_ == rhs.mask_; }
     friend bool operator!=(bit_iterator const& lhs, bit_iterator const& rhs)
     { return !(lhs == rhs); }
private:
     T mask_;
};
 
template<typename T>
class bit_reference
{
public:
        bit_reference(T const& m): mask_(m) {}
        bit_reference& operator=(bit_reference const&) = delete;
        operator std::size_t() const { return safe_ctzll(mask_); }
        bit_iterator<T> operator&() const { return bit_iterator<T>(mask_); }
private:
        T mask_;
};
 
typedef uint64_t BitBoard;
 
namespace std {
bit_iterator<BitBoard> begin(BitBoard& b) { return bit_iterator<BitBoard>(b); }
bit_iterator<BitBoard> end(BitBoard& b) { return bit_iterator<BitBoard>(BitBoard(0)); }
} 
 
int main()
{
    BitBoard b = 0x022fdd63cc95386dULL;
    for (auto i: b) std::cout << i << " "; std::cout << "\n";
    std::cout << std::boolalpha << std::is_sorted(std::begin(b), std::end(b)) << "\n";
}
Online output from g++ 4.7.2 at http://ideone.com/xp0kpW
OneTrickPony
Posts: 157
Joined: Tue Apr 30, 2013 1:29 am

Re: C vs ASM

Post by OneTrickPony »

On my i7:

asm version by 32bit Visual studio: 18577ms
normal version by 32bit VS: 12518ms
normal by 64bit VS compiler: 12515ms
GCC 4.8 normal (asm doesn't compile): 12464ms
Unoptimized version by VS run 42273ms

(-Ox with VS, O3 with GCC)

This is first time ever I see GCC outperforming VS on Windows :)
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: C vs ASM

Post by lucasart »

Rein Halbersma wrote:C++11 style iteration over raw 64-bit integers (i.e. not wrapped inside a class)

Code: Select all

#include <cstddef>
#include <cstdint>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <ios>
 
template<typename> class bit_iterator;
template<typename> class bit_reference;
 
template<typename T>
std::size_t safe_ctzll(T mask)
{
     return mask? __builtin_ctzll(mask) : (8 * sizeof(T));
}
 
template<typename T>
class bit_iterator
:
    public std::iterator<
        std::input_iterator_tag,
        std::size_t, std::ptrdiff_t,
        bit_iterator<T>, bit_reference<T>
    >
{
public:
     bit_iterator(): mask_(0) {}
     bit_iterator(T const& m): mask_(m) {}
     bit_reference<T> operator*() const { return bit_reference<T>(mask_); }
     bit_iterator& operator++() { mask_ &= mask_ - 1; return *this; }
     bit_iterator operator++(int) { auto old = *this; ++*this; return old; }
 
     friend bool operator==(bit_iterator const& lhs, bit_iterator const& rhs)
     { return lhs.mask_ == rhs.mask_; }
     friend bool operator!=(bit_iterator const& lhs, bit_iterator const& rhs)
     { return !(lhs == rhs); }
private:
     T mask_;
};
 
template<typename T>
class bit_reference
{
public:
        bit_reference(T const& m): mask_(m) {}
        bit_reference& operator=(bit_reference const&) = delete;
        operator std::size_t() const { return safe_ctzll(mask_); }
        bit_iterator<T> operator&() const { return bit_iterator<T>(mask_); }
private:
        T mask_;
};
 
typedef uint64_t BitBoard;
 
namespace std {
bit_iterator<BitBoard> begin(BitBoard& b) { return bit_iterator<BitBoard>(b); }
bit_iterator<BitBoard> end(BitBoard& b) { return bit_iterator<BitBoard>(BitBoard(0)); }
} 
 
int main()
{
    BitBoard b = 0x022fdd63cc95386dULL;
    for (auto i: b) std::cout << i << " "; std::cout << "\n";
    std::cout << std::boolalpha << std::is_sorted(std::begin(b), std::end(b)) << "\n";
}
Online output from g++ 4.7.2 at http://ideone.com/xp0kpW
All that for what ? if I include this file into my source code, what it the *practical* benefit ? Write for (auto i: b) {...} instead of while (b) { sq = pop_lsb(&b); ... } ? Now what is the type of i ? Is it an int ? Can it be converted implicitely to an int (or unsigned) ? Or will I get insulted by our friend the C++ compiler every time I use it ? Why would I want to include a ton of useless "no-op code" in my source, that is truly obfuscated ? Bjarn often says: in C++ what you don't use you don't pay for. Nothing could be further from the truth, as any experienced programmer knows already (remember the first time you have to figure out an error message happenning inside an STL file...?)
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
Rein Halbersma
Posts: 749
Joined: Tue May 22, 2007 11:13 am

Re: C vs ASM

Post by Rein Halbersma »

lucasart wrote:
Rein Halbersma wrote:C++11 style iteration over raw 64-bit integers (i.e. not wrapped inside a class)

Code: Select all

int main()
{
    BitBoard board = 0x022fdd63cc95386dULL;
    for (auto square: board) std::cout << square << " "; std::cout << "\n";
    std::cout << std::boolalpha << std::is_sorted(std::begin(board), std::end(board)) << "\n";
}
Online output from g++ 4.7.2 at http://ideone.com/xp0kpW
All that for what ? if I include this file into my source code, what it the *practical* benefit ? Write for (auto i: b) {...} instead of while (b) { sq = pop_lsb(&b); ... } ? Now what is the type of i ? Is it an int ? Can it be converted implicitely to an int (or unsigned) ? Or will I get insulted by our friend the C++ compiler every time I use it ? Why would I want to include a ton of useless "no-op code" in my source, that is truly obfuscated ? Bjarn often says: in C++ what you don't use you don't pay for. Nothing could be further from the truth, as any experienced programmer knows already (remember the first time you have to figure out an error message happenning inside an STL file...?)
The type of i is a bit_reference object, and it has indeed an implicit conversion operator to std::size_t, which is why the loop prints out all the 1-bit indices of the BitBoard b. You are right that I should have written it a bit clearer. In C you do that by explicitly using (builtin) types and short variable names. In C++11 the way to do that is to use the auto-keyword to hide type deduction and to use longer meaningful variable names for clarity, e.g. square and board instead of i and b. Since the compiler still checks the auto-type, it's perfectly type-safe.

The reason to write it like that is that Bitboard type is actually a packed implementation of the Standard Library's container std::set<unsigned>: a sorted collection of unique integers (the squares). The last line std::is_sorted(std::begin(b), std::end(b)) reveals that hidden invariant. I have also written some code that wraps a BitBoard inside a class bit_set, which adds the `std::set` member functions find() / insert() / erase() / size() to it so that you can also set / clear individual bits and use popcount on it.

It simply raises the level of abstraction compared to manipulating raw 64-bit integers. You can call my code obfuscation, but any high-level code hides low-level details. It's in fact the other way around, your raw pop_lsb is just one step above ASM, and it's not even remotely familiar to any other data manipulation. Now that is what I call obfuscation. THe fact that chess programmers have been exposed to this for 30 years does not make it accesible to any other type of programmers.

Using iterator and container syntax is just damn convenient. It allows e.g. initialization of bitboards with array syntax like bit_set white_pawns { a2, b2, c2, d2, e2, f2, g2, h2 }; and copying bit_sets to any other STL container. Go ahead and try writing that by hand, it'll be much more verbose than using a 60-line header that efficiently implements that for you.
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: C vs ASM

Post by lucasart »

Rein Halbersma wrote: Using iterator and container syntax is just damn convenient. It allows e.g. initialization of bitboards with array syntax like bit_set white_pawns { a2, b2, c2, d2, e2, f2, g2, h2 }; and copying bit_sets to any other STL container. Go ahead and try writing that by hand, it'll be much more verbose than using a 60-line header that efficiently implements that for you.
Now you have a point. Real practical use case, rather than theoretical masutrbation. It would be nice indeed to have an assignment to an array of squares. But I'm going to be the devil's advicate and tell you that in can do it in plain C with a variable argument list function. Although it involves run-time cost, so it's only OK if not done in critical execution path (like once at startup when precalculating bitboards for example). Or else, simply:
Bitboard b = (1ULL << A2) | (1ULL << B2) ... | (1ULL << H2);
Or even more simply
Bitboard b = 0xFF00ULL;
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
mar
Posts: 2596
Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: C vs ASM

Post by mar »

Rein Halbersma wrote:C++11 style iteration over raw 64-bit integers (i.e. not wrapped inside a class)

Code: Select all

return mask? __builtin_ctzll(mask) : (8 * sizeof(T));
Nice code, Rein.
May I ask why you do a zero test each time you dereference the iterator? It shouldn't be necessary at all since end() wraps zero bitboard anyway. Perhaps an assert would do?
Also, builtins are nice and handy but you can only use them when compiling with gcc/clang (ok not a problem because other compilers don't fully support C++11).
Either way, I'm staying with my old low level code which works everywhere.
mar
Posts: 2596
Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: C vs ASM

Post by mar »

Rein Halbersma wrote:

Code: Select all

     friend bool operator==(bit_iterator const& lhs, bit_iterator const& rhs)
     { return lhs.mask_ == rhs.mask_; }
Why not

Code: Select all

bool operator==( bit_iterator const& rhs) const
     { return mask_ == rhs.mask_; } 
Rein Halbersma
Posts: 749
Joined: Tue May 22, 2007 11:13 am

Re: C vs ASM

Post by Rein Halbersma »

mar wrote:
Rein Halbersma wrote:C++11 style iteration over raw 64-bit integers (i.e. not wrapped inside a class)

Code: Select all

return mask? __builtin_ctzll(mask) : (8 * sizeof(T));
Nice code, Rein.
May I ask why you do a zero test each time you dereference the iterator? It shouldn't be necessary at all since end() wraps zero bitboard anyway. Perhaps an assert would do?
Also, builtins are nice and handy but you can only use them when compiling with gcc/clang (ok not a problem because other compilers don't fully support C++11).
Either way, I'm staying with my old low level code which works everywhere.
http://gcc.gnu.org/onlinedocs/gcc-4.4.5 ... ltins.html
"Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined."

On Ideone, leaving the test out doesn't change the output, but it's not safe in general.
Rein Halbersma
Posts: 749
Joined: Tue May 22, 2007 11:13 am

Re: C vs ASM

Post by Rein Halbersma »

mar wrote:
Rein Halbersma wrote:

Code: Select all

     friend bool operator==(bit_iterator const& lhs, bit_iterator const& rhs)
     { return lhs.mask_ == rhs.mask_; }
Why not

Code: Select all

bool operator==( bit_iterator const& rhs) const
     { return mask_ == rhs.mask_; } 
Because operator== has symmetric semantics, and the friend function is guaranteed to play nice with it. Member functions introduce asymmetry between the implicit left-argument (the this pointer) and the explicit right argument, e.g. during name lookup and type conversions, and I don't want to think about it whether that applies here. :) I use a strict convention when I overload operators: symmetric ones (+, *, &, |) are defined as nonmember functions, perferably interms of the asymmetric member functions (+=, *=, &=, |= etc.), and as friend functions otherwise.
Rein Halbersma
Posts: 749
Joined: Tue May 22, 2007 11:13 am

Re: C vs ASM

Post by Rein Halbersma »

Rein Halbersma wrote: http://gcc.gnu.org/onlinedocs/gcc-4.4.5 ... ltins.html
"Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined."

On Ideone, leaving the test out doesn't change the output, but it's not safe in general.
Hmm on second thought, it's the job of outside caller to make sure that only valid iterators are being derefencered, so I believe you are right that this test can be eliminated. (the same applies to e.g. linked list iterators: inside operator++ there is a node = node->next; without a check for nullptr). Thanks Martin, for making me think harder!