GCCはswitch文をどう最適化するのか、その判断基準を読み解く
Switch Lowering in GCC
GCCがswitch文をジャンプテーブル、比較木、ビットセットのどれで実装するかを、実際のアセンブリとソースコードから解き明かす。ケース値が疎でも密集した部分集合を見つけてジャンプテーブルにしたり、連続ラベルを2回の比較にまとめたりと、その判断は単純な密度だけでは決まらない。最終的にpass_lower_switchのヒューリスティクスを追い、コンパイラの意外な工夫を明らかにする。
コンパイラは、ケースが連続していることを見抜き、4回ではなく2回の比較で実装できると判断する。
HNでの議論
36- LarsKrimi
sparse_8 の switch は、ジャンプの前に x を 8 で割れば単純化できるはずだ。面白いことに、gcc はこの単純化を見つけられない。
それは無理だろう。なぜなら、そうすると各ケースの 7 つの値が default ケースではなく関数呼び出しで処理されることになってしまうからだ。0/8 は 0 だが、3/8 もまた 0 なのだ。
- rurban
clang と gcc にとって何とも残念な話だ！ 両者は大きな疎な switch テーブルに対して未だに完全ハッシュを実装していない。私は最近、自分の rcc C コンパイラのためにそれをやったが、たった一日の作業で済んだ。特に Unicode を扱う作業には有益だ。LLVM のパッチは 10 年前に却下された。Gcc にはブランチにいくつかの Unicode パッチが眠っていて、それにもこれが必要だろう。
- p-t
compact_7() のやつは 34 ではなく 35 のつもりだったんじゃないか、そして bittest() のやつはどこかの時点で edx を使うつもりだったんじゃないかと思う（まあ、俺が何か見落としているのでなければだが lol）。
- tsukikage
なぜ間接参照するんだ？ なぜジャンプへのジャンプに飛ぶのではなく、ジャンプテーブルが f0..fX を直接参照するようにしないんだ？
- Andi
JavaScript で（コードを生成することで）似たようなものを、イミュータブルな Map や Set 向けに実装したことを覚えている。モダンなエンジンでは目立った性能向上はなかった。複雑な Unicode 範囲の正規表現については、高速化は約 2 倍だった！