Entry

プログラミングメモ - 配列のインデックスアクセスとポインタアクセス

2009年02月05日

インデックスアクセスするよりもポインタでアクセスした方が速いよ,という話はよく聞くんだけれども,どのくらい差があるのだろうと思って,ちと調べてみました。大した差にはならなそうで,時間を計測してもあまり意味がなさそうだから,生成されるコードを見てみる。

調べたのは以下のコード。処理系は相変わらずの cygwin gcc 3.4.4 です。

int
main(int argc, char* argv[]) {
    int* ptr;
    int a[8192];
    int b[8192];
    int i;
    int j;
    
    // access by index
    for (i = 0; i < 8192; i++) {
        a[i] = 1;
    }
    // access by pointer
    for (ptr = b, j = 0; j < 8192; ptr++, j++) {
        *ptr = 1;
    }

    return 0;
}

配列を1で埋めるコード。説明するまでもありませんね。なんで0で埋めないかというと,0で埋める命令は CPU の命令に用意されているからです。CPU にズルされると困るので,0以外の値で埋めています。

で,アセンブリ出力(抜粋)。

    call    ___main
    movl    $0, -65564(%ebp)
L2:
    cmpl    $8191, -65564(%ebp)
    jg        L3
    movl    -65564(%ebp), %eax
    movl    $1, -32792(%ebp,%eax,4)
    leal    -65564(%ebp), %eax
    incl    (%eax)
    jmp    L2
L3:
    leal    -65560(%ebp), %eax
    movl    %eax, -12(%ebp)
    movl    $0, -65568(%ebp)
L5:
    cmpl    $8191, -65568(%ebp)
    jg      L6
    movl    -12(%ebp), %eax
    movl    $1, (%eax)
    leal    -12(%ebp), %eax
    addl    $4, (%eax)
    leal    -65568(%ebp), %eax
    incl    (%eax)
    jmp     L5
L6:
    movl    $0, %eax
    leave
    ret

このうち,1を代入しているのは以下の箇所なんですけど,どっちが速いんだろう。

    /* インデックスアクセス */
    movl    $1, -32792(%ebp,%eax,4)
    /* ポインタアクセス */
    movl    $1, (%eax)

インデックスアクセスする場合は,ベースアドレス(%ebp)と %eax の値からアドレスを計算して,そのアドレスに1をセットしている。一方,ポインタアクセスの方は %eax レジスタが指してるアドレスだけから直接代入しています。違いが出るとしたら,まずここなんだと思う。

ただ,上のコードの場合,ポインタアクセスする場合もループの終了条件をインデックス(j)で判断しなくちゃいけません。ループのたびに,j と ptr をどちらもインクリメントする必要があるので,その分オーバーヘッドになっている。

ちなみに,-O2 で最適化すると,こんな感じになります(抜粋してコメントつけた)。

    call    ___main
    xorl    %eax, %eax
    .p2align 4,,15
    /* インデックスアクセスループの開始 */
L5:
    movl    $1, %edx
    movl    %edx, -32776(%ebp,%eax,4)
    incl    %eax
    cmpl    $8191, %eax
    jle     L5
    leal    -65544(%ebp), %edx
    movl    $8191, %eax
    .p2align 4,,15
    /* ポインタアクセスループの開始 */
L9:
    movl    $1, (%edx)
    addl    $4, %edx  /* ポインタを進める */
    decl    %eax      /* %eax をデクリメント */
    jns     L9        /* %eax が0になってなかったら L9 にジャンプ */
    leave
    xorl    %eax, %eax
    ret

これは明らかにポインタアクセスの方が速い。インデックスアクセスで管理するインデックスは,メモリ番地を計算するモトになっているので,アクセス用の変数(i = %eax)の値を0から始めて,順番にインクリメントしていかなくちゃいけません。結果,ループの終了条件も cmpl 命令で即値 $8192 と比較しなくちゃいけない。これに対して,ポインタアクセスの終了判定は,単にループが8192回まわればいいだけなので,最初に %eax に $8192 を設定してデクリメントすることで,終了判断しています。cmpl 命令は,理屈で言うと $8192 と引き算した結果が0になるか(ZF が立つか)を見ているけれど,jns 命令は,引き算なしでデクリメントした結果,ゼロフラグが立ったかを見るだけなので,こっちの方が断然速い。ま,そんな劇的なもんじゃないんでしょうけど。

ちと今ウェーブレット変換のコードを書いているんですけど,この手の積分変換は膨大な量のループをくるくるやらなきゃいけないので,ここら辺をどう書くかでちと迷っていたのでした。やっぱりポインタアクセスだな,こりゃ。つか,アセンブリで書けってか。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN