switch-case文の効率について

最近のコンパイラの実装を良くわかっていないので素人っぽい質問になりますが、switch-case文の効率ってナイーブな方法よりはましになっているのでしょうか？

ナイーブな実装だと、単純に条件分岐を繰り返すだけですよね。

switch (b) {
case 1:
...
case 2:
...
case 3:
...
}

だと、馬鹿正直に順に書けば、
mov a, b
sui 1
jz case 1の処理
mov a, b
sui 2
jz case 2の処理
...

のような感じでしょうか。どのcaseにヒットするかあまり傾向がないとすると、分岐予測ミスが頻発し予測ミスのフラッシュもしくはパイプラインストールしまくりで恐ろしく効率悪い。

例えば上から順にジャンプベクタを用意して（上記例ではcaseが連番ですが、そうでない場合でも結果的に連番になるようにマッピングする処理を書いておくとして）、bの値によってベクタに書かれたアドレスをメモリからフェッチして即値アドレスジャンプ、なんて実装だったら速いですよね。

bは基底アドレスからのオフセットになるように変換されていて、基底アドレスから順にとび先がメモリに格納されている前提で、
mov a, b
sui case文の最大値
jc defaultの処理←ヒット率低めのはず
movi a, ベクタの基底アドレス
add b
call [a]
な感じの実装だと条件分岐が少なくて嬉しいような気がします。

なんか最近、ソースコードの書きやすさから安易にswitch-case文を書いてしまっているのですが、気にしなくてもいいのか、やはり気にした方がいいのか（最終的に効率よさげなCプログラムは如何様ににでも書き方はあると思います、無駄な配列を用意するとか）どっちなんでしょうか。

No.5 回答者： okwave2goo 回答日時： 2015/06/12 18:30

> もちろん、傾向がつかめる分岐ならこの限りではないと思いますけど。

GreenHills社のコンパイラは、実際に実行したプロファイラの結果を最適化に戻して、使い方にあった個別の最適化を行うような機能がありますね。

No.4 回答者： Tacosan 回答日時： 2015/06/12 12:43

調べてみるとちょっと古い例ですが

http://www.codeproject.com/Articles/100473/Somet …
というのがヒットしました.

もちろん今現在どうなっているかはわかりませんが.

No.3 回答者： artoo 回答日時： 2015/06/11 23:52

昔はCPUが遅かったので、テーブルを引くようにコンパイルされてたと思いますが(テーブルサイズとのトレードオフは当然あり。

メモリも狭かったので）、今時はCPUが速いので、ifと同じようにコンパイルされるケースが増えてると思いますよ。

この回答へのお礼

ありがとうございます。

＞今時はCPUが速いので、ifと同じようにコンパイルされるケースが増えてると思いますよ。

へー、それは興味深いですね。今時は半導体のプロセスが微細になりパイプライン段数が深くなっているのと、スーパースケーラでALUをいくつも並べて並列実行が可能なので、できるだけALUをふんだんに使う処理を行うほうが効率よく、唯一のボトルネックである条件分岐によるミスペナルティが増大する傾向にあると思っていました。もちろん、傾向がつかめる分岐ならこの限りではないと思いますけど。

お礼日時：2015/06/12 00:07

No.2 回答者： Tacosan 回答日時： 2015/06/11 15:05

この辺は処理系依存だから「実際にやってみる」しかない.

ただ, テーブル参照なんてのは 20～30年も前から普通に使われているはず. もちろんそれに加えて
・単純な if～else への変換
・バイナリ―サーチ
なども入ってるんじゃないかな (case の値が連続しない場合に「連番になるようにマッピングする」のと「バイナリ―サーチ」のどっちが速いかは知らん).

まあ, 本気で実行速度を考えるなら C で書いたりしないと思う.

この回答へのお礼

ありがとうございます。

単純なif～elseへの変換は、私が例示した書き方ですね。まさに単純なif～elseの変換です。
ところで、バイナリサーチが分岐命令なしに作れるのでしょうか？ちょっと驚きです。もしよろしければどんな処理になるのか教えていただけないでしょうか。

＞まあ, 本気で実行速度を考えるなら C で書いたりしないと思う.

それはその通りですね。C言語の教科書では「速い」とか謳っているものもありますが、CPU本来の表現力と比較すればCは表現力が貧弱なので、本気で効率を考えたらCで書くのは間違っていると思います、というかOSも要らない。

お礼日時：2015/06/11 23:52

No.1 回答者： ahoo_chieokur 回答日時： 2015/06/11 07:22

組み込みなら気にするかも。

処理時間が伸び縮みするのを嫌ってキャッシュOFFにしたりしてた。

あなたの目の前にある処理性能数百MIPS、主記憶１GB以上の計算機なら書きやすさの方を優先。

この回答へのお礼

ご回答ありがとうございます。

＞あなたの目の前にある処理性能数百MIPS、主記憶１GB以上の計算機なら書きやすさの方を優先。

世の中そういう流れなのですね。まあ、数百MIPSのCPUならパイプラインストールもさほど気にするレベルではない世代のものだとは思いますが。

ただ質問の趣旨としては、書きやすいcase-switch文を使ってもそこそこましなコードにコンパイルしてくれるのか否か、という点です。10回や20回同じswitch-case文をループで回すぐらいだったら何の気にもしませんが、数億回とか回す処理だとさすがに多少は気にした方がいいように思います。

お礼日時：2015/06/11 23:39