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になっている。あそうか、Macのgccはデフォルトだと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) に変換してくれたら良いのに。