問題タブ [branch-prediction]

いくつかのアセンブリ コードを考えると、分岐の 90% を取得する必要があることがわかっています。

私は分岐条件についての知識がありません。また、各分岐の実行可否の決定は、確率のみに基づいて行う必要があります。

ブランチのオフセットは、正または負にすることができます。

それを行う正しいアルゴリズムは何ですか？

Intelによると、分岐の削除は、タイトなループで使用する C コードを最適化する最も効果的な方法の 1 つです。ただし、リンクされたページの例では、ループのアンロールと不変ブランチのループ外への移動のみがカバーされています。

最適化のための分岐削除の追加のさまざまな (前後の) 例はありますか?

そこで今朝、初めてベンチマークをいじってみることにしました。

「do-end」ブロック形式と「{ }」形式のコードの速度の違いに興味がありました。

そこで、ベンチマーク コードを Proc に格納して、複数回連続して呼び出すことができるようにしました。

一度実行したときに期待される結果。

しかし、もう一度実行しました。

私には、これは私が期待しているものとは正反対のように見えます。分岐予測の概念に精通しています。これは分岐予測の典型的な例ですか? そうでない場合は、何ですか？このような不正確さを防ぐ方法はありますか (これが 1 つと見なされる場合でも)?

編集:いくつかの提案の後、このコードを30回以上実行しました。多くの場合、2 つの結果が交互に表示されます。データのサンプルは次の場所にあります。

gist.github.com/TheLarkInn/5599676

私はそれを使用してStackOverflowを読みました

分岐の予測ミスの影響を受けやすいため、非効率的である可能性があります (たとえば、この質問を参照してください)。

-constructもswitch同様です。たとえば、

この点で違いはありますか (3 つの可能性を考慮したという事実以外に)?

これは、低レベルの最適化手法について説明し、著者が高価な分割を安価な比較に変換する例を示す素晴らしい記事です。 https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

クリックしたくない人のために、基本的に彼はこれを変換しました：

これに：

その結果、最大 6 倍のスピードアップが実現しました。

比較は非常に安価ですが、ブランチはパイプラインの停止を引き起こす可能性があるため、非常に高価であるといつも聞いています。分岐に関する一般的な通念のため、このようなアプローチを考えたことはありませんでした。

この場合、分岐がボトルネックにならないのはなぜですか? それぞれの比較の直後に戻るからですか? ここのコード サイズが小さいため、プロセッサが予測を誤る可能性があまりないためでしょうか。それがボトルネックになり、部門のコストを支配し始めるのはどのような場合ですか? 著者はこれについて決して話しません。

安価な比較と高価なブランチの間の明らかな競合を解決できる人はいますか? もちろん、最適化の黄金律は、常に測定しなければならないということです。ただし、コードを高速化するための新しいアプローチを考え出すときに、比較を賢く使用できるように、この問題についてある程度の直感を持っているとよいでしょう。

ありがとう！

現在、SSE-2 命令を使用した x86-64 アセンブリを使用してstrlen()、 、 などの C99 標準ライブラリ文字列関数の高度に最適化されたバージョンをコーディングしています。memset()

これまでのところ、パフォーマンスの点で優れた結果を得ることができましたが、さらに最適化しようとすると、奇妙な動作が発生することがあります。

たとえば、いくつかの単純な命令を追加または削除したり、ジャンプで使用されるローカル ラベルを単純に再編成したりすると、全体的なパフォーマンスが完全に低下します。そして、コードに関してはまったく理由がありません。

だから私の推測では、コードの配置や、予測を誤った分岐に問題があると思います。

同じアーキテクチャ (x86-64) でも、CPU が異なれば分岐予測のアルゴリズムも異なることがわかっています。

しかし、x86-64 で高パフォーマンスを実現するために開発する場合、コードのアライメントと分岐予測に関する一般的なアドバイスはありますか?

特に位置合わせについては、ジャンプ命令で使用されるすべてのラベルが DWORD で位置合わせされていることを確認する必要がありますか?

.label:前のコードでは、次のように の前に align ディレクティブを使用する必要があります。

もしそうなら、SSE-2 を使用する場合、DWORD に合わせるだけで十分ですか?

分岐予測については、CPU を助けるために、ジャンプ命令で使用されるラベルを整理する「好ましい」方法はありますか? それとも、今日の CPU は、実行時に分岐の回数を数えることで判断できるほど賢いのでしょうか?

編集

わかりました、ここに具体的な例があります - これstrlen()が SSE-2 の始まりです:

1000 文字の文字列で 10'000'000 回実行すると、約 0.48 秒かかります。これは問題ありません。
ただし、NULL 文字列の入力はチェックされません。明らかに、簡単なチェックを追加します。

同じテストで、0.59 秒で実行されます。しかし、このチェックの後にコードを調整すると:

元のパフォーマンスが戻ってきました。4 は何も変わらないので、アライメントには 8 を使用しました。
誰かがこれを説明し、いつコードセクションを整列するか、または整列しないかについてアドバイスを与えることができますか?

編集2

もちろん、すべてのブランチ ターゲットを揃えるほど単純ではありません。私がそうすると、上記のような特定の場合を除いて、パフォーマンスは通常悪化します。