[解決済み] GCC 5.4.0での高価なジャンプ

質問

次のような関数がありました（重要な部分のみ表示）。

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) && (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

このように書くと、私のマシンでは、この関数に ~34ms かかりました。条件をboolの乗算に変更した後（コードはこのようになります）。

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) * (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

を実行したところ、実行時間が約19msに短縮されました。

使用したコンパイラはGCC 5.4.0で -O3 を確認した後 godbolt.orgを使用して生成されたasmのコードです。 最初の例ではジャンプが生成され、2番目の例では生成されないことがわかりました。GCC 6.2.0を試すことにしましたが、GCC 7はもうジャンプ命令を生成しないようです。

この高速化の方法を見つけるのは、かなりむずかしく、かなりの時間がかかりました。なぜコンパイラはこのような挙動をするのでしょうか？また、プログラマーが気をつけるべきことなのでしょうか？また、このようなことは他にもあるのでしょうか？

解決方法は？

論理AND演算子( && つまり、最初の比較が真と評価された場合にのみ、2番目のテストが行われるのです。つまり、2回目のテストは、1回目の比較が「true」と評価された場合のみ行われます。例えば、次のようなコードを考えてみましょう。

if ((p != nullptr) && (p->first > 0))

ポインタを参照解除する前に、ポインタが非NULLであることを確認する必要があります。もしこの はなかった。 を短絡的に評価すると、NULLポインタをデリファレンスしてしまうので、未定義の動作になってしまいます。

また、条件の評価が高価な処理である場合、短絡的な評価によって性能が向上する可能性もある。たとえば、以下のような場合だ。

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

もし DoLengthyCheck1 が失敗したら DoLengthyCheck2 .

しかし、結果のバイナリでは、短絡演算はしばしば2分岐となる。これは、コンパイラがこれらのセマンティクスを保持する最も簡単な方法だからである。(これは、コンパイラがこれらのセマンティクスを維持するための最も簡単な方法だからです（これは、コインの反対側で、短絡的な評価が時々 抑制する 最適化の可能性があります)。このことは、あなたの if ステートメントをGCC 5.4で実行しました。

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L5

    cmp     ax, 478           ; (l[i + shift] < 479)
    ja      .L5

    add     r8d, 1            ; nontopOverlap++

ここでは、2つの比較( cmp 命令)があり、それぞれに別の条件ジャンプ/分岐( ja または、上記の場合はジャンプ)。

一般に、分岐は遅いのでタイトなループでは避けるべきとされています。これは、8088（フェッチ時間が遅く、プリフェッチキュー（命令キャッシュに匹敵）が非常に小さく、分岐予測が全くできないため、分岐を行うとキャッシュをダンプする必要があった）から最新の実装（長いパイプラインのため予測ミスの分岐も同様に高価）まで、事実上すべての x86 プロセッサで当てはまりました。ここで、ちょっとした注意点があることに注意してください。Pentium Pro以降の最新のプロセッサは、分岐のコストを最小化するように設計された高度な分岐予測エンジンを搭載しています。分岐の方向が適切に予測できれば、コストは最小になります。たいていの場合、これはうまくいくのですが、もし、分岐予測エンジンが味方してくれない病的なケースに陥った場合。 コードが極端に遅くなることがあります。 . 配列がソートされていないとのことなので、おそらくこのような状況なのでしょう。

ベンチマークでは && を使用した * を使用すると、コードが明らかに速くなります。その理由は、オブジェクトコードの該当箇所を比較すると明らかです。

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    xor     r15d, r15d        ; (curr[i] < 479)
    cmp     r13w, 478
    setbe   r15b

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     ax, 478
    setbe   r14b

    imul    r14d, r15d        ; meld results of the two comparisons

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

があるので、この方が速いというのはちょっと直感に反しています。 より という命令もありますが、最適化というのはそういうものです。同じ比較をしている ( cmp ) が実行されていますが、今度はそれぞれの前に xor を、その後に setbe . XORは、レジスタをクリアするための標準的なトリックに過ぎません。その setbe は、フラグの値に基づいてビットをセットするx86の命令で、分岐のないコードを実装するためによく使われる。ここでは setbe の逆バージョンです。 ja . これは、比較結果が等しいかそれ以下であった場合、目的レジスタに 1 をセットします（レジスタは事前にゼロにされているので、それ以外は 0 になります）。 ja は、比較対象が上であった場合に分岐した。この2つの値が r15b と r14b レジスタを使用し、それらを掛け合わせます。 imul . 乗算は伝統的に比較的遅い処理でしたが、最近のプロセッサでは非常に速く、2バイトサイズの値を乗算するだけなので、特に速くなるでしょう。

乗算をビット単位の AND 演算子に置き換えることも同様に簡単にできます ( & ) は、短絡的な評価を行いません。これにより、コードがより明確になり、コンパイラが一般的に認識するパターンとなります。しかし、あなたのコードでこれを行い、GCC 5.4でコンパイルすると、最初のブランチを出力し続けます。

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L4

    cmp     ax, 478           ; (l[i + shift] < 479)
    setbe   r14b

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

技術的にこの方法でコードを出力しなければならない理由はないのですが、何らかの理由で内部ヒューリスティックがこの方が速いと言っているのです。それは となる しかし、分岐予測が成功するよりも失敗する方が多い場合は、より遅くなる可能性があります。

新しい世代のコンパイラ（やClangなどの他のコンパイラ）はこのルールを知っていて、手で最適化することで求めていたのと同じコードを生成するために、このルールを使う場合があります。私は定期的にClangが && を使った場合と同じコードが出力されます。 & . 以下は、GCC 6.2 の出力で、あなたのコードが通常の && 演算子を使用します。

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L7

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r14b

    add     esi, r14d         ; nontopOverlap++

このように巧妙な これ は！？これは、符号付き条件( jg と setle ) とは対照的に、符号なし条件 ( ja と setbe ) が、これは重要ではありません。古いバージョンと同じように最初の条件に対して比較と分岐を行い、同じように setCC 命令は、2つ目の条件に対して分岐のないコードを生成しますが、インクリメントを行う方法はより効率的になっています。のフラグを設定するために2回目の冗長な比較を行うのではなく、1回目の比較でフラグを設定します。 sbb という知識を利用しています。 r14d は1か0のどちらかになり、単純に無条件にこの値を nontopOverlap . もし r14d そうでない場合は1が加算され、まさに想定された通りになります。

GCC 6.2 では、実際に より を使用すると、効率的なコードになります。 && 演算子よりも、ビット単位の & 演算子を使用します。

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L6

    cmp     eax, 478          ; (l[i + shift] < 479)
    setle   r14b

    cmp     r14b, 1           ; nontopOverlap++
    sbb     esi, -1

ブランチと条件セットはまだ残っていますが、今度はあまり賢くない方法でインクリメントする方法に戻りました。 nontopOverlap . これは、なぜコンパイラを出し抜こうとするときに注意しなければならないかという重要な教訓です。

しかし、もしあなたが 証明する ベンチマークで分岐コードの方が実際に遅いことを確認したら、コンパイラーを出し抜くのもいいかもしれません。そのためには、ディスアセンブルを注意深く調べ、コンパイラを新しいバージョンにアップグレードしたときに、自分の判断を再評価できるように準備しておく必要があります。例えば、あなたが持っているコードは、次のように書き換えることができます。

nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));

