CTOの河合(@neuecc)です。グラニもエンジニアブログはじめました！グラニの中心的テクノロジーであるC#関連は元より、Unity関連やUniRx、最近力を入れているVR関連についての情報を色々と発信していけたらと思っています。私自身は、思いたったときが書き時ということで、私が社内にふっと流したくなったものを、外向けに発信していこうかな、と思っています。
さて、今回のテーマはswitch文のコンパイル結果について。C#は割と素直なコンパイル結果(ILへの変換)を得られるのですが、一部のものはアグレッシブな変換を行います。有名所ではラムダ式のクロージャなどは、隠れたクラスを作ってくれる、作ってしまうなど、コードの見た目からイメージした通りではない結果を出力しますが、実はswitch文もかなりアグレッシブな変換を行います。そこで、今回はそうしたswitchの最適化を見ていきましょう。
なお、最適化はコンパイラの実装によって変わります。Unity(monoの古いバージョン)でもRoslyn(VS2015)以前と以降でも、あるいはその前でも主にVSのバージョンによって細かく向上していっています。今回の検証はViaual Studio 2017 RCによるものです。また、C#コンパイラによる最適化は中間言語(IL)への変換までで、実行時最適化についてはJITコンパイラの仕事になってきます。
case数による最適化
switchは中身が少ない場合に、if文に置換される場合があります。例えばintでたった2ケースの場合
static int SmallCase1(int x) { switch (x) { case 0: return 0; case 1: return 1; default: return -1; } }
これは以下のように変換されます。
if (x != 0) { if (x != 1) { // default: } else { // case 1: } } else { // case 0: }
量が少ない場合はifのほうが速い、という決定でしょう。3ケース以上では、書いたままの挙動です。しかしそもそも書いたままとはどういうことか、というと、具体的にはILにおいてはOpCodes.Switch、つまりジャンプテーブルを利用した分岐に変わります。
// Emitのイメージ
OpCode.Switch(label1, label2, label3)
MarkLabel(label1);
MarkLabel(label2);
MarkLabel(label3);
悪くなさそうです。
文字列のswitch
C#のswitchは数値以外にも文字列が使えます。文字列も同様に少ない場合はifに書き換わります。書き換わる数はintの場合とは異なり、もう少し多めです。
static int StringSwitch(string x) { switch (x) { case "aaa": return 0; case "bbb": return 1; case "ccc": return 2; case "ddd": return 3; case "eee": return 4; case "fff": return 5; default: return -1; } }
というswitchは
static int StringSwitch(string x) { int result; if (!(x == "aaa")) { if (!(x == "bbb")) { if (!(x == "ccc")) { if (!(x == "ddd")) { if (!(x == "eee")) { if (!(x == "fff")) { result = -1; } // 以下elseが続くので省略 }
に書き換わります。なるほど、若干理想のイメージと異なる気はしますが、shoganai。それより大きな場合は更に異なるものになり、
static int StringSwitch(string x) { switch (x) { case "aaa": return 0; case "bbb": return 1; case "ccc": return 2; case "ddd": return 3; case "eee": return 4; case "fff": return 5; case "ggg": return 6; default: return -1; } }
これは、以下のような原型をとどめてる気があまりしないものに変わります。
private static int StringSwitch(string x) { uint num = <PrivateImplementationDetails>.ComputeStringHash(x); int result; if (num <= 1488952485u) { if (num != 876991330u) { if (num != 1426598844u) { if (num == 1488952485u) { if (x == "bbb") { // elseは中略 } else { if (num <= 3003732817u) { if (num != 2339852366u) { if (num == 3003732817u) { if (x == "fff") { // elseは中略 } else { if (num != 3815745472u) { if (num == 3848007555u) { if (x == "ddd") { // (略) } else { if (x == "ccc") { // (略) } } } result = -1; return result; }
えー、全然違うじゃん！何に書き換わるかというとまずどこからか出てくる
<PrivateImplementationDetails>.ComputeStringHash
によって文字列のハッシュコードが計算され、そこから二部探索的に目的のコード部分を探り当てるコードに変換されます。switch使えば文字列も一発で引いてくれるんだ、などという甘い幻想はなかった。普通のstring.GetHashCodeではなく、わざわざ隠れたComputeStringHashメソッドを使うのは、ハッシュ値の算出をライブラリに依存せずコンパイル時に固定するためでしょう（文字列のハッシュコード値は、環境によって異なる（同じであるとは保証されていない）ため、永続化させてはいけない）。
バラバラの数値の場合
文字列が思ってたのと違うような形に変換される他に、数値であっても、その中身によって変換結果が変わってきます。例えば、以下のようにバラバラの数値をswitchにかける場合
static int SwitchCase(int x) { switch (x) { case 1230: return 0; case 324: return 0; case 24432: return 0; case 99: return 0; case 93429: return 0; case 929: return 0; case 199: return 0; case 94249: return 0; case 53: return 0; case 1234: return 0; default: return 0; } }
これは以下のようなifの羅列になります。
if (x <= 929) { if (x <= 99) { if (x == 53) { } if (x == 99) { } } else { if (x == 199) { } if (x == 324) { } if (x == 929) { } } } else { if (x <= 1234) { if (x == 1230) { } if (x == 1234) { } } else { if (x == 24432) { } if (x == 93429) { } if (x == 94249) { } } }
二分探索のifのコードになっていて、つまりstringのComputeStringHashを除いた場合と同様、ってことですね。
さて、何故こうなってしまうかというと、OpCodes.Switch を改めて見てもらうと
switch (N, t1, t2... tN) | Jumps to one of N values.
飛び番のテーブルは作れません。しょーがないよね、そりゃそうですね、ということなのであった。なお、別に0始まりである必要はなくて、連番であれば構いません。連番も、1,2個の欠番ならば塞いでくれます。以下のようなコードは
static int SwitchCase(int x) { switch (x) { case 30: return 1; case 31: return 2; // 32, 33... case 34: return 3; case 100: return 4; case 101: return 5; case 102: return 6; default: return -1; } }
以下のような、ILの原理を理解した上でイメージする最大限にいい感じのコードに書き換わってくれます。
switch (x) { case 30: return 1; case 31: return 1; case 32: case 33: break; case 34: return 3; default: switch (x) { case 100: return 4; case 101: return 5; case 102: return 6; } break; } return -1;
C#コンパイラもなかなか賢いですね！
なお、switchはintや文字列よりも、Enumと組み合わされるケースが多いと思いますが、その場合はその後ろのプリミティブの型(何も指定していない場合はint)で適用されます。
// Enum定義 public enum MyEnum1 // defaultは : int { Foo, // defaultは0から連番 Bar, Baz, } // 数字を弄るパターンも割りとよくある(10XXXは魔法、20XXXは物理、みたいなゾーン分けなど) public enum MyEnum2 { Foo = 100, Bar = 200, Baz = 300, }
つまり、上記のようなEnumをswitchした場合、前者のほうが速い、ということになります。
switch非対象の型でswitchしたい場合の最適化手段
intや文字列以外でもswitchのようなことをしたい、場合は全然あると思います。ifの羅列、もいいですが、数が多くなる場合は、今回見たstringの生成結果を模してみるのも効果的かもしれません。
// 数が十分に多い場合。10以下ぐらいならif列挙で良いでしょう(stringと同じように) static readonly Dictionary<Type, int> jumpTable = new Dictionary<Type, int>(3) { {typeof(FooClass), 0 }, {typeof(BarClass), 1 }, {typeof(FooBarClass), 2 }, }; static void TypeJump(Type t) { int key; if (!jumpTable.TryGetValue(t, out key)) return; switch (key) { case 0: // case FooClass break; case 1: // case BarClass break; case 2: // case FooBarClass break; default: break; } }
int側は0からの連番にすることにより、ジャンプテーブルが間違いなく使われることが期待できます。他に、より書きやすい代替としてDictionaryにActionを詰める(Dictionary<T, Action>)手法もありますが、intからのswitch-caseのほうが効率的に動作するでしょう。
まとめ
コード高速化の手段としてILGeneratorを用いて、ILを直接動的に書き込む手段は(AOT/IL2CPP環境など動的生成が許されていない環境でなければ)非常に有効です。動的生成ならではの、ifなどの分岐を生成時に決定して除去する、定数的なものを埋め込んでしまうなど、その生成時に最適化されたコードパスを通すなどのような手段が取れることも大変強いです。しかし、ILを直接書き込むことには弱点があり、今回見たようなC#コンパイラの行う最適化は事実上できません。やろうと思えば出来ますが、途方もない手間であり、実際は、素直なILを書く程度に留まらざるをえないでしょう。一概に動的コード生成すれば最速なんだ、というわけではないし、また、ではより速いコードを作るにはどうすればいいのか。何故やや遅くなってしまうのか、の原則は、こういうところに隠れているものかもしれません。
なお、強調しすぎてもしすぎることはないですが、「速い」といっても、これは本当に本当に些細な差ですので、よし、Enumは連番のほうが速いから連番にしよう！とかはやめるべきです。理屈上そうだというだけで、実際のアプリケーションで有意な差にまで繋がることはほぼないでしょう。
