ローレベルな最適化をしてみる

d.y.d.を見て、O(n)くらい→必要ならO(1)で n*(n+1)/ 2 にするとかオーダーを意識しよう、という趣旨だということは百も承知で、ローレベルな最適化をして遊んでしまったのでメモ。

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char* argv[] ) {
    if( argc >= 2 ) {
        long long sum = 0;

        int i, n = atoi(argv[1]); // n := コマンドの第一引数
        for( i=0; i<n; ++i )      // 0 から n-1 まで足し算
            sum += i;
        printf("%lld\n", sum);
    }
    return 0;
}

これを最適化コンパイルして 10億 を渡して実行すると、要は10億回ループで足し算すると、 どのくらいの時間で答えが表示されるでしょうか。実際に動かさずに頭で考えてみて下さい。 Cはわからんという方は、適当に自分の好きな言語で。1ミリ秒? 1秒? 1分? 1時間? 1日?

まぁ1秒は切るかなーと思いつつ、上記引用のソースを10億ループで手元のマシン(MacBook Pro / Intel Core 2 Duo 2.4GHz)上のgcc-4.0.1で単純に-O3で実行してみる。

% gcc -O3 sum.c
% time ./a.out 1000000000
499999999500000000
./a.out 1000000000  1.30s user 0.01s system 98% cpu 1.337 total

ふむ、思ったより遅かった(あくまでO(n)の範囲で)。
そこで、ちょっとディスアセンブルしてみる

% otool -tV a.out
....
00001fd0	xorl	%eax,%eax
00001fd2	xorl	%edx,%edx
00001fd4	xorl	%ecx,%ecx
00001fd6	nopw	%cs:0x00000000(%eax,%eax)
00001fe0	addl	%edx,%esi
00001fe2	adcl	%ecx,%edi
00001fe4	incl	%eax
00001fe5	addl	$0x01,%edx
00001fe8	adcl	$0x00,%ecx
00001feb	cmpl	0xe4(%ebp),%eax
00001fee	jne	0x00001fe0
00001ff0	jmp	0x00001fa4

いっぱい出るけど、肝心のループ部分意外は無視して良い。で、上記がそのループ部分に該当する。なんか妙に冗長な気がする。
ソースを見てみると、sumの型はlong longになっている。あそうか、Macgccはデフォルトだとx86の32bitコードを吐くので、long long(64bit)の足し算は2命令に別れる(adclが出てくる)んだ、と思い当たる。
とりあえず64bitバイナリにしてみよう。

% gcc -arch x86_64 -O3 sum.c
% time ./a.out 1000000000
499999999500000000
./a.out 1000000000  0.84s user 0.01s system 97% cpu 0.863 total

ふむ、とりあえず1秒切った。ディスアセンブルしてみる。ループ部分は以下。

0000000100000f50	incl	%ecx
0000000100000f52	addq	%rdx,%rsi
0000000100000f55	incq	%rdx
0000000100000f58	cmpl	%ecx,%eax
0000000100000f5a	jne	0x00000f50

あれ、何かインクリメントが2回?
多分、int用とlong long用のレジスタを使い分けてるのだろう、と想像。intの代わりにlongにしてしまえ、とソースを書き換えてもう一度。

        int i, n = atoi(argv[1]); // n := コマンドの第一引数
          ↓
        long i, n = atoi(argv[1]); // n := コマンドの第一引数
% gcc -arch x86_64 -O3 sum.c
% time ./a.out 1000000000
499999999500000000
./a.out 1000000000  0.72s user 0.00s system 98% cpu 0.735 total

さらに速くなった。やっぱりループ部分をディスアセンブルしてみよう。

0000000100000f50	addq	%rdx,%rsi
0000000100000f53	incq	%rdx
0000000100000f56	cmpq	%rdx,%rax
0000000100000f59	jne	0x00000f50

うんうん、これを期待していた。


趣旨を外れて暴走気味ですが、低レベルな職業柄か朝からこんなことばかり思いついてしまう。><

まあ5分くらい弄ってたら2倍近く高速化できたなーってのと、CPU内でμOPs化されて最適化されるような時代でも未だアセンブリ見る意味がある(こともある)んだ、と思ったので。

追記:

Linux/ gcc-4.3 x86_64でやったら、全然違うアセンブリ(lea命令使ったもの)になって、intのが速かった。Mac付属のgcc-4.2だと上記と同じなのだけど。4.3でより最適化が進むようになったとか?(prefixだらけだし命令数は多くなるのに。) やっぱり何が速いかはアセンブリ見ても分からないのですね。><


ループ開始アドレスが16byte-alignになるよう、適当なbyte数のNOP(1命令)が入るらしい(4.0でも)。命令キャッシュにループがきれいに乗って速いんでしょうね。


ちなみにgcc-4.2以降で-O1以上を指定し、atoi を使わず 100000000 とハードコーディングすると、信じられないほど速くなります。
理由はコンパイル時に計算されて答えが埋め込まれるから。もはやO(1)っていうかO(0)。でもその分コンパイルが遅い(実際にループして計算しているのでしょう)。
どうせならatoi指定しても数列和公式で O(1) に変換してくれたら良いのに。