最高速のfizzbuzzを実装する話

この前、Twitterで誰かが「コンパイラ言語でFizzbuzz書くなら、コンパイル時に全ての演算を済ませ、実行コストはI/O命令1個になるように最適化しないと」という話をしていた。いいこと言うな、と思ってスルーしていたのだが、体調不良で頭だけ動いている状態だったのでC++11でトライしてみることに。

案ずるより産むが易しというもので、割と簡単に綺麗に書けた。こんな感じ。

char配列を可変長のテンプレート引数として結合していって、文字列定数を生成するというテクニックは実際に使い所があるかもと思った。最近C++書いてないけど。

#include <cstdio>

template <typename LHS, int N> struct numstr {
    template <char... Args> struct append {
        typedef typename numstr<LHS, N / 10>::template append<'0' + N % 10, Args...>::result result;
    };
};

template <typename LHS> struct numstr<LHS, 0> {
    template <char... Args> struct append {
        typedef typename LHS::template append<Args...>::result result;
    };
};

template <int N, int Mod3 = N % 3, int Mod5 = N % 5> struct fizzbuzz {
    template <char... Args> struct append {
        typedef typename numstr<fizzbuzz<N - 1>, N>::template append<'\n', Args...>::result result;
    };
};

template <> struct fizzbuzz<0> {
    template <char... Args> struct append {
        struct result {
            const char data[sizeof...(Args)];
            constexpr result() : data{Args...} {}
        };
    };
};

template <int N> struct fizzbuzz<N, 0, 0> {
    template <char... Args> struct append {
        typedef typename fizzbuzz<N - 1>::template append<'F', 'i', 'z', 'z', 'B', 'u', 'z', 'z', '\n', Args...>::result result;
    };
};

template <int N, int Mod5> struct fizzbuzz<N, 0, Mod5> {
    template <char... Args> struct append {
        typedef typename fizzbuzz<N - 1>::template append<'F', 'i', 'z', 'z', '\n', Args...>::result result;
    };
};

template <int N, int Mod3> struct fizzbuzz<N, Mod3, 0> {
    template <char... Args> struct append {
        typedef typename fizzbuzz<N - 1>::template append<'B', 'u', 'z', 'z', '\n', Args...>::result result;
    };
};

int main() {
    constexpr fizzbuzz<100>::append<>::result s;
    fwrite(s.data, 1, sizeof(s.data), stdout);
    return 0;
}

コンパイルしてディスアセンブルすると、コンパイル時に生成された文字列定数をfwriteするだけのmain関数が生成されていることが確認できる。

$ clang++ -O2 -std=c++11 -pedantic -Wall fizzbuzz11.cc && otool -tV a.out
a.out:
(__TEXT,__text) section
_main:
0000000100000dd0 pushq %rbp
0000000100000dd1 movq %rsp, %rbp
0000000100000dd4 movq 0x225(%rip), %rax ## literal pool symbol address: ___stdoutp
0000000100000ddb movq (%rax), %rcx
0000000100000dde leaq __ZZ4mainE1s(%rip), %rdi ## main::s
0000000100000de5 movl $0x1, %esi
0000000100000dea movl $0x19d, %edx
0000000100000def callq 0x100000df8 ## symbol stub for: _fwrite
0000000100000df4 xorl %eax, %eax
0000000100000df6 popq %rbp
0000000100000df7 retq

ちなみに、C++14だと、いたるところにconstexprがつけられるので、もっと普通のコードになる。