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 つの条件テストは相互に排他的であり、副作用は発生しません。確かに、望ましい動作を実現するためにステートメントを特定の順序で評価する必要がある場合、効率の問題は意味がありません。
ベストアンサー1
一般的なルールとして、ほとんどのIntel CPUは、前方分岐が最初に発生したときには実行されないものと想定します。ゴッドボルトの作品。
その後、分岐は分岐予測キャッシュに入り、過去の動作が将来の分岐予測に使用されます。
したがって、タイトなループでは、順序の誤りの影響は比較的小さくなります。分岐予測子は、どの分岐セットが最も可能性が高いかを学習しますが、ループ内にかなりの量の作業がある場合、小さな違いはそれほど大きな影響を及ぼしません。
一般的なコードでは、ほとんどのコンパイラはデフォルトで (別の理由がない限り)、生成されたマシン コードをコード内で順序付けたのとほぼ同じ順序で順序付けます。したがって、if ステートメントは失敗すると前方に分岐します。
したがって、「最初の遭遇」から最良の分岐予測を得るには、分岐を可能性の降順で並べる必要があります。
一連の条件を何度も繰り返してループし、些細な作業を行うマイクロベンチマークでは、命令数などの小さな影響が支配的になり、相対的な分岐予測の問題はほとんど考慮されません。そのため、この場合はプロフィールを作成しなければならない経験則は信頼できないからです。
さらに、ベクトル化やその他の多くの最適化が小さなタイトループに適用されます。
したがって、一般的なコードでは、最も可能性の高いコードをifブロック内に配置すると、キャッシュされていない分岐予測のミスが最小限に抑えられます。タイトなループでは、最初は一般的なルールに従ってください。さらに詳しく知る必要がある場合は、プロファイルする以外に選択肢はほとんどありません。
当然ながら、一部の検査が他の検査よりもはるかに安価である場合、このすべてが無意味になります。