« x86カルトクイズ | メイン | ηTペアリングの高速な実装 »

x86カルトクイズ(解答編)

問題編はこちらのx86カルトクイズです.

Q1

[乗算の削減]
lea    eax, [eax + eax*8]
lea    eax, [eax + eax*4]

45 = 9 * 5 = (8 + 1) * (4 + 1)を利用する.乗算命令が速くなったとはいえ,まだadd/sub/shift/leaの組み合わせを使った方が速いことが多い.

Q2

[条件分岐の削減]
cdq
xor    eax, edx
sub    eax, edx

条件分岐は可能な限り使わない.次の二つの恒等式

-x = x ^ (-1) - (-1)
 x = x ^ 0 - 0

unsigned int m = (x < 0) ? -1 : 0

を組み合わせることで絶対値を

unsigned int m = x >> 31;
return x ^ m - m;

と実現する.ここでmを取得する部分は

mov    edx, eax
sar    edx, 31

であるが,これに限り32bit除算の準備のために用意されたcdqを使うことができる.

cdq ⇔ edx = eax < 0 ? -1 : 0

P4系ではどちらも同じμOPに分解されるがcdqの方がコードサイズは小さくてすむ.

Q3

[μOPでの挙動とパーシャルレジスタストール]
/* 3.1 */
.label:
...
shr    eax, 1
shr    eax, 1
jnz    .label

Core系では二つの1bitシフトに分割したほうが速くなることがある.それまでのP4では分割しない方がよい.
P4以前では分割しない方がよい.また8倍までの左シフトに対してはshlよりもaddを使った方がよいことが多い.

3.2はdecに変えない方がよい.sub ecx, 1とdec ecxの違いはecx == 0のとき前者はCF(キャリーフラグ) = 1となるが,後者はCFが変化しない点にある.そのためdec/incはフラグに対してパーシャルレジスタストールを起こし遅くなる.バイト長が長くなるがsub/addを使うべきである.

Q4

[バイトコード]

処理内容は変わらないが,前者のコードが8B 0C 45 00000000と7byteなのに対して,後者は8B 0C 00と3byteですむ.アドレス生成回路としてもシフトが使われるか,加算が使われるかの差があるかもしれない.NASMでは前者のニーモニックを記述しても自動的に後者に変換される.XbyakでもReg32.optimize()において同様の処理を行っている.

Q5

[浮動小数と整数演算]

整数として加算するのでxm0の値は0x3fc00000,floatとしては12.0である.

Q6

[浮動小数乗算の整数加算への置き換え]

整数として0x01800000の加算は,xのfloatとしての指数部に3を足すことになる.したがって一般にこの操作はxのfloatとしての値を8倍することになる.これはFLT_MIN(= 0x00800000) <= |x| <= FLT_MAX(= 0x7f7fffff) / 8の範囲で正しい.

通常ならmulss xm0, [_8f]を使うが,padddの方がレイテンシが短い.ただし0は0ではなくFLT_MIN * 4になる.またデノーマル数(0 < |x| < FLT_MIN),あるいは処理後がオーバーフローする(FLT_MAX/8 < |x|)ときも値が異なることに注意する.

Q7

[bsrの注意事項]
mov    edx, [esp+4]
bsr    eax, edx
cmovz  eax, edx
ret

bsr命令は入力値edxが0のとき出力値eaxが不定となる仕様であるため単純には使えない.
そのため

    mov    eax, [esp+4]
    test   eax, eax
    jz     .skip
    bsr    eax, eax
    jmp    .exit
.skip:
    mov    eax, [0の時の特殊値]
.exit:

という形にしたくなる.が,bsrは入力値が0のときZF(ゼロフラグ)を1にする.これを利用すれば,ZF == 1のときのみ移動する条件付き移動命令cmovzを使って

    mov    edx, [esp+4]
    bsr    eax, edx
    cmovz  eax, [0の時の特殊値]

とできる.更に特殊値が0ならば答えのように短くできる.

Q8

[Windowsにおけるスタックの仕様]

Windowsではespの指す部分がコミットされていない場合,アクセスがあった時点で4KB単位でコミットされる.その際コミット領域が連続している必要がある.したがって確実にコミットさせるために

sub    esp, 8192
mov   [esp+4096], eax ; dummy write
mov   [esp], eax
add    esp, 8192

などのように4KBずつアクセス(readでも可)しておく必要がある.

Q9

[浮動小数から整数への変換]

floatからintへのキャストがボトルネックとなる.

通常使う四捨五入では0.5は常に切り上げとなる.そのため統計的にわずかであるが演算結果が大きくなってしまう.これを防ぐために浮動小数から整数へのデフォルトの変換命令は0.5を偶数方向に丸める四捨五入を採用している.たとえば1.5は2,2.5は2,3.5は4となる.

だがこの仕様はCの常に0方向に切り捨てる仕様と相容れない.そのためキャストごとにFPUの制御モードを変更する必要があり,そのコストが非常に大きい.

FPUの場合

ループの外で制御モードを変更する.
cwOrg dw ; デフォルトのFPU制御ワード
cwTrunc dw ; cwOrg |= (3 << 10) ; truncate to 0
 
; ループ前
fldcw    [cwTrunc] ; 丸めモードを0への切り捨てに変更する
; ループ内
fistp    dword [...]
; ループ後
fldcw    [cwOrg] ; デフォルトモードに復元

SSEの場合

同様にループの外で制御モードを変更する.
mxcsrOrg dd ; デフォルトのMXCSRレジスタ
mxcsrTrunc dd msxcrOrg |= (3 << 11) ; truncate to 0
; ループ前
ldmscsr    [mxcsrTrunc] ; 丸めモードを0への切り捨てに変更する
; ループ内
cvtps2pi [...] ; float x 2 → int x 2
; ループ後
ldmxcsr    [mxcsrOrg] ; デフォルトモードに復元