はありません。 if また、大半のコンパイラはこのために分岐コードを生成することは考えません。GCCも例外ではありません。すべてのバージョンで次のようなものが生成されます。

    movzx   r14d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r14d, 478         ; (curr[i] < 479)
    setle   r15b

    xor     r13d, r13d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r13b

    and     r13d, r15d        ; meld results of the two comparisons
    add     esi, r13d         ; nontopOverlap++

これまでの例を見てきた人なら、これはとても見慣れたものに見えるはずです。どちらの比較も枝分かれしない方法で行われ、中間結果は and を一緒に編集し、この結果（0か1のどちらかになる）を add を編集して nontopOverlap . もし、分岐のないコードが欲しいなら、これで事実上、確実に手に入れることができます。

GCC 7はさらに賢くなりました。GCC 7はさらに賢くなり、上記のトリックに対して、オリジナルのコードとほとんど同じコード(命令の若干の並べ替えを除く)を生成するようになりました。ですから、あなたの質問に対する答えは "なぜコンパイラはこのような動作をするのでしょうか?"。 それはおそらく、彼らが完璧ではないからでしょう。ヒューリスティックを使って可能な限り最適なコードを生成しようとしますが、常に最良の判断ができるわけではありません。しかし、少なくとも、時間とともに賢くなることはできます。

この状況に対する一つの見方として、分岐するコードの方が ベストケース の性能を発揮します。分岐予測が成功すれば、不要な演算をスキップすることで、実行時間が若干早くなる。しかし、分岐のないコードの方が ワーストケース の性能を発揮します。分岐予測に失敗した場合、分岐を回避するために必要な命令を追加で数回実行すると 間違いなく の方が、予測ミスのある分岐よりも高速です。どんなに賢いコンパイラでも、この選択は難しいでしょう。

プログラマーが気をつけるべきことなのか、という質問に対しては、マイクロ最適化によって高速化しようとしている特定のホットループを除けば、答えはほぼ間違いなく「ノー」です。ただし、マイクロ最適化によって高速化しようとしている特定のホットループは例外です。前にも言ったように、コンパイラの新しいバージョンに更新したときに、これらの決定を再検討する用意をしておいてください。トリッキーなコードに対してバカなことをするかもしれませんし、最適化のヒューリスティックを十分に変えて、元のコードに戻ることができるかもしれません。徹底的にコメントしましょう