Time ago I have found a little C++ program that computes the number of solutions to the N Queens problem at compile-time using just templates. I have translated it into CTFE code and I have shown in this newsgroup that if your purpose is to compute a result at compile-time, then D CTFE allows you to write much simpler (and faster) code compared to the C++ template mataprogramming.
This time I have translated that C++ code to D code that uses just templates. This is not idiomatic D code, because for this purpose CTFE is better, but templates are used in D too, so it may be a performance benchmark for templates in general. I am not very good with C++ templates yet, so if you spot an error in my D translation please tell me that I will redo the timings. Compilation time: G++ 0.96 seconds, dmd 12.4 seconds. With N=7 G++ uses about 34 MB RAM, DMD about 130+ MB RAM. I have used MinGW 4.5.1 and DMD 2.050. Compilation: g++ nqueens_cpp.cpp -o nqueens_cpp dmd nqueens_d.d The D code is nicer and shorter. GCC 4.5 has optimized the template compilation, and from the benchmark it seems faster: http://cpptruths.blogspot.com/2010/03/faster-meta-programs-using-gcc-45-and.html Is a similar optimization (using a hash) already present in DMD and is it useful? ----------------------------- // G++ 4.5.1 code #include "stdio.h" typedef unsigned long long uint64_t; template <uint64_t Cols = 0, uint64_t Diag135 = 0, uint64_t Diag45 = 0, uint64_t Solution = 0> struct state { static uint64_t const cols = Cols; static uint64_t const diag135 = Diag135; static uint64_t const diag45 = Diag45; static uint64_t const solution = Solution; }; template <int K, int J, typename State> struct test { static bool const result = ((State::cols & (1ull << J)) + (State::diag135 & (1ull << (J + K))) + (State::diag45 & (1ull << (32 + J - K)))) == 0; }; template <int K, int J, typename State> struct mark { typedef state < State::cols ^ (1ull << J), State::diag135 ^ (1ull << (J + K)), State::diag45 ^ (1ull << (32 + J - K)), State::solution > state_type; }; template <int StartValue, int Times, typename State> struct accumulate_result { typedef typename accumulate_result < StartValue + 1, Times - 1, state < State::cols, State::diag135, State::diag45, State::solution + test<0, StartValue, State>::result > >::state_type state_type; }; template <int StartValue, typename State> struct accumulate_result<StartValue, 0, State> { typedef State state_type; }; template <int Niv, int Dx, typename State> struct solve; template <bool Condition, typename State, int Current, int Niv, int Dx> struct result_from_test { typedef typename mark < Niv, Current, typename solve < Niv - 1, Dx, typename mark<Niv, Current, State>::state_type >::state_type >::state_type state_type; }; template <typename State, int Current, int Niv, int Dx> struct result_from_test<false, State, Current, Niv, Dx> { typedef State state_type; }; template <int Begin, int Times, typename State, int Niv, int Dx> struct process_queens { typedef typename process_queens < Begin + 1, Times - 1, typename result_from_test < test<Niv, Begin, State>::result, State, Begin, Niv, Dx >::state_type, Niv, Dx >::state_type state_type; }; template <int Begin, typename State, int Niv, int Dx> struct process_queens<Begin, 0, State, Niv, Dx> { typedef State state_type; }; template <int Niv, int Dx, typename State = state<> > struct solve { typedef typename process_queens<0, Dx, State, Niv, Dx>::state_type state_type; static uint64_t const result = state_type::solution; }; template <int Dx, typename State> struct solve<0, Dx, State> { typedef typename accumulate_result<0, Dx, State>::state_type state_type; static uint64_t const result = state_type::solution; }; template <int Dx> struct meta_queens: solve<Dx - 1, Dx> {}; int main() { printf("%llu", meta_queens<7>::result); } -------------------------------- // D2 code import core.stdc.stdio: printf; template State(ulong Cols=0, ulong Diag135=0, ulong Diag45=0, ulong Solution=0) { enum ulong cols = Cols; enum ulong diag135 = Diag135; enum ulong diag45 = Diag45; enum ulong solution = Solution; } template Test(int k, int j, alias state) { enum bool Test = ((state.cols & (1UL << j)) + (state.diag135 & (1UL << (j + k))) + (state.diag45 & (1UL << (32 + j - k)))) == 0; } template Mark(int k, int j, alias state) { alias State!(state.cols ^ (1UL << j), state.diag135 ^ (1UL << (j + k)), state.diag45 ^ (1UL << (32 + j - k)), state.solution ) Mark; } template AccumulateResult(int startValue, int times, alias state) { static if (times == 0) alias state AccumulateResult; else alias AccumulateResult!(startValue + 1, times - 1, State!(state.cols, state.diag135, state.diag45, state.solution + Test!(0, startValue, state)) ) AccumulateResult; } template ResultFromTest(bool condition, alias state, int current, int niv, int dx) { static if (condition == 0) alias state ResultFromTest; else alias Mark!(niv, current, Solve!(niv - 1, dx, Mark!(niv, current, state)) ) ResultFromTest; } template ProcessQueens(int begin, int times, alias state, int niv, int dx) { static if (times == 0) alias state ProcessQueens; else alias ProcessQueens!(begin + 1, times - 1, ResultFromTest!(Test!(niv, begin, state), state, begin, niv, dx), niv, dx ) ProcessQueens; } template Solve(int niv, int dx, alias state=State!()) { static if (niv == 0) alias AccumulateResult!(0, dx, state) Solve; else alias ProcessQueens!(0, dx, state, niv, dx) Solve; } template MetaNQueens(int dx) { enum ulong MetaNQueens = Solve!(dx - 1, dx).solution; } void main() { printf("%llu", MetaNQueens!(7)); } ----------------------------- Bye, bearophile
