2009年11月13日
比較を 0 と行うという最適化は有効なのか ?
多くの CPU の命令セットでは、0 との比較を特別扱いしています。
そのため、ループを書く際には、なるべく 0 と比較するように書いた方が速いので良い、という主張をたまに聞きます。
しかし、一般的な for 文のイディオム for (i = 0; i < N; i++) を崩してまで、0 と比較するように書く意味が、本当にあるのでしょうか ? それぐらいは、現代のコンパイラならば勝手に最適化してくれそうな気もします。
というわけで、x86、ARM、SH、MIPS、PPC で検証してみました。
x86 は、手元の MinGW の gcc 4.4.0 です。
それ以外の CPU は、弊社の exeGCC 4 (GCC 4.3.3 ベース) を使用しました。最適化レベルは、全て一般的な -O2 です。(FPU は無関係だと思われるので、全て disable モードでコンパイルしています。)
そのため、ループを書く際には、なるべく 0 と比較するように書いた方が速いので良い、という主張をたまに聞きます。
しかし、一般的な for 文のイディオム for (i = 0; i < N; i++) を崩してまで、0 と比較するように書く意味が、本当にあるのでしょうか ? それぐらいは、現代のコンパイラならば勝手に最適化してくれそうな気もします。
というわけで、x86、ARM、SH、MIPS、PPC で検証してみました。
x86 は、手元の MinGW の gcc 4.4.0 です。
それ以外の CPU は、弊社の exeGCC 4 (GCC 4.3.3 ベース) を使用しました。最適化レベルは、全て一般的な -O2 です。(FPU は無関係だと思われるので、全て disable モードでコンパイルしています。)
例題プログラムは全て共通です。
まず、x86 です。(不要な部分は編集しています。以下同様です。)
ARM ではどうでしょうか。v5 アーキテクチャ(926ES-J)、Little endian、ARM モードの結果です。
SH ではどうでしょうか。SH4、Little endian での結果です。
PPC ではどうでしょうか。Generic PowerPC、Little Endian での結果です。
MIPS ではどうでしょうか。mips32、Little endian での結果です。
- まとめ
確かに命令数が減るプロセッサ (ARM、MIPS) もあるのですが、やはり全く変わらないものもある (x86、PPC、SH) という結果になりました。
個人的には、このような最適化が無意味とまでは言いませんが、for 文のイディオムを崩してまで積極的にマイクロオプティマイズする価値は低いのではないかと思います。例えば、0 と、 -1 など他の数、どちらの定数と比較しても良いような場合は、0 と比較するように意識して書いた方が良いかも、という程度だと思います。
#include <stdio.h> int x; void f1(int n) { int i; for (i = 0; i < n; i++) { x += i; } } void f2(int n) { int i; for (i = n - 1; i >= 0; i--) { x += i; } } int main() { x = 0; f1(10); printf("%d\n", x); x = 0; f2(10); printf("%d\n", x); return 0; }なるべくコードの見た目が同じになるように配慮しました。また、ループ回数だけではなく、カウンタ変数自体の値を利用したいケースも考慮し、値の遷移する範囲も同じになるようにしています。(i が 0 から 9 の範囲を動く。)
まず、x86 です。(不要な部分は編集しています。以下同様です。)
_f1: pushl %ebp movl %esp, %ebp movl 8(%ebp), %ecx testl %ecx, %ecx jle L4 movl _x, %edx xorl %eax, %eax L3: addl %eax, %edx incl %eax cmpl %ecx, %eax jne L3 movl %edx, _x L4: leave ret _f2: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax decl %eax js L10 movl _x, %edx L9: addl %eax, %edx decl %eax cmpl $-1, %eax jne L9 movl %edx, _x L10: leave ret確かに 0 と比較する方が、C コードの見た目は冗長なのに、アセンブリコードレベルでは 1 命令少なくなっています。しかし、肝心のループ部分の命令数は同じなので、やはり x86 ではあまり効果が無さそうです。
ARM ではどうでしょうか。v5 アーキテクチャ(926ES-J)、Little endian、ARM モードの結果です。
f1: cmp r0, #0 bxle lr ldr r1, .L7 mov r3, #0 ldr r2, [r1, #0] .L3: add r2, r2, r3 add r3, r3, #1 cmp r0, r3 bgt .L3 str r2, [r1, #0] bx lr f2: subs r0, r0, #1 bxmi lr ldr r2, .L14 ldr r3, [r2, #0] .L11: add r3, r3, r0 subs r0, r0, #1 bpl .L11 str r3, [r2, #0] bx lrARM では 2 命令の差が出ました。ループ部分の命令数も、0 と比較する方が 1 命令少ないです。ARM では、多少の効果は期待できるのかもしれません。
SH ではどうでしょうか。SH4、Little endian での結果です。
_f1: mov.l r14,@-r15 cmp/pl r4 bf/s .L6 mov r15,r14 mov.l .L8,r3 mov #0,r1 mov.l @r3,r2 .L3: dt r4 add r1,r2 bf/s .L3 add #1,r1 mov.l r2,@r3 .L6: mov r14,r15 rts mov.l @r15+,r14 _f2: mov r4,r7 add #-1,r7 mov.l r14,@-r15 cmp/pz r7 bf/s .L16 mov r15,r14 mov.l .L18,r6 mov r4,r2 mov #-1,r1 add #-2,r2 cmp/ge r1,r2 bf/s .L17 mov.l @r6,r3 .L12: dt r4 add r7,r3 bf/s .L12 add #-1,r7 mov.l r3,@r6 .L16: mov r14,r15 rts mov.l @r15+,r14SH では、0 と比較する方が 6 命令多くなりました。しかし、ループ部分の命令数は同じなので、これもほとんど関係無さそうです。bf/s というのは、遅延分岐で、次の命令が必ず実行されるそうです。私が SH に慣れてないということもあるのですが、パッと見、かなりトリッキーなコードに感じられます。(難しい…)
PPC ではどうでしょうか。Generic PowerPC、Little Endian での結果です。
f1: mr. 0,3 mtctr 0 blelr- 0 lis 11,x@ha li 9,0 lwz 0,x@l(11) .L3: add 0,0,9 addi 9,9,1 bdnz .L3 stw 0,x@l(11) blr f2: addic. 9,3,-1 bltlr- 0 addi 0,3,-2 lis 11,x@ha mtctr 3 cmpwi 7,0,-1 lwz 0,x@l(11) blt- 7,.L13 .L9: add 0,0,9 addi 9,9,-1 bdnz .L9 stw 0,x@l(11) blr .L13: li 10,1 mtctr 10 b .L9PPC でも、0 と比較する方が 5 命令多くなりました。しかしこれも、ループ部分は同じに見えます。
MIPS ではどうでしょうか。mips32、Little endian での結果です。
f1: blez $4,$L8 lw $5,%gp_rel(x)($28) move $3,$0 addu $5,$5,$3 $L7: addiu $3,$3,1 slt $2,$3,$4 bne $2,$0,$L7 addu $5,$5,$3 subu $5,$5,$3 sw $5,%gp_rel(x)($28) $L8: j $31 nop f2: addiu $4,$4,-1 bltz $4,$L15 lw $2,%gp_rel(x)($28) addu $2,$2,$4 $L14: addiu $4,$4,-1 bgez $4,$L14 addu $2,$2,$4 subu $2,$2,$4 sw $2,%gp_rel(x)($28) $L15: j $31 nopMIPS では、0 と比較する方がループ部分で 1 命令少なくなりました。
- まとめ
確かに命令数が減るプロセッサ (ARM、MIPS) もあるのですが、やはり全く変わらないものもある (x86、PPC、SH) という結果になりました。
個人的には、このような最適化が無意味とまでは言いませんが、for 文のイディオムを崩してまで積極的にマイクロオプティマイズする価値は低いのではないかと思います。例えば、0 と、 -1 など他の数、どちらの定数と比較しても良いような場合は、0 と比較するように意識して書いた方が良いかも、という程度だと思います。
コメント一覧
1. Posted by 齊藤 2009年11月13日 10:37
i >= 0 でなく i != 0 にすれば x86 でも 1 命令減ります。
2. Posted by 若槻 2009年11月13日 17:21
> i >= 0 でなく i != 0 にすれば x86 でも 1 命令減ります。
それだと、負数が入ってきた場合の挙動が 2 つのプログラムで変わってしまうのですよね。条件が i < N; ならばそこで止まりますが、I != 0; I-- だと無限ループになってしまうので。
どのみち想定外の引数なので、問題無いと言えば無いのですが。できるだけ 2 つのプログラムの挙動が変わらないようにしたかったのです。
それだと、負数が入ってきた場合の挙動が 2 つのプログラムで変わってしまうのですよね。条件が i < N; ならばそこで止まりますが、I != 0; I-- だと無限ループになってしまうので。
どのみち想定外の引数なので、問題無いと言えば無いのですが。できるだけ 2 つのプログラムの挙動が変わらないようにしたかったのです。
3. Posted by 若槻 2009年11月13日 17:30
おっと、なんかうっかり caps lock がかかって大文字になってしまいました。i < n と、i != 0; i-- です。
あと、正確には無限ループではありませんね。例えば -1 が入ってくると、符号が反転するまでループが回り続けるという意図でした。
あと、正確には無限ループではありませんね。例えば -1 が入ってくると、符号が反転するまでループが回り続けるという意図でした。
4. Posted by koba 2009年11月13日 19:01
x86で0との比較が-1との比較に置き換えられているのは、きっといろいろな歴史的な事情があるんだろうなあ。
SH4の場合、ソース上にはでてきていないループカウンタをわざわざr4に入れてデクリメントの命令を使っているのが興味深い。この方が速くなるのだろうか。
最近のCPUは組み込み向けでも同一クロックで複数命令を並列に実行するから、命令の個数を数えただけではどちらが速度的に有利かは断定できない。
SH4の場合、ソース上にはでてきていないループカウンタをわざわざr4に入れてデクリメントの命令を使っているのが興味深い。この方が速くなるのだろうか。
最近のCPUは組み込み向けでも同一クロックで複数命令を並列に実行するから、命令の個数を数えただけではどちらが速度的に有利かは断定できない。
5. Posted by 若槻 2009年11月13日 21:07
> x86で0との比較が-1との比較に置き換えられているのは、きっといろいろな歴史的な事情があるんだろうなあ。
>
> SH4の場合、ソース上にはでてきていないループカウンタをわざわざr4に入れてデクリメントの命令を使っているのが興味深い。この方が速くなるのだろうか。
なるほど、勉強になります。ありがとうございます。
> 最近のCPUは組み込み向けでも同一クロックで複数命令を並列に実行するから、命令の個数を数えただけではどちらが速度的に有利かは断定できない。
そうですね。そもそも前提となっている 「0 を特別扱いしている CPU が多い = 命令数が少なくて済む = 速い!」 という推論自体が、現代の CPU ではあまりあてにならないのでしょうね。
例えばこういうサイトが検索したらありましたが、
「最適化/比較は0と行うのが基本」
http://www.asahi-net.or.jp/~dp8t-asm/java/tips/OptCompareZero.html
このサイトでは、生成される JVM のバイトコードの命令数を根拠にしていますが、JVM などは JIT が入ってくるので、ますます性能に関する予測は難しくなると思います。
ちなみに twitter で、kmt_t さんが DalvikVM に言及していました。興味深いです。
http://twitter.com/kmt_t/status/5666038298
http://twitter.com/kmt_t/status/5666100371
http://twitter.com/kmt_t/status/5666297581
http://twitter.com/kmt_t/status/5666346306
>
> SH4の場合、ソース上にはでてきていないループカウンタをわざわざr4に入れてデクリメントの命令を使っているのが興味深い。この方が速くなるのだろうか。
なるほど、勉強になります。ありがとうございます。
> 最近のCPUは組み込み向けでも同一クロックで複数命令を並列に実行するから、命令の個数を数えただけではどちらが速度的に有利かは断定できない。
そうですね。そもそも前提となっている 「0 を特別扱いしている CPU が多い = 命令数が少なくて済む = 速い!」 という推論自体が、現代の CPU ではあまりあてにならないのでしょうね。
例えばこういうサイトが検索したらありましたが、
「最適化/比較は0と行うのが基本」
http://www.asahi-net.or.jp/~dp8t-asm/java/tips/OptCompareZero.html
このサイトでは、生成される JVM のバイトコードの命令数を根拠にしていますが、JVM などは JIT が入ってくるので、ますます性能に関する予測は難しくなると思います。
ちなみに twitter で、kmt_t さんが DalvikVM に言及していました。興味深いです。
http://twitter.com/kmt_t/status/5666038298
http://twitter.com/kmt_t/status/5666100371
http://twitter.com/kmt_t/status/5666297581
http://twitter.com/kmt_t/status/5666346306
6. Posted by 通りすがり 2018年01月02日 11:51
for( i=N; --i >=0;)
これが最速かと
これが最速かと
7. Posted by 名無し 2019年09月18日 22:35
> 負数が入ってきた場合の挙動が 2 つのプログラムで変わってしまうのですよね。
ガードすれば良いだけでは。
if (n >= 2) {
int i;
for (i = n - 1; i != 0; i--) {
x += i;
}
}
https://godbolt.org/z/u3RCNO
ガードすれば良いだけでは。
if (n >= 2) {
int i;
for (i = n - 1; i != 0; i--) {
x += i;
}
}
https://godbolt.org/z/u3RCNO