C++ templates question

Discussion of chess software programming and technical issues.

Moderator: Ras

Jose Carlos
Posts: 151
Joined: Wed Mar 08, 2006 10:09 pm
Location: Murcia (Spain)

Re: Some advice needed

Post by Jose Carlos »

Sven Schüle wrote: Hi José,

some points:

1) I hope your InsertPawnCapture() method also covers promotions with capture, otherwise you'd better insert that part into InsertPawnMoves().

2) The assert() for tColor to be either white or black should be moved to the very beginning of the function. C++, as opposed to C, does not require all declarations to appear before the first statement, so you can start with an assert() before accessing the "assert-ed" parameters in the initializer expression of a variable declaration.

3) If you use constants like tAdvanceOne, tRowPromo etc. at several places in the move generator, or even in the whole program, you might consider to provide static inline template functions (maybe in some Board class) returning the appropriate color-dependent value based on accessing an (also static) array of two elements, as in this example:

Code: Select all

// header file: declaration

class CBoard {
public:
    static template <CColor::TColores tColor> advanceOne();
private:
    static CSquare::TDirections tAdvanceOne[2];
};

// static
inline template <CColor::TColores tColor> CBoard::advanceOne()
{
    return tAdvanceOne[tColor];
}

// cpp file: definition of static variables

// static
CSquare::TDirections tAdvanceOne[2] = {
    CSquare::UP, CSquare::DOWN
};

// used somewhere:

cTo = cFrom + CBoard::advanceOne<tColor>();
There is a tiny overhead of typing few more characters but you save repeating all the same code to define and initialize those constants in each function that uses them. The compiler will replace the function call with the correct array element without any overhead since the array index is known at compile time and the array is static, i.e. not part of any object instance and has therefore a fixed address.

As I said, my proposal is not suitable if this is the only place where you use those constants.

Sven
Hi Sven. Thanks for the explanations. As I said, I'm new to C++ and I'm learning (and enjoying the learning) as I write the program.

InsertPawnCapture covers promotions, yes, but I've found another error while reading the code I posted: I increment the pointer (pMove), but InsertPawnCapture could find there's no opponent piece in the To square, and then it won't insert the move, so the pointer should not be incremented.
I still don't have enough code to run the program and test it, so I just type and type, hoping it'll work someday... :)

Ok, I'll move the assert to the top. I think I'll have a hard time to get used to declarations not in the first lines, but I'll survive.

Right now, those constants are used only there. Actually, I had written the function splitting white and black; then I saw templates in Stockfish and I thought they were worth a try. I figured out those constants (I didn't declare them as const until Marco said it) as the way to avoid splitted code. I'm not sure if I'll need them somewhere else in the code, but I'll do what you propose anyway because it'll help me understanding templates better.

Thanks again.
__________________________
José Carlos Martínez Galán
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: Some advice needed

Post by mcostalba »

Sven Schüle wrote:The compiler will replace the function call with the correct array element without any overhead since the array index is known at compile time and the array is static, i.e. not part of any object instance and has therefore a fixed address.
Hi Sven, sorry to contradict you but your solution is not the equivalent of constant substitution at compile time (as is the original) in your case the array is actually instantiated in memory at program startup and a memory access (although at fixed address) is done every time the value is required. Because Josè is new to templates I'd prefer to do not mess the discussion with too complex (and incorrect) stuff.
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: Some advice needed

Post by mcostalba »

José Carlos wrote:I'll do what you propose anyway because it'll help me understanding templates better.
If you want to understand templates better try to understand this that is the correct implementation of what Sven suggested:

Code: Select all

template<CColor::TColores tColor> struct advanceOne {
    enum { value = tColor == CColor::WHITE ? CSquare::UP : CSquare::DOWN };
};

With usage:

adv = advanceOne<tColor>::value;

The critical observation that you want to do is that there is _no_ variable declared whatsover because an enum is not a variable, so there are no runtime entities of any kind but all the work is done 100% at compile time. If you get this example you can say you have understood the templates ;-)
Jose Carlos
Posts: 151
Joined: Wed Mar 08, 2006 10:09 pm
Location: Murcia (Spain)

Re: Some advice needed

Post by Jose Carlos »

mcostalba wrote: If you want to understand templates better try to understand this that is the correct implementation of what Sven suggested:

Code: Select all

template<CColor::TColores tColor> struct advanceOne {
    enum { value = tColor == CColor::WHITE ? CSquare::UP : CSquare::DOWN };
};

With usage:

adv = advanceOne<tColor>::value;

The critical observation that you want to do is that there is _no_ variable declared whatsover because an enum is not a variable, so there are no runtime entities of any kind but all the work is done 100% at compile time. If you get this example you can say you have understood the templates ;-)
Hard to get. A struct (semantycally equivalent to a class) with no data members, but just an enum with only one value, which is computed from the template parameter at compile time... :shock:
I wonder if that struct would be equivalent to a namespace in this context... I guess it wouldn't (probably becauses there can't be templated namespaces)... I need to think about it to make sure I understand.
Thanks for the lessons :)
__________________________
José Carlos Martínez Galán
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Some advice needed

Post by Sven »

