分岐のないコード の

分岐のないコードについて

条件分岐の概念では、条件に基づいて分岐する命令ファミリーであるjccを紹介します。 jccは、条件が満たされたときだけ、プログラムの別の地点に実行を移します。

しかし、現代のCPUは高速で、多くの命令を並列に実行できます。 条件を実行時にチェックしている間、すべての処理を止めて待つのは、コストがかかりすぎます。

そのため、CPUは内部的には待ちません。 分岐予測器を使って条件の結果を推測し、予測した経路を_投機的に_実行し始めます。

予測が当たれば、分岐がなかったかのように実行が進みます。 しかし、予測が外れると、CPUは予測した経路で_行った処理を破棄_して、正しい経路でやり直さなければなりません。

これは分岐予測ミスと呼ばれ、遅延を伴うためコストが高くつきます。

分岐の予測が難しいと、こうした予測ミスが積み重なります。 そういう場合は、分岐を完全になくして、条件に関係なく同じ命令が実行されるようにするほうがよいことがあります。 jccを使わずに値の選択を行うコードは、ブランチレスと呼ばれます。

コードの分岐を減らしたり、ある分岐の予測をしやすくしたりする書き方には、いくつかの方法があります。 とくにx86-64には、ブランチレスコードを書くためによく使われる2つの命令ファミリーがあります。

条件付き移動

cmovccの命令ファミリーは、特定の条件が満たされたときだけ、転送元オペランドを転送先にコピーします。 それ以外の場合、転送先は変わりません。

ccというサフィックスは、jccと同じ命名規則に従い、意味も同じです。

規則はjccと似ています。

1. lとgは符号ありの比較に使います。bとaは符号なしに使います。
2. サフィックスにeを付けると、等しい場合も含まれます。
3. nを付けると、条件が否定されます。
4. フラグがセットされていることを参照する変種もあります。 たとえばcmovzやcmovcです。

rdiにある符号あり整数の絶対値を求めてraxに返すことを考えてみましょう。 jccで書くと、この関数は2つの経路のどちらかを選びます。

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

cmovccで書くと、2つの候補値がどちらも無条件に計算され、条件付き移動がそのうちの一方を選びます。

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

ブランチレスの版は、いつも同じ命令を実行します。 予測器が推測するjccはありません。

cmovccの転送先はレジスタでなければなりません。 転送元にはレジスタかメモリの場所を指定できますが、即値は指定できません。

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

条件付きセット

setccの命令ファミリーは、特定の条件が満たされたときは転送先オペランドを1に、それ以外のときは0に設定します。 転送先は常に_8ビットのオペランド_です。

ccサフィックスは、jccやcmovccと同じ命名規則に従います。 たとえばsetzは、ZF == 1なら転送先を1に、それ以外なら0に設定します。

転送先が8ビットなので、より幅の広い値が必要なときは、setccの後にmovzxを続けるのが一般的です。

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

これは、比較の結果を整数の0か1に変える際によく使われるイディオムです。

ブランチレスコードを使うべきとき

ブランチレスコードが、分岐のあるコードよりいつも速いわけではありません。 分岐の予測が非常にしやすいときは、予測器がほぼ毎回当てるので、jccのコストは実質ゼロです。 そうした分岐を置き換えるブランチレスコードは、候補の計算をいつも両方実行するため、かえって遅くなります。

ループカウンターはその典型例です。 rdiから始まるrsi個の64ビット整数を合計する関数を考えてみましょう。

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

これはまさに分岐予測器が得意とするパターンなので、sum_arrayがいくつの要素を処理しても、この分岐には実質的にコストがかかりません。

ブランチレスコードが効果を発揮するのは、分岐の予測が難しいときや、入力に関係なく一定のタイミングが求められるときです。