ただし,FPU制御ワードの変更に比べてmscsrの変更はコストが大きい.ループが小さい場合はSSEを使わずFPUで閉じた方がよいケースもある.

SSE2の場合

上記を回避する専用命令が追加された.
cvttps2piを使えばMSCSRレジスタを変更することなく切り捨てを行える

SSE3搭載CPUでFPUを使う場合

上記を回避する専用命令が追加された.
fisttpを使えばFPU制御ワードを変更することなく切り捨てを行える

Q10

[ビット演算]

xに対してxを超えない最大の2巾の指数を求めるにはQ7のbsrを使えばよい.
今回はx>0が保証されているため例外処理は不要である.ループアンロールなどはここではしない.

proc log2A
    mov   edx, [esp+4]
    mov   eax, [esp+8]
    mov   ecx, [esp+12]
    push  ebx
.lp:
    mov   ebx, [eax]
    add   eax, byte 4
    bsr   ebx, ebx
    mov   [edx], ebx
    add   edx, byte 4
    sub   ecx, byte 1
    jnz   .lp
    pop   ebx
    ret

またxを2e * f(1 <= f < 2)という形で考えると,bsrはeを求めることに相当する.したがってxをdoubleに変換し,その指数部を取り出す方法もある.doubleの仮数部は11bit,指数部は52bitなので52(=32+20)bit右シフトした後,1023を引けばよい.bsrはレイテンシが大きいのでこちらの方が速い.

_1023   dd 1023, 1023, 1023, 1023
 
proc log2B
    mov        edx, [esp+4]
    mov        eax, [esp+8]
    mov        ecx, [esp+12]
.lp:
    cvtpi2pd   xm0, [eax]      ; [D1_H:D1_L:D0_H:D0_L]
    cvtpi2pd   xm1, [eax+8]    ; [D3_H:D3_L:D2_H:D2_L]
    add        eax, 16
    shufps     xm0, xm1, (3 * 64 + 1 * 16 + 3 * 4 + 1)
                               ; [D3_H:D2_H:D1_H:D0_H]
                               ; 32bit右シフト相当
    psrld      xm0, 20         ; 20bit右シフト
    psubd      xm0, [_1023]
    movaps     [edx], xm0
    add        edx, 16
    sub        ecx, byte 4
    jnz        .lp
    ret

なお,もし0 < x < (1 << 23)という条件があるならばdoubleではなくfloatに変換することで更に効率よく処理を行える.floatの仮数部は8bit,指数部は23bitなので23bit右シフトした後,127を引けばよい.

_127 dd 127, 127, 127, 127
 
proc    log2C
    mov        edx, [esp+4]
    mov        eax, [esp+8]
    mov        ecx, [esp+12]
.lp:
    cvtpi2ps   xm0, [eax]      ; [*:*:F1:F0]
    cvtpi2ps   xm1, [eax + 8]  ; [*:*:F3:F2]
    punpckldq  xm0, xm1        ; [F3:F2:F1:F0]
    add        eax, 16
    psrld      xm0, 23
    psubd      xm0, [_127]
    movaps     [edx], xm0
    add        edx, 16
    sub        ecx, byte 4
    jnz        .lp
    ret

よく「アセンブラを使っても最近の最適化コンパイラに勝てない」という意見が聞かれるが,それは単に「自分では確認せず,おうむ返しをしている」か,「コンパイラと同じ(or それ以下の)コードを書いている」かのどちらかであろう.もちろん「コストに見合わない」こともあるがそれはまた別の話である.

一般に最適化ではQ6, 7, 10のような,コンパイラで自動生成されることのない部分を考慮しつつ,さぼれるだけさぼれるロジックを考える.そしてそういうロジックを自在に記述するためにアセンブリ言語やイントリンジック関数を使う.実際,これらのテクニックは音声や動画のコーデックの開発でしばしば使われる.その際Q3などの知識がクリティカルとなることはまずない.瑣末な知識を覚えるよりも(無論覚えるに越したことはない --- 実践に暗記は必要である),常に代替ロジックが無いかを考える方がよりよいコードに繋がると思う.

コメント (4)

とっこ:

Q3で、1bitシフトに分割した方が速いのはCoreでなくPrescottではないですか?
Coreで多ビットシフトが遅くなったという話も聞きませんし、
Prescottは1bitシフトが高速ですし。

それにしても難しい。こういう問題を見られたことは嬉しいですが、
何だか自信をなくしてしまいます(^^;

へるみ:

>Prescottではないですか?
ご指摘ありがとうございます.すいません,書き間違いです.「P4から分割した方がよい」という知識は持っていて,Coreではどうだろうと試してみて,Coreでもやっぱり速くなったのでそちらに意識がいってしまいました.

試したコードはこんなものです(shr eax, 2でも同様の結果を得ました).

proc    func1
        mov        eax, [esp+4]
        shr        eax, 1
        shr        eax, 1
        shr        eax, 1
        shr        eax, 1
        ret
 
proc    func2
        mov        eax, [esp+4]
        shr        eax, 4
        ret
ingkt:

Q10の解答でbsr ebx, [eax]とせず別にmovしているのは何か意味があるんですか?

へるみ:

コメントスパムに紛れてコメントが遅れました.申し訳ありません.

>何か意味があるんですか?
本当だ,この場合は分ける必要は無いですね.
最初x == 0のときの例外処理を付けようとして分けておいたのがそのままになっていました.
ご指摘ありがとうございました.

コメントを投稿

(いままで、ここでコメントしたことがないときは、コメントを表示する前にこのブログのオーナーの承認が必要になることがあります。承認されるまではコメントは表示されません。そのときはしばらく待ってください。)