比較命令の高速化

#define SAMPLE_NUM 576
int xr_max( float xr[SAMPLE_NUM]){
    int i;
    float x, max = 0.0;

    for ( i = 0; i < SAMPLE_NUM; i++ ){
        x = fabs(xr[i]);
        if( x > max )
            max = x;
    }
    return (int)max;
}

を最適化します. (午後のこ〜だのソースの一部分です)
VC++6.0でのコンパイルは次のようになりました.

_xr_max:
_x$ = 8
_xr$ = 8
    fld     DWORD PTR _0
    mov     ecx, DWORD PTR _xr$[esp-4]
    mov     edx, 576
$L2050:
    fld     DWORD PTR [ecx]
    fabs
    fst     DWORD PTR _x$[esp-4]

    fcomp   ST(1)
    fnstsw  ax
    test    ah, 41h
    jne     SHORT $L2051
    fstp    ST(0)

    fld     DWORD PTR _x$[esp-4]
$L2051:
    add     ecx, 4
    dec     edx
    jne     SHORT $L2050

    call    __ftol
    ret

私のマシンではこれを約13000clkで実行します (当然この値はCPUやメモリ等によって大幅に変わるので飽くまで目安です). 比較の部分でtest ah,41hが使われていますが, ペアリングなどの関係でand ah,41hにすべきだそうです.
test eax,4100hも考えられますが, K6では確か遅くなったような気がします.

では fcompの代わりに整数演算命令を使ってみます.

    push    ebx
_P=4*1
    mov    ebx,[esp+_P+4]
    mov    ecx,576
    xor    eax,eax
xrm_lp:
        mov     edx,[ebx]
    add    ebx,4
        and     edx,7FFFFFFFh
    cmp    edx,eax
    jb    short xrm_F0
    mov    eax,edx
xrm_F0:
    dec    ecx
    jnz    short xrm_lp
    push    eax
    fld    dword ptr [esp]    ;(1)
        fsub    dword ptr [_05] ;=0.5
    fistp    dword ptr [esp]    ;(2)
    pop    eax        ;(3)
    pop    ebx
    ret

7FFFFFFFhとandを取ることで最上位bitがクリアされ浮動小数として正の値になります. (1)〜(3)でeaxに格納されている浮動小数の値を整数に変換します. fistpによる整数への変換方法はFPUのコントロールレジスタの値によって代わりますが, 四捨五入モードの場合は0.5を引いておけば int へのキャスト(切捨て)とほぼ同じ動作をします. この場合だと約2500clkで動作しました. 4〜5倍の高速化です. FPUの比較命令がいかに遅いかが分かります.

補足

新井俊一さんから, 最大値 / 最小値を求める部分では分岐予測が外れることが多いので分岐しない方法 [後日, 説明予定] を使った方がよいのでは?とのメールを頂きました. 確かに一般の場合はその通りです. ただこのルーチンを実際に使っていた部分では, xr[]はほぼ単調減少することが分かっていたので分岐予測がかなりの確率でヒットするだろうと推測していました. そのため単純な分岐を採用しました. とは言え, 何も説明せずにいたのは私のミスです. 申し訳ありません.

次に3D Now!命令を使ってみます.

    femms
    mov    edx,[esp+4]
    mov    ecx,576/4
    movq    mm3,[forAbs3DN]    ;mm3=[7FFFFFFF:7FFFFFFF]
    pfsub    mm0,mm0        ;mm0=[0:0]
    movq    mm1,mm3
xr3_lp:
    pand    mm1,[edx]    ;mm1=[|xr[i+1]|:|xr[i]|]
    movq    mm2,mm3        ;mm2=for abs
    pand    mm2,[edx+8]    ;mm2=[|xr[i+3]|:|xr[i+2]|]
    add    edx,16
    pfmax    mm0,mm1        ;mm0=max(mm0,mm1)
    movq    mm1,mm3        ;mm1=for abs
    pfmax    mm0,mm2        ;mm0=max(mm0,mm2)
    loop    xr3_lp

    pf2id    mm0,mm0
    movd    eax,mm0
    psrlq    mm0,32
    movd    ecx,mm0
    cmp    eax,ecx
    jae    short xr3_exit
    mov    eax,ecx
xr3_exit:
    femms
    ret

pfmaxという命令がありますから, それを使います. 絶対値を求めるところで, 値を読み込んでからandをするよりは, 先にレジスタに7FFFFFFFhを入れておいてそれとメモリとのandを取るほうが依存関係が弱くなるのでこうしました. なお, pand命令どうしはペアリングできません. この場合約1000clkで動作します. 標準の方法に比べて10倍以上も速いです. 最後の上位32bitと下位32bitの大きい方を取る部分が少しもたついてます. うまいやり方があったら教えてください.

[Back]

御意見は光成滋生<herumi@nifty.com>までお願いします