以下の square の実装は、連鎖した if 文に期待されるような一連の cmp/je 文を生成します。
int square(int num) {
if (num == 0){
0を返します。
} else if (num == 1){
1を返します。
} else if (num == 2){
4を返します。
} } else if (num == 3){
9を返します。
} } else if (num == 4){
16を返します。
} } else if (num == 5){
25を返します。
} } else if (num == 6){
36を返します。
} } else if (num == 7){
49を返します。
} else {
num * numを返す。
}
}
また、次のようにすると、returnのデータテーブルが生成されます。
int square_2(int num) {
スイッチ (num){
ケース 0: return 0;
ケース1:1を返す。
ケース 2: return 4;
ケース 3: return 9;
ケース 4: return 16;
ケース5:25を返す
ケース6:36を返す
ケース 7: return 49;
デフォルト:num * numを返す。
}
}
なぜgccは上のものを下のものに最適化できないのでしょうか?
参考までに分解してみると、https://godbolt.org/z/UP_igi
EDIT: 面白いことに、MSVCはswitchのケースでデータテーブルの代わりにジャンプテーブルを生成します。そして驚くべきことに、clangはそれらを同じ結果に最適化します。
switch-case`の生成されたコードは、従来、ジャンプテーブルを使用していました。この場合、ルックアップテーブルを介して直接リターンするのは、ここでのすべてのケースがリターンを伴うという事実を利用した最適化であると思われます。規格ではそのような効果を保証していませんが、もしコンパイラが従来のswitch-caseのジャンプテーブルの代わりに一連の比較を生成していたら、私は驚きます。
さて、if-else
についてですが、これは正反対です。switch-case」は分岐の数に関わらず一定時間で実行されるのに対し、「if-else」はより少ない分岐数に最適化されます。ここでは、基本的にコンパイラが一連の比較を書いた順番に生成してくれることを期待します。
つまり、もし私が square()の呼び出しのほとんどが
0か
1であり、他の値であることはほとんどないと予想して
if-elseを使用していたとすると、これをテーブルルックアップに最適化すると、実際にコードの実行速度が予想よりも遅くなり、
switchではなく
if` を使用する目的が失われてしまいます。ですから、議論の余地はありますが、GCCは正しいことをしていて、clangは最適化において過剰に攻撃的であると感じています。
誰かがコメントで、clangがこの最適化を行い、if-else
についてもルックアップテーブルベースのコードを生成しているリンクを紹介していました。clangでケースの数を2つ(とデフォルト)に減らすと、注目すべきことが起こります。clangは再びifとswitchの両方で同じコードを生成しますが、今回は次のようになります。
両方ともルックアップテーブル方式ではなく、比較と移動に切り替わります!
要約すると、「if-else」には一連の比較を、「switch-case」にはジャンプテーブルを使用するのが、コンパイラが従う傾向にあり、開発者がコードを書くときに期待する傾向にある標準的なパターンです。しかし、ある特殊なケースでは、よりよい最適化を実現するために、このパターンを破ることを選択するコンパイラもあります。また、開発者が何を望んでいるかを信頼して、一見最適ではないように見えても、パターンに従うことを選択するコンパイラもあります。どちらも有効なアプローチであり、それぞれ長所と短所があります。
考えられる根拠としては,num
の値が小さい方が,例えば常に0であるような場合には,最初に生成されたコードの方が速いかもしれないということです.switchの生成コードは,すべての値に対して同じ時間がかかります.
この表]1によると、最良のケースを比較しています。この表の説明はこの回答を参照してください。
num == 0`の場合、"if"には、xor、test、je(ジャンプあり)、retがあります。レイテンシーは1+1+ジャンプです。ただし、xorとtestは独立しているので、実際の実行速度は1+1サイクルよりも速くなります。
num < 7」の場合、「"switch"」では、mov、cmp、ja(ジャンプなし)、mov、retとなります。レイテンシー:2 + 1 + ジャンプなし + 2.
ジャンプにならないジャンプ命令は、ジャンプになるジャンプ命令よりも高速です。しかし、表にはジャンプした場合のレイテンシーが定義されていないので、どちらが良いのかは私にはわかりません。もしかしたら、最後の方が常に優れていて、GCCがそれを最適化できていないだけかもしれません。