The fastest perft in the West

[Rein Halbersma]

What's faster than running perft() in a few seconds? Running perft() in zero seconds of course! And I don't mean computing perft() numbers at program startup time, store them into a table and reading them out again. No, I mean computing perft() completely at compiletime.

Code: Select all

#include <dctl.hpp>

using namespace dctl::core;
using namespace dctl::algo;

int main()
{
  static_assert(
    traversal::depth_limited_count<true>( // perft with bulk-counting
      basic_state<
        international,
        basic_board<international>
      >::initial(),                       // the starting position in International Draughts
      7,                                  // depth = 7
      drop_duplicates_gen                 // no duplicate captures
    ) == 1'049'442
  );
}

Thaty's right: a full perft(7) run, completely done at compiletime. Made possible by g++12 with -std=c++20 and -fconstexpr-ops-limit=34359738368 as compiler options. Running this on my Linux dev box:

Code: Select all

rein@rein-virtual-machine:~/projects/dctl/build$ time example/constexpr 

real	0m0,003s
user	0m0,000s
sys	0m0,003s

So a perfect 0.000s runtime perft(7): I'll take and keep that speed crown forever now

What makes this possible? Short answer: g++12 and a machine with at leat 38Gb of RAM and 15 minutes of compilation time. Long answer: a conforming C++20 compiler. In C++20, almost everything is constexpr: all the Standard Library algorithms and some of the containers such as std::string and std::vector. There are some caveats (e.g. you must use a compiletime std::vector within the constexpr computation).

In C++20, you can also use almost the full language at compile time. I simply sprinkled "constexpr" in front of every function and increased the default compiler limit of constexpr operations by 1000X from 1<<25 to 1<<35. Without this limit expansion, only perft(4) works out of the box. But that's it: my regular perft() function works at compile-time and the compiler can count over a million positions.

Why not the full perft(11)? I tried it, and g++ ran out of memory The perft(7) run took 38Gb of RAM, higher depths consumed at least 48Gb (the size of my Linux VM on my 64Gb machine). Perhaps in the near future, compiler technology improves to a state where perft(11) can be comfortably computed. Since g++12 came out in April 2022, I could have done this computation already 6 months ago, but I only realized it this weekend and it worked almost out of the box with very little modification.

Note to other authors: every draughts program can now achieve this, as long as you mark all your own functions constexpr and use a constexpr container to store your generated moves into (C-array, std::array, std::vector or a homegrown datastructure that is constexpr-ified). You might have troubles using other libraries (I had when I used Boost.StaticVector or Boost.SmallVector to store the generated moves).

[Joost Buijs]

Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.

[Rein Halbersma]

Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.

Ah but this is not template-metaprogramming. Just a regular perft() function but called inside a static_assert(), so done at compiletime. This requires no modification of existing code, apart from prefixing all your functions with "constexpr".

[Joost Buijs]

Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.

Ah but this is not template-metaprogramming. Just a regular perft() function but called inside a static_assert(), so done at compiletime. This requires no modification of existing code, apart from prefixing all your functions with "constexpr".

Aha, I have to admit that I didn't look at the code snippet and blindly assumed you were using TMP. It's truly amazing that the compiler is capable of checking a complex function like perft() with a static assert, I never thought this would be possible. Of course you could do this with TMP as well, but that would mean writing totally different code.

I wonder whether other C++ compilers like CLang and MSVC are also capable of doing this.

[Rein Halbersma]

Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.

Ah but this is not template-metaprogramming. Just a regular perft() function but called inside a static_assert(), so done at compiletime. This requires no modification of existing code, apart from prefixing all your functions with "constexpr".

Aha, I have to admit that I didn't look at the code snippet and blindly assumed you were using TMP. It's truly amazing that the compiler is capable of checking a complex function like perft() with a static assert, I never thought this would be possible. Of course you could do this with TMP as well, but that would mean writing totally different code.

In theory, a TMP program could also do this already with C++98 code. But I doubt any compiler would be able to do perft(7) using TMP. I used to rotate the bit-layout using TMP and I can tell you that even such "minor" operations took an enormous amount of compile time. With constexpr the slow down is about 100x-1000x. With TMP it's a factor of 1M or more.

I started my DCTL project around 2010 and in the early years I indeed had to heavily rely on TMP (the Boost.MPL library in particular). Around 2013 it became clear to me that C++11 constexpr (only one-line non-mutating functions would be greatly expanded in C++14 (then to all non-virtual non-allocating, but mutating functions). I basically went all in on that bet and wrote my constexpr bitset at that time and largely eliminated TMP from my program. C++17 and C++20 have added virtual and allocating code to constexpr and used the expanded constexpr across the entire Standard Library, to the point where all algorithms and sequence containers are constexpr now.

I wonder whether other C++ compilers like CLang and MSVC are also capable of doing this.

https://en.cppreference.com/w/cpp/compi ... y_features

It appears that Clang 15 and MSVC 2022 have constexpr string/vector and will also be able to run perft() in the compiler. I haven't tested it yet because Clang misses some other C++20 features that my program relies on. I think MSVC 2022 will work out of the box for my program.

[Joost Buijs]

In C++20 there is also 'consteval' to declare an immediate function that has to be evaluated at compile-time and always produces a compile-time constant. This is more strict than 'constexpr' which can be used at run-time as well.

The last years C++ is getting extremely complicated, I take my hat off to the people writing parsers and code-generators for it.

[Rein Halbersma]

Aha, I have to admit that I didn't look at the code snippet and blindly assumed you were using TMP. It's truly amazing that the compiler is capable of checking a complex function like perft() with a static assert, I never thought this would be possible. Of course you could do this with TMP as well, but that would mean writing totally different code.

I wonder whether other C++ compilers like CLang and MSVC are also capable of doing this.

Clang 16 (development version, will be released in April 2023 I think) now also successfully computes perft(7) at compile time. Most likely Visual C++ as well, but I'm too lazy to install the latest edition again (my dev env is Linux).