[解決済み] if...else if文を確率で並べるとどのような効果がありますか？

質問

具体的には、もし私が一連の if ... else if と評価される相対的な確率があらかじめわかっています。 true 確率の高い順に並べると、実行時間にどれくらいの差が出るのでしょうか？例えば、このようにした方がいいでしょうか。

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

をこれか？

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

ソートされた方が速いのは明らかですが、読みやすさや副作用の存在を考えると、最適でない並び方をしたい場合もあります。また、CPUが分岐予測をどの程度行うかは、実際にコードを動かしてみないとわからない。

ということで、具体的なケースを想定して、自分なりの答えを出しましたが、他の方のご意見・ご感想も伺えればと思います。

重要：この質問は if 文は、プログラムの動作に他の影響を与えることなく、任意に並べ替えが可能です。私の答えでは、3つの条件テストは相互に排他的であり、副作用は生じません。確かに、ある目的の動作を達成するために、ある順序で文を評価しなければならないのであれば、効率の問題は無意味です。

どのように解決するのですか？

一般的なルールとして、すべてのIntel CPUは、最初に見たとき、順方向分岐は取られないと仮定します。 以下を参照してください。 ゴッドボルトの研究 .

その後、枝は枝予測キャッシュに入り、過去の動作が将来の枝予測に利用されます。

つまり、タイトなループの中では、ミスオーダーの影響は比較的小さいと言えます。 分岐予測器は、どの分岐が最も可能性が高いかを学習し、ループ内で自明でない量の作業がある場合、小さな差はそれほど大きくはなりません。

一般的なコードでは、ほとんどのコンパイラはデフォルトで（他に理由がない限り）、生成される機械語コードの順番を、あなたのコードで並べたのとほぼ同じにします。 したがって、if文は失敗すると前方に分岐します。

ですから、"first encounter"から最適な分岐予測を得るためには、可能性の低い順に並べる必要があります。

ある条件下で何度もループするようなマイクロベンチマークでは、命令数などの影響が小さく、相対的な分岐予測の問題はほとんど発生しません。 そこで、このような場合 プロファイル 経験則は当てにならないので。

その上、ベクトル化やその他多くの最適化が、小さなタイトループに適用されます。

そのため、一般的なコードでは、最も可能性の高いコードを if ブロックに入れることで、キャッシュされない分岐予測のミスが最も少なくなります。 タイトなループでは、まず一般的なルールに従い、それ以上の知識が必要な場合は、プロファイルを作成する以外に方法はありません。

もちろん、あるテストが他のテストよりはるかに安い場合は、すべてが水の泡になります。