Bug 5276 – Template compilation uses much more memory than G++ 4.8

Created attachment 832 D2 version of the benchmark This performance bug may share the same cause of bug 4900 If this turns out to be true then we may close this as resolved duplicated. In attach there are two programs that perform many computations at compile time using just templates, one written in C++ and one in D2. This is not idiomatic D code, because for this purpose CTFE is better, but it may be good enough as first performance benchmark for templates. Compilation time (N=7): G++ 0.95 seconds, dmd 12.4 seconds. 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 See also: http://cpptruths.blogspot.com/2010/03/faster-meta-programs-using-gcc-45-and.html

Created attachment 833 C++ G++ 4.5 version of the benchmark

I'm getting: N=7: 0.55s g++-4.7.3 versus 0.77s dmd 2.066-alpha N=8: 2.17s g++-4.7.3 versus 1.41s dmd 2.066-alpha Dmd uses much more memory (as usual.)

(In reply to safety0ff.bugz from comment #2) > I'm getting: Now my timings for N=7 are about 1 second for dmd, and about 1.1 seconds for g++. So for this benchmark the dmd performance problem is not a problem. Is the lazy instantiation of templates recently introduced by Walter the cause of this significant performance increase? For N=7 dmd uses about 130 MB RAM, while g++ uses about 30 MB. So the memory usage is about the same, but now dmd is much faster than before. So the original bug report could be closed. Or I can rename it, turning it into a memory usage problem instead: on my system I can compile the C++ code with N=9 (it uses about 1/2 GB RAM), but I think I can't compile the D code with N=9 on my PC.

Updated D code, a little slower (?) but also nicer: 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; } enum Test(int k, int j, alias state) = ((state.cols & (1UL << j)) + (state.diag135 & (1UL << (j + k))) + (state.diag45 & (1UL << (32 + j - k)))) == 0; alias Mark(int k, int j, alias state) = State!(state.cols ^ (1UL << j), state.diag135 ^ (1UL << (j + k)), state.diag45 ^ (1UL << (32 + j - k)), state.solution); template AccumulateResult(int startValue, int times, alias state) { static if (times == 0) alias AccumulateResult = state; else alias AccumulateResult = AccumulateResult!( startValue + 1, times - 1, State!(state.cols, state.diag135, state.diag45, state.solution + Test!(0, startValue, state))); } template ResultFromTest(bool condition, alias state, int current, int niv, int dx) { static if (condition == 0) alias ResultFromTest = state; else alias ResultFromTest = Mark!(niv, current, Solve!(niv - 1, dx, Mark!(niv, current, state))); } template ProcessQueens(int begin, int times, alias state, int niv, int dx) { static if (times == 0) alias ProcessQueens = state; else alias ProcessQueens = ProcessQueens!( begin + 1, times - 1, ResultFromTest!(Test!(niv, begin, state), state, begin, niv, dx), niv, dx); } template Solve(int niv, int dx, alias state=State!()) { static if (niv == 0) alias Solve = AccumulateResult!(0, dx, state); else alias Solve = ProcessQueens!(0, dx, state, niv, dx); } enum MetaNQueens(int dx) = Solve!(dx - 1, dx).solution; void main() { import core.stdc.stdio: printf; printf("%llu", MetaNQueens!7); }

Fixed by https://github.com/dlang/dmd/pull/2239 - compilation is under one second now.