mcostalba wrote:
Sven Schüle wrote:The compiler will replace the function call with the correct array element without any overhead since the array index is known at compile time and the array is static, i.e. not part of any object instance and has therefore a fixed address.
Hi Sven, sorry to contradict you but your solution is not the equivalent of constant substitution at compile time (as is the original) in your case the array is actually instantiated in memory at program startup and a memory access (although at fixed address) is done every time the value is required. Because Josè is new to templates I'd prefer to do not mess the discussion with too complex (and incorrect) stuff.
I don't see how it is incorrect. Accessing elements of a "static const" array with a constant array index will surely be optimized by replacing the array access with the value, the same as for a single "static const" variable that is not part of an array. That is no memory access at runtime. You are right when stating that my proposal is not closely related to templates, but I'm pretty sure that you're wrong when calling it "incorrect". The key is the "const" keyword.

Sven
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: Some advice needed

Post by mcostalba »

Sven Schüle wrote:but I'm pretty sure that you're wrong when calling it "incorrect"
You don't have to mix correct semantic with what the compiler is able to do in terms of optimization.

I have rewritten the two approaches and tested to semantically validate if we are talking of compile time constants or not:

Code: Select all


// Real compile time stuff here
template<Color tColor> struct advanceOne1 {
    enum { value = tColor == WHITE ? 8 : -8 };
};


// Run time entities that perhaps happens to be simplified at
// compile time due to smart compiler
static const int tAdvanceOne[2] = { 0, 1 };

template <Color tColor> inline int advanceOne2()
{
    return tAdvanceOne[tColor];
}

template <int n> struct test_compile_time_parameter {}; // Our little validation tool



test_compile_time_parameter<advanceOne1<WHITE>::value> t1;  // OK we can pass advanceOne1::value as template parameter

test_compile_time_parameter<advanceOne2<WHITE>()> t2; // Compile error. Not a compile time constant !

compile_time_parameter<tAdvanceOne[WHITE]> t3; // Compile error. Surprise !  Even this is not a semantically correct compile time constant 
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Some advice needed

Post by Sven »

Hi Marco,

my conclusion is very simple:

You are right, and I was wrong!

I checked your program snippet and verified that your conclusions are valid. I stand corrected. Please accept my apologies for not having checked my code proposal on my own with a compiler.

The good news is, I have learned really a lot from your valuable contribution. Even though it was simple to find out that my (even repeated) claim was wrong using your "little validation tool", I never had that particular idea how to check whether something is a compile-time constant or not. Using that "something" as a template argument for "something else" does the trick.

In the future, before posting code snippets I should probably take the time to use a compiler at least. I did it by heart this time since I was absolutely convinced of the correctness of my idea. Actually it is not only an "idea", I have also used code like this frequently. The point is: it is not "incorrect code" (here I am not talking about using my code together with your "little validation tool" but about the pure code itself that I presented) but it is not suitable as a replacement for a compile-time constant. That's really surprising for me since I have no idea why semantics are really "blocking" possible optimizations here (you have to admit: the compiler can know exactly the value of "tAdvanceOne[WHITE]" and therefore also of the expression that "calls" the inline function "advanceOne<WHITE>()", but I have to accept it. It is also a new limit of inlining that I was not aware of up to now, so thank you, Marco, for that lesson!

The second good news is, using this knowledge might help me to slightly improve my chess engine, by avoiding this technique of which I really firmly believed it were appropriate. I must admit that, mostly due to the fact that my engine "KnockOut" isn't among the top 100 existing engines, I never cared much about optimizing it on the assembler level. Now that I saw this assembler code with my own eyes, after compiling some example code with VS2010:

Code: Select all

    int const cFrom = 33;
    int cTo = cFrom + CBoard::advanceOne<CColor::WHITE>();
00401000  mov         eax,dword ptr [CBoard::tAdvanceOne (403020h)]  
00401005  add         eax,21h  
I am fully convinced of my proposal being "invalid" in terms of optimized code. However, if speed is *not* an issue then it might still be a good alternative due to its simplicity. Your "template enum" approach, though, is clearly the better one.

@José: My apology goes also to you, for having gone slightly off-topic with my well-meant proposal that was finally proven to be wrong by Marco.

Sven
Jose Carlos
Posts: 151
Joined: Wed Mar 08, 2006 10:09 pm
Location: Murcia (Spain)

Re: Some advice needed

Post by Jose Carlos »

Dont apologize, please. This debate is of great interest for me. I have learnt a lot from both of you.

Thank you very much.
__________________________
José Carlos Martínez Galán
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: C++ templates question

Post by Daniel Shawul »

Hello Jose
If you are really into templates the best book i can recommend is "Modern C++ Design by Andrei Alexandrescu". Very thorough discussion of template metaprogramming in general. Usually towards the end of the book,I usually get a head ache and still haven't finished it yet ...
Daniel
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: Some advice needed

Post by mcostalba »

Sven Schüle wrote:Please accept my apologies


O c'mon Sven you really don't need to apologize for anything :-)

And by the way you were not far from to be correct: array are not allowed but const integer variables are (perhaps surprising) allowed to be used as template parameters by the standard. For instance this works either:

Code: Select all

// We use a const int instead of an enum
template<Color tColor> struct advanceOne1 {
   static const int value = tColor == WHITE ? 8 : -8;
};

template <int n> struct test_compile_time_parameter {}; 

test_compile_time_parameter<advanceOne1<WHITE>::value> t1;  // OK we can pass advanceOne1::value as template parameter 
This is somewhat a bit of hack because it is not clear why single const variable are allowed and arrays are not. The historical reason is that C++ designers wanted to give a stop to the C style #define and so allowed the const integers to be used as a perfect replacement of a #define, for instance you can define a given const int variable in an header file and include it how many times you want and you'll never get a "variable redefinition" error as should be with any other type of variable....C++ is full of these little details: it can be fun or it can be a nightmare according to your mood :-)