How beautiful is your code?

[Gusev]

How can a general purpose bitset template library do the >> and << efficiently ? (these operations don't make any sense from a set point of view)

Yet they are supported, http://www.cplusplus.com/reference/bits ... operators/

Code: Select all

** bitset member functions: ***
bitset<N>& operator&= &#40;const bitset<N>& rhs&#41;;
bitset<N>& operator|= &#40;const bitset<N>& rhs&#41;;
bitset<N>& operator^= &#40;const bitset<N>& rhs&#41;;
bitset<N>& operator<<= &#40;size_t pos&#41;;
bitset<N>& operator>>= &#40;size_t pos&#41;;
bitset<N> operator~() const;
bitset<N> operator<<&#40;size_t pos&#41; const;
bitset<N> operator>>&#40;size_t pos&#41; const;
bool operator== &#40;const bitset<N>& rhs&#41; const;
bool operator!= &#40;const bitset<N>& rhs&#41; const;

*** global functions&#58; ***
template<size_t N>
  bitset<N> operator& &#40;const bitset<N>& lhs, const bitset<N>& rhs&#41;;
template<size_t N>
  bitset<N> operator| &#40;const bitset<N>& lhs, const bitset<N>& rhs&#41;;
template<size_t N>
  bitset<N> operator^ &#40;const bitset<N>& lhs, const bitset<N>& rhs&#41;;

We can have the beauty, but we are at the mercy of the compiler developers. Still, I see no reason why they couldn't implement bitset efficiently if they wanted to.

[lucasart]

Still, I see no reason why they couldn't implement bitset efficiently if they wanted to.

I can see already one BIG reason. They define a bitset<size_t N>. The entire reason for using bitboards is that all is computed in 64-bit operations (using 64-bit registers etc.). If you make it generic (for any N), you necessarly lose all that.
Anyway, I am not sure, and I am not a C++ guru, but all I say is that it's better to check than to assume (perhaps there is a special definition of the templates in the case N=64?).
For example Marco Costalba is a C++ guru, and I'm sure he would use std::bitset if it was indeed efficient. If he doesn't, you can reasonably assume that there's a valid reason.

[Don]

In our little community, sources of engines like Fruit or Stockfish are often praised, the first one for its clarity, the second one for its mastering of all C++ tricks (something that, as a pascal programmer, I have to trust you for). But what is a beautiful code ?

I just read a very interesting article on the subject:
http://kotaku.com/5975610/the-exception ... t=56177550

So how beautiful is your code?

I don't believe there is such thing. Beautiful means nothing and it is in the eye of the beholder. Names that I think could be applied to compliment code are "straightforward", "readable", "efficient", "modular", "maintainable" etc., but beautiful is a silly name, the same thing happens when chefs praise food. The food could be "flavorful", "intense", "spicy" etc. but they use poetry instead.

For instance, a pascal programmer could see a goto and vomit. A C programmer could use it in a way that it very convenient to simplify the code and see it beautiful. I grew as a pascal programmer and I developed an aversion to gotos that I believed played against me when I started with C. Still today I do not use any, when my mind is telling me it could be better to do it in certain cases. I think we need to keep our minds open. setjmp longjmp is another case that some people have strong disagreements about it, when it comes to "beauty".

"Beautiful code is for hippies, who could only play frisbee" will say Eric Cartman

Miguel

I taught myself programming with basic for the TRS-80 and you had to use a lot of goto's. Then I learned pascal and read about structured programming and stopped using goto's completely. I was fanatical about not using them.

However, I eventually discovered that goto's still have their place and I could make the code a lot clearer in a few limited cases, but those cases could make a big difference in clarity. It is sometimes the difference between a single goto and a confusing mess of nested conditional statements just to avoid using one goto label.

As far as "beauty" is concerned, I don't write beautiful code and I don't see the point. That's for anal retentive sissies - the type that will argue for hours on end about indentation style on forums. I want my code to be bugfree and easy for ME to understand and I'm not trying to win a style contest.

[Rein Halbersma]

Code: Select all

#include <bitset>
typedef std&#58;&#58;bitset<NUM_SQUARES> Bitboard;

That's intersting. Is there really zero cost in using std::bitset<64> instead of using uint64_t ? I'm always very suspicious about these obfuscated template libraries, but perhaps I'm wrong.

In this other thread, I wrote about a class template wrapper around a 64-bit integer that allows STL style iteration (begin(), end(), ++, *, etc.). The assembly code has 0% overhead compared to raw 64-bit integer code.

The operations that are critical on a bitboard are:
- get/set/test the i-th bit. I already see that bitset::set() is a variable parameter function, so I'm more than worried about the performance compared to a simple b |= (1ULL << i);
- all bitwise operations (logical ones, but also shifts, and multiplication for magics). How can a general purpose bitset template library do the >> and << efficiently ? (these operations don't make any sense from a set point of view)

For almost every high-quality implementation of the STL, the general std::bitset<N> template is implemented in terms of a basic_bitset<Nwords, N> class template, where Nwords is the number of machine words that is used as the underlying raw data. Using partial template specialization, the case Nwords=1 is defined separately. In that case, all the get/set/test and <<, >> member functions are one-liners that are guaranteed to be inlined by any modern compiler. You should expect native performance for them. However, I don't know if every STL implementation has a specialization for 64-bit builds so that you get the same performance as for native 64-bit integers.

- lsb(), msb(), popcnt(): those must use portable assembly (compiler intrinsics) to achieve any decent performance. I really doubt that a general purpose STL could do that.

Has anyone used bitset in a chess engine, and looked into performance ?

The original SGI implementation (pre 1998) of the STL std::bitset had no compiler intrinsics but lookup tables for each byte. The modern gcc/libstdc++ and Clang/libc++ implementations use __builtin_ctzl / __builtin_popcountl and memset to get native performance for bit-twiddling.

The major inconvenience for std::bitset is that their are no iterators. The SGI and gcc implementations have non-standard find_first() and find_next() member functions (with intrinsic bitscan for gcc) that allow efficient looping over all 1-bits of a bitset. But for MSVC++ and Clang/libc++ you are out of luck. Even so, I think my class template wrapper with special iterators begin()/end() that can be passed to any non-modifying STL algorithm (std::copy, std::is_sorted, std::for_each etc.) allow you a real boost in convenience and abstraction with virtually no performance penalty.

[Rein Halbersma]

Still, I see no reason why they couldn't implement bitset efficiently if they wanted to.

I can see already one BIG reason. They define a bitset<size_t N>. The entire reason for using bitboards is that all is computed in 64-bit operations (using 64-bit registers etc.). If you make it generic (for any N), you necessarly lose all that.
Anyway, I am not sure, and I am not a C++ guru, but all I say is that it's better to check than to assume (perhaps there is a special definition of the templates in the case N=64?).
For example Marco Costalba is a C++ guru, and I'm sure he would use std::bitset if it was indeed efficient. If he doesn't, you can reasonably assume that there's a valid reason.

Partial specialization allows you to define different implementations depending on N. Every STL implementations I know of, has special code for bitsets fitting inside a single integer (not sure if they specialize for 64-bit as well). You are definitely right to always check your own STL vendor's code (and it's not too hard to read, once you get used to all the __ prefixed variable names).

One reason that std::bitset is not used a lot more in game programs is that efficient iteration over 1-bits is not mandated by the Standard, so you have to rely on vendor-specific extensions (such as the SGI/gcc find_first/find_next member functions), or you have to rely on your own wrappers that implement iterators.

[lucasart]

In this other thread, I wrote about a class template wrapper around a 64-bit integer that allows STL style iteration (begin(), end(), ++, *, etc.). The assembly code has 0% overhead compared to raw 64-bit integer code.

Thanks. I will have a look at your code. It will surely teach me some things about C++. But I still much prefer my C-style code as it is a *lot* shorter and simpler. The onle "bitboard library" functions I have are:

Code: Select all

inline void set_bit&#40;Bitboard *b, unsigned sq&#41;	&#123; assert&#40;square_ok&#40;sq&#41;); *b |= 1ULL << sq; &#125;
inline void clear_bit&#40;Bitboard *b, unsigned sq&#41;	&#123; assert&#40;square_ok&#40;sq&#41;); *b &= ~&#40;1ULL << sq&#41;; &#125;
inline bool test_bit&#40;Bitboard b, unsigned sq&#41;	&#123; assert&#40;square_ok&#40;sq&#41;); return b & &#40;1ULL << sq&#41;; &#125;
inline Bitboard shift_bit&#40;Bitboard b, int i&#41; &#123; assert&#40;abs&#40;i&#41; < 64&#41;; return i > 0 ? b << i &#58; b >> -i; &#125;
inline bool several_bits&#40;Bitboard b&#41; &#123; return b & &#40;b - 1&#41;; &#125;

inline int count_bit&#40;Bitboard b&#41; &#123; return __builtin_popcountll&#40;b&#41;; &#125;
inline int lsb&#40;Bitboard b&#41; &#123; assert&#40;b&#41;; return __builtin_ffsll&#40;b&#41; - 1; &#125;
inline int msb&#40;Bitboard b&#41; &#123; assert&#40;b&#41;; return 63 - __builtin_clzll&#40;b&#41;; &#125;

inline int pop_lsb&#40;Bitboard *b&#41;
&#123;
	const int s = lsb&#40;*b&#41;;
	*b &= *b - 1;
	return s;
&#125;

Regarding iterators, I'm really not a fan of using these obscure C++ template features, when all they do is create obfuscation rather than help the programmer to simplify the problem at hand. I find this code much easier to understnad for example:

Code: Select all

Bitboard b = ...;
while (b) {
    const int sq = next_bit(&b);
    ...
}

And when I get a compile time error, the error is in my code in a trivial part that I understand, instead of being in an illegible template library (the reason why I hate STL and use it only when I really need to).

[Rein Halbersma]

Thanks. I will have a look at your code. It will surely teach me some things about C++. But I still much prefer my C-style code as it is a *lot* shorter and simpler. Regarding iterators, I'm really not a fan of using these obscure C++ template features, when all they do is create obfuscation rather than help the programmer to simplify the problem at hand. I find this code much easier to understnad for example:

Code: Select all

Bitboard b = ...;
while (b) {
    const int sq = next_bit(&b);
    ...
}

First, calling STL iterators an "obscure feature" is not very helpful. If you seriously believe that, you are not getting the full benefit from C++ (you are using it as a strong type-checked C with classes). Modern C++ uses templates all over the place and for good reasons.

Second, I seriously doubt that the bit-loop with explicit pop_lsb calls is easy to understand for first-time engine programmers who have not been exposed to bit-twiddling before. The fact that high-performance engines use bitboards is an implementation detail (albeit a very important one for performance reasons). But IMHO that does not justify exposing that all over the place. Instead, I much prefer to iterate over bitboards just as over any other data structure

Code: Select all

BitSet b = ...;
for (auto it = b.begin(); it != b.end(); ++it) {
    ...
}

Here a BitSet is my wrapper class. It has the same interface as an STL std::set<int>, i.e. it's a sorted container of unique occupied square numbers. THat is the only thing worth knowing about the interface. The fact that computing its size and first member can be done using CPU intrinsics is nice and very important, but it's not worth exposing that all over the place.

And when I get a compile time error, the error is in my code in a trivial part that I understand, instead of being in an illegible template library (the reason why I hate STL and use it only when I really need to).

Use whatever suits your needs best. But if you learn to use the STL properly, you should not get too many illegible template errors in the first place

[lucasart]

obfuscated templates libraries may be useful for experienced C++ programmers who understand the arcanes of the STL (at best 1% of amateur C++ programmers?). But saying that they make life easier for beginners is such falsehood, it's not evne funny.
http://yosefk.com/c++fqa/templates.html

I have made a choice to use these nasty things to a minimum and only when they are actually useful. There are some many C++ programs that make a point of using all the defective C++ feature there is, as if their code was written to impress someone about their knowledge of the language. What matters is to write simple, maintainable, portable code. The rest is masturbation, IMO.
As a matter of fact, all very large projects written in C++ inevitably become an unmaintainable mess, that only some C++ gurus can fix (at huge cost, especially when the code is written to use all C++ obfuscated STL there is).

[Don]

obfuscated templates libraries may be useful for experienced C++ programmers who understand the arcanes of the STL (at best 1% of amateur C++ programmers?). But saying that they make life easier for beginners is such falsehood, it's not evne funny.
http://yosefk.com/c++fqa/templates.html

I have made a choice to use these nasty things to a minimum and only when they are actually useful. There are some many C++ programs that make a point of using all the defective C++ feature there is, as if their code was written to impress someone about their knowledge of the language. What matters is to write simple, maintainable, portable code. The rest is masturbation, IMO.
As a matter of fact, all very large projects written in C++ inevitably become an unmaintainable mess, that only some C++ gurus can fix (at huge cost, especially when the code is written to use all C++ obfuscated STL there is).

Amen to that. I find it useful to pretend an idiot must understand your code. And it's true, I am the idiot! And won't violate that unless there is a compelling reason (usually performance) for doing so.

[Rein Halbersma]

obfuscated templates libraries may be useful for experienced C++ programmers who understand the arcanes of the STL (at best 1% of amateur C++ programmers?). But saying that they make life easier for beginners is such falsehood, it's not evne funny.
http://yosefk.com/c++fqa/templates.html

The fact that perhaps less than 1% of C++ programmers is capable of writing easy-to-use, hard-to-misuse, efficient and re-usable Boost/STL-grade code, does not mean that more than 99% C++ users would not benefit from using Boost/STL itself. Just pointing to a FAQ of corner cases does not mean that the fast majority of template libraries is not enormously useful. E.g. both Stroustrup's Programming Principles book and the new edition of C++ Primer encourage the use template libraries even for beginning C++ users.

I have made a choice to use these nasty things to a minimum and only when they are actually useful. There are some many C++ programs that make a point of using all the defective C++ feature there is, as if their code was written to impress someone about their knowledge of the language. What matters is to write simple, maintainable, portable code. The rest is masturbation, IMO.
As a matter of fact, all very large projects written in C++ inevitably become an unmaintainable mess, that only some C++ gurus can fix (at huge cost, especially when the code is written to use all C++ obfuscated STL there is).

Not biting at the hyperbole and prejudiced generalization here The real fact is that any large project has the danger of becoming unmaintainable. Valdemar Erlingsson and Wylie Garvin made some very good -and language independent- points about that (essentially summarizing Code Complete)