Tuesday, November 7, 2017

最高速の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がつけられるので、もっと普通のコードになる

14 comments:

  1. 共有していただきありがとうございます! これは私が必要とするものです。
    instagram viewer

    ReplyDelete

  2. شركة سكاي لخدمات نقل العفش والاثاث بالمنطقة العربية السعودية نحن نوفر خدمات نقل اثاث بالرياض ونقل عفش بالمدينة المنورة ونقل عفش بمكة ونقل عفش بالطائف نحن نقدم افضل نقل اثاث بخميس مشيط ونقل عفش بجدة
    شركة سكاي لنقل العفش
    نقل عفش بمكة
    نقل عفش بالرياض
    نقل عفش بالمدينة المنورة
    نقل عفش بجدة

    ReplyDelete
  3. شركة نقل عفش
    اهم شركات مكافحة حشرات بالخبر كذلك معرض اهم شركة مكافحة حشرات بالدمام والخبر والجبيل والخبر والاحساء والقطيف كذلك شركة رش حشرات بالدمام ومكافحة الحشرات بالخبر
    شركة مكافحة حشرات بالدمام
    شركة تنظيف خزانات بجدة الجوهرة من افضل شركات تنظيف الخزانات بجدة حيث ان تنظيف خزانات بجدة يحتاج الى مهارة فى كيفية غسيل وتنظيف الخزانات الكبيرة والصغيرة بجدة على ايدى متخصصين فى تنظيف الخزانات بجدة
    شركة تنظيف خزانات بجدة
    شركة كشف تسربات المياه بالدمام
    شركة نقل عفش واثاث

    ReplyDelete
  4. I like to read your article because it really helps me. Thank you for sharing this post with us.

    Togel Online

    Prediksi Hongkong

    ReplyDelete