34451


switch文とif文の実行速度やメモリの使用量について

if文はメンテナンス性を考えると効率が悪い方法というのを知っています。

[code]

    enum Act{ AAA, AAB, ... , ZZZ};
    if ( AAA == ch ){...}
    else if( AAB == ch ){...}
    ...
    else if( ZZZ == ch ){...}
    else{...}
    
[/code]

そこで、switch文を使うのですが、、カッコも悪く効率も悪そうです。

[code]

    switch (　ch ){
    case AAA: ... break;
    case AAB: ... break;
    ...
    case ZZZ: ... break;
    default: ... break;
    }
    
[/code]

なぜなら、コンパイルの結果同じバイナリコードが生成されているとしたら  
上から順に比較することになり最悪で26^3回の比較が必要になるからです。  
26^3回がコンピュータにとってたいした数ではないかもしれませんが、極力多くしてみました。  
それに始めて見たときにこのコードに対して、知的さを感じず快く思いませんでした。  
そこで以下のようなコードを考えました。

[code]

    void (*name[])(void*)={ aaa, aab, ... , zzz};
    name[ch](NULL);
    aaa(void* a){}
    aab(void* a){}
    ...
    zzz(void* a){}
    
[/code]

これなら関数になるので抜け出す処理が記述されていても納得ですし。  
caseがどんなに増えてもアクセスは定数時間かと思います。  
巨大なswitch文が一人で居座るわけでなくなるので、ファイルの分割も行いやすくなります。  
分割してコンパイルしていればそれ相応に恩恵を受けるかと思います。  
ただ、ひとつ関数が増えるたびに変更する箇所がenumと配列,caseだけのswitchと比べたら手間になってしまっている気がします。

実際の現場ではどれが利用されて居るのでしょうか。  
内心はif<3~5 switch<10
それ以上では、配列関数ポインタ又は、関数へのポインタの配列、もしくは関数の配列（実は名前を知らない）を利用したほうがよいと思うのですが、規則や効率など総合的に見てこういった書き方はどうなのでしょう。


CC BY-SA 3.0
2017-05-03T08:31:42.663
34434
2017-05-07T23:10:56.027
2017-05-07T04:21:24.877
10455
10455
question
c
switch文とif文の実行速度やメモリの使用量について


コンパイラがソースコードを解析したとき、`if`の連続を`switch`と同等に処理するか、`switch`を`if`の連続と同等に処理するかは、コンパイラが決めることで、人間が気にする必要はほとんどありません。その`switch`でさえ、`case`の値が単純な数列の場合、ジャンプテーブルの生成まで、コンパイラが自動で行います。

もっと高位の次元で、アルゴリズムをどう実装するか、といった場面では、人間による工夫も必要でしょうが、`if`にするか`switch`にするかといったレベルでは、コンパイラに任せてしまうのがベストです。

だから、人間にとっていちばん読みやすい書き方をしたときに、高速で省メモリなバイナリを生成します。

なぜなら、コンパイラは人間の癖を知っているのです。コンパイラはそのように、人間の癖に合わせて設計されています。

ちなみに3番目に例示された、ジャンプテーブルを自前で用意する、というのが、いちばん良くありません。ジャンプテーブルの配列の引数値がオーバーフローしたとき、アクセス違反が発生したり、想定外のアドレスにジャンプしたりしますので、プログラマが細心の注意を払って実装しなければなりませんし、何より、コンパイラが最適化する余地がなくなります。


CC BY-SA 3.0
2017-05-03T09:19:02.053
34435
2017-05-03T09:19:02.053
3337
34434
answer


