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 モードでコンパイルしています。)



例題プログラムは全て共通です。
#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     lr
ARM では 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+,r14
SH では、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 .L9
PPC でも、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
        nop
MIPS では、0 と比較する方がループ部分で 1 命令少なくなりました。

- まとめ

確かに命令数が減るプロセッサ (ARM、MIPS) もあるのですが、やはり全く変わらないものもある (x86、PPC、SH) という結果になりました。
個人的には、このような最適化が無意味とまでは言いませんが、for 文のイディオムを崩してまで積極的にマイクロオプティマイズする価値は低いのではないかと思います。例えば、0 と、 -1 など他の数、どちらの定数と比較しても良いような場合は、0 と比較するように意識して書いた方が良いかも、という程度だと思います。

トラックバックURL

コメント一覧

1. Posted by 齊藤   2009年11月13日 10:37
3 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 つのプログラムの挙動が変わらないようにしたかったのです。
3. Posted by 若槻   2009年11月13日 17:30
おっと、なんかうっかり caps lock がかかって大文字になってしまいました。i < n と、i != 0; i-- です。

あと、正確には無限ループではありませんね。例えば -1 が入ってくると、符号が反転するまでループが回り続けるという意図でした。
4. Posted by koba   2009年11月13日 19:01
x86で0との比較が-1との比較に置き換えられているのは、きっといろいろな歴史的な事情があるんだろうなあ。

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

コメントする

名前
URL
 
  絵文字
 
 
記事検索
最新コメント
アクセスカウンター
  • 今日:
  • 昨日:
  • 累計:

QRコード
QRコード