テンプレートでたらいまわし(7回目)

引数を遅延評価するようにしたらかえって遅くなった。

#include <iostream>

/* Int */
template <int x>
struct Int
{
    enum { value = x };
};

/* Tarai */
template <int x, int y, int z>
struct Tarai;

template <class X, class Y, class Z>
struct Tarai0;

template <bool b, class X, class Y, class Z>
struct Tarai1;

template <class X, class Y, class Z>
struct Tarai2;

template <class X, class Y, class Z>
struct TaraiDelay2;

template <class T>
struct TaraiForce;

template <int x, int y, int z>
struct Tarai
{
    enum { value = Tarai0< Int<x>, Int<y>, Int<z> >::value };
};

template <class X, class Y, class Z>
struct Tarai0
{
    enum { x = TaraiForce<X>::value,
           y = TaraiForce<Y>::value };
    enum { value = Tarai1< (x <= y), Int<x>, Int<y>, Z >::value };
};

template <class X, int y, class Z>
struct Tarai1<true, X, Int<y>, Z>
{
    enum { value = y };
};

template <class X, class Y, class Z>
struct Tarai1<false, X, Y, Z>
{
    typedef TaraiDelay2<X, Y, Z> XX;
    typedef TaraiDelay2<Y, Z, X> YY;
    typedef TaraiDelay2<Z, X, Y> ZZ;
    enum { value = Tarai0< XX, YY, ZZ>::value };
};

template <class X, class Y, class Z>
struct Tarai2
{
    enum { x = TaraiForce<X>::value };
    enum { value = Tarai0< Int<x - 1>, Y, Z >::value };
};

template <int n>
struct TaraiForce< Int<n> >
{
    enum { value = n };
};

template <class X, class Y, class Z>
struct TaraiForce< TaraiDelay2<X, Y, Z> >
{
    enum { value = Tarai2<X, Y, Z>::value };
};

int main(int argc, char *argv[])
{
    int n = Tarai<48, 24, 0>::value;
    std::cout << n << std::endl;

    return 0;
}
% time g++ tarai7.cpp

real    0m12.758s
user    0m12.001s
sys     0m0.136s

% time ./a.out
48

real    0m0.003s
user    0m0.004s
sys     0m0.000s

悔しいので、なんとか速くならないかと足掻いてみると、以下のコードでかろうじて6回目のものを上回った。

#include <iostream>

/* Int */
template <int x>
struct Int
{
    enum { value = x };
};

/* Tarai */
template <int x, int y, int z>
struct Tarai;

template <class X, class Y, class Z>
struct Tarai0;

template <bool b, class X, class Y, class Z>
struct Tarai1;

template <class X, class Y, class Z>
struct Tarai2;

template <class X, class Y, class Z>
struct TaraiDelay2;

template <int x, int y, int z>
struct Tarai
{
    enum { value = Tarai0< Int<x>, Int<y>, Int<z> >::value };
};

template <int x, int y, class Z>
struct Tarai0< Int<x>, Int<y>, Z >
{
    enum { value = Tarai1< (x <= y), Int<x>, Int<y>, Z >::value };
};

template <class X, int y, class Z>
struct Tarai1< true, X, Int<y>, Z >
{
    enum { value = y };
};

template <int x, int y, class Z>
struct Tarai1<false, Int<x>, Int<y>, Z>
{
    typedef Int<x> X;
    typedef Int<y> Y;
    enum { xx = Tarai0< Int<x - 1>, Y, Z>::value,
           yy = Tarai0< Int<y - 1>, Z, X>::value };
    typedef Int<xx> XX;
    typedef Int<yy> YY;
    // この部分を有効にするだけでかなり遅くなる
    // typedef TaraiDelay2<Z, X, Y> ZZ;
    typedef void ZZ;
    enum { value = Tarai0< XX, YY, ZZ>::value };
};

template <int x, class Y, class Z>
struct Tarai2< Int<x>, Y, Z>
{
    enum { value = Tarai0< Int<x - 1>, Y, Z >::value };
};

// 実際には使われない
template <class Y, class Z, class XX, class YY, class ZZ>
struct Tarai2< TaraiDelay2<XX, YY, ZZ>, Y, Z >
{
    enum { x = Tarai2<XX, YY, ZZ>::value };
    enum { value = Tarai0< Int<x - 1>, Y, Z >::value };
};

int main(int argc, char *argv[])
{
    int n = Tarai<48, 24, 0>::value;
    std::cout << n << std::endl;

    return 0;
}
% time g++ tarai7-2.cpp

real    0m3.378s
user    0m3.252s
sys     0m0.104s

% time ./a.out
48

real    0m0.002s
user    0m0.000s
sys     0m0.004s

ただ、ここまで変えてしまうと問題の本質からは外れてしまっている気がする。しかもそこまでしてもわずかしか速くならないのはどういうことか。どうもテンプレートのインスタンス化は相当重い処理のようで、下手に遅延評価のための構造を増やすよりも、zの無駄な計算をやる方が、memoizeも効いているので結果的には速い、ということのようだ。(この結果はコンパイラによっても変わってきそうだが)