極端な例を用意したのはわかりますが、 **実際の現場** を想定するのであれば、

  * 26^3の分岐（分岐先ではなく分岐自身）が実行時間に対して支配的だとすると設計が悪い可能性があり、設計を見直します。それでもパフォーマンスチューニングが必要であれば[PGO; Profile-guided optimization](https://en.wikipedia.org/wiki/Profile-guided_optimization)を行います。PGOにより分岐の出現パターンに応じた最適化を期待します。
  * 支配的でないのであれば、他の部分のパフォーマンスチューニングに力を注ぎ、分岐に関しては書きやすいように書きます。CPPマクロを使用したテーブルなど。

PGOはコンパイルの際に、実際に実行したプロファイル結果を参考に最適化を行うものです。一例とし[てVisual
C++](https://msdn.microsoft.com/ja-jp/library/e7k32f4k.aspx)では

  * インライン展開
  * 仮想呼び出し推理
  * レジスタの割り当て
  * 基本ブロックの最適化
  * サイズ/速度の最適化
  * 関数のレイアウト
  * **条件付き分岐の最適化**
  * 実行されないコードの分離
  * EH コードの分離
  * メモリの組み込み

といった最適化が行われます。このうち条件付き分岐の最適化は

> 値プローブを使用し、switch ステートメント内の特定の値が他の値よりも頻繁に使用されているかどうかを、ガイド付き最適化のプロファイルで検出できます。
> この値は switch ステートメントから取得できます。 また、if ブロックまたは else ブロックのどちらがより頻繁に true
> になるかに応じて、このどちらかのブロックを最初に置くようにオプティマイザーが if/else を並べ替えることができる場合には、これと同じことを
> if/else 命令でも行うことができます。

といったもので、if / switch文のどちらを選んでも関係なく、また比較順序やcaseの記述順序についても最適化されます。

* * *

>
> 巨大なswitch文が一人で居座るわけでなくなるので、ファイルの分割も行いやすくなります。分割してコンパイルしていればそれ相応に恩恵を受けるかと思います。
>
> 分割す‌​ればコンパイルも早くなるだろうし。

コンパイル時間を気にされていて、ソースコードを分割することを検討されていると解釈しました。まず今どきのプロセッサでのコンパイル時間は大したことがありません。またC言語では各ソースコードに対して`#include`などプリプロセッサの実行し直しとなるため、ソースコードを分割するとコンパイル時間は増加します。  
これはあくまで質問文で言及されているコンパイル時間に関するコメントであり、一般論としては既に述べているように設計を見直すべきです。


CC BY-SA 3.0
2017-05-03T14:29:28.000
34440
2017-05-07T23:10:56.027
2020-06-17T08:14:45.997
-1
4236
34434
answer


ifとswitch・・・。「どちらで記述すると他の人に伝わり易いか」以外に比較する必要性を感じていない、に一票。

WindowsやLinuxなどユーザ空間だけでしかプログラミングをした経験が無いと迷い込みやすい「沼」にはまり込んでおられるように思います。

少し視点を変えて、特定マイコン向けの組み込み環境でC言語でプログラミングをしてみると、「効率」とか「最適化」とかいった、今はまだ「何だか良くわからないけどカッコイイ言葉」が切実に現実味のある言葉として身近に感じられるようになると思います。

そこまでするのが億劫なら、マイコン向けコンパイラのドキュメント(特に最適化の説明)を紐解くだけでも有用だと思いますが。


CC BY-SA 3.0
2017-05-04T05:42:05.100
34451
2017-05-04T05:42:05.100
20139
34434
answer


本当に26^3通りの分岐を行いたいのでしょうか？  
17576個のenumシンボルと17576個の分岐先関数を用意するのでしょうか？

私が過去にやったことがあるのは、JIS漢字コードからUnicodeへの変換やその逆変換を行うために、二分岐検索を用いたルックアップテーブルを作成したことがあるくらいです。

文字コードの変換の例でいうと、元の値は16ビット値でしたので、65536通りです。これを別の65536通りの値に変換するというものですが、このような用例では、処理を分岐したいわけでなく、値を変換したいだけなので、配列から値を取り出すとか、検索や演算で求めるだけで済むわけです。

実際の現場と仰っていますが、26^3個の分岐先の関数が、それぞれ関係のない別の処理を行うという状況はあまりありません、入力値である`ch`の値に応じて、ちょっとだけ違う似たような処理を行うのであれば、分岐先の関数を必要に応じてカテゴリー毎に何種類かに分けて、引数として`ch`を受け取る関数を用意すれば、大半の`ch`を一つの関数で受け持つことができるでしょう。

ここでいう`ch`が、ウィンドウメッセージやイベントやコマンドの番号の様なものだとして、17576種ものコマンドがあるかというと、実際の現場ではあまりないでしょう。仮にあるとしても、`ch`が数千種から数万種の値を取り得るという前提であれば、グループ番号とサブコマンド番号に分けるというのを検討してみます。例えば、上位8ビットをグループ番号、下位8ビットをサブコマンド番号とすることを考えます。符号無し8ビット整数であることが明らかならば、境界値チェックは必要なく、256個の配列を用いてジャンプテーブルを構成すればいいでしょう。一段目の分岐をジャンプテーブルで行い、二段目の分岐を`switch`で行うというもの、ありえない設計ではないと思います。

あとは、机上の議論ではなく、質問者が、具体的にどんな問題を解決したいかによって、どういう方法を採用するのが適しているかは変わってきます。


CC BY-SA 3.0
2017-05-06T00:55:03.237
34477
2017-05-06T00:55:03.237
3337
34434
answer