たらいべんち

たらいまわしが流行って(いつの話だ)

memoがどうとかは考えず、素直な実装でコンパイル中に計算してしまって、その速度を比較してみます。

D版。

template tarai(int x, int y, int z) {
    static if (x <= y) {
        enum { v = y };
    } else {
        enum { v = tarai!(tarai!(x-1, y, z).v,
                          tarai!(y-1, z, x).v,
                          tarai!(z-1, x, y).v).v };
    }
}

static assert(0, tarai!(30, 15, 0).v);

C++版。

template<int x, int y, int z, bool b = x <= y> struct tarai {
    enum { x_ = tarai<x-1, y, z>::v,
           y_ = tarai<y-1, z, x>::v,
           z_ = tarai<z-1, x, y>::v,
           v = tarai<x_, y_, z_>::v };
};
template <int x, int y, int z> struct tarai<x, y, z, true> {
    enum { v = y };
};

#include <stdio.h>
int main() {
    printf("%d\n", tarai<30, 15, 0>::v);
}

C++版はコード生成までされちゃうので不利なのですが、 DMD より GCC の方が速くて意外でした。

G++: 1.798秒、 cl.exe(WINE): 3.828秒、 DMD: 2.759秒、 GDC: 2.803秒、 dmd.exe(WINE) 3.343秒、でした。 WINE の結果は参考程度にしかならないでしょう。 GDC がコンパイル通ってしまうのはたぶん static assert がサポートされてないバージョンだからかな。

i@u ~/wrk/tarai> time g++ -c tarai.cc
g++ -c tarai.cc  1.73s user 0.05s system 99% cpu 1.798 total
i@u ~/wrk/tarai> time cl.exe -c tarai.cc
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.

tarai.cc
cl.exe -c tarai.cc  3.31s user 0.33s system 94% cpu 3.828 total
i@u ~/wrk/tarai> time dmd -c tarai.d
tarai.d(11): static assert  (0) is false, 30
dmd -c tarai.d  2.67s user 0.05s system 98% cpu 2.759 total
i@u ~/wrk/tarai> time gdc -c tarai.d
gdc -c tarai.d  2.70s user 0.07s system 98% cpu 2.803 total