Switch-Case
はじめに
「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。作ったものの紹介だけではなく実現のために使った技術を紹介していくのも貢献。その道の人には当たり前でも、そうでない人にも興味をもって貰えるかもしれない。
前回のテーマは構文解析。今回のテーマは Switch-Case。
- 参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
- リポジトリ ... https://github.com/Kray-G/kinx
Switch-Case
なぜ Switch-Case を取り上げるかというと、やはり ジャンプテーブル の魅力があるから。基本多分岐なので、複数の条件に対して一発でジャンプできるのが期待値だろう。ただ、そのために結構複雑な処理をしている。
整数値・それ以外
まず、数値（整数）かそれ以外かで動作が異なる。整数値以外は基本 if-else にするしかないのだが、整数値は可能ならジャンプテーブルにしようと試みる。なので、まずは整数値かどうか確認し、どちらかに分岐させる。
整数値の場合
整数値の場合、ジャンプ・テーブル化を試みる。ただし、下限と上限の差がありすぎる場合、無駄なジャンプが増えすぎてしまうという問題がある。そこで、閾値を設定して複数のブロックに分割する。例えば以下のケースをパースした場合、
switch (a) {
case 10: break;
case 11: break;
case 1: break;
case 2: break;
case 3: break;
case 4: break;
case 5: break;
case 6: break;
case 51: break;
case 52: break;
case 53: break;
case 54: break;
case 100: break;
case 'aaa': break;
default: break;
}
1～100 までのジャンプテーブルを作ってしまうと 13 個だけが有効で、残りの 87 個は default にジャンプするだけの無駄が多いテーブルを作ってしまう。アドレス（ポインタ）サイズが 64bit の場合、100 個のジャンプを用意するだけで 800 バイト必要になる。800 バイトが多いかどうかは別にして、無駄なスペースが沢山あることに違いはない。
そこで、まず数値自体をソートして順に確認していき、閾値（デフォルトは 16）以上のインターバルがあった場合、別々のグループ（ブロック）に分けて、それぞれでジャンプテーブル化させるようにする。どのブロックに分岐するかは二分探索で選択する形でコード出力する（場合によっては線形探索）。
ちなみにブロック内の選択肢が少ない場合はあえてジャンプテーブル化はしない。線形探索や二分探索の方が効率が良い場合がある。なぜなら、ジャンプテーブルの場合、上限・下限値を越えないか比較し、評価値から下限値を減算してその上でジャンプさせることになるので都合3回は比較が入る。例えば比較値が 1 種類の場合、単に一発比較するだけの方が効率が良い。したがって、これにもブロック内の要素数を考慮してどの方式を使うかを決定する。
ちなみに、今後触れようと思うが VM コードの実行で Switch-Case を採用する場合のペナルティ（ダイレクト・スレッディングの有効性）は一般的には CPU パイプラインの投機実行ミスを指摘されるが、この比較回数もあるんじゃないかと思う。何せ 1 命令実行するために最低 3 回は比較と分岐が入る。明らかに上限・下限を超えないと判断できない限り、範囲外の条件判断は必要だしね。この辺は投機実行でカバーできているのかもしれないが。
上記の場合、1～11 のブロック、51～54 のブロック、100 だけのブロックに分かれる。評価値（a）の値によって二分探索（または線形探索）でどのグループを探索するかを決め、それぞれのグループの中で実際のジャンプ先を決定する。
それ以外
それ以外の場合、単に線形探索でジャンプ先を決定する。つまり if-else の連続で値をチェックする。
出力例
具体的な出力コードは以下のような感じ。break しかしてないので結局最後に jmp しているだけで、本気で最適化したらこのコード自体出力されないよなものだが現時点ではサーチのエッセンスは出力されている。
.L460
d04: enter 7, vars(1), args(1)
.L462
d06: pushvl0 $0(0)
d07: dup
d08: typeof is integer
d09: jz .L463(d1d)
d0a: dup
d0b: lti 1
d0c: jnz .L464(d22)
d0d: dup
d0e: gti 11
d0f: jnz .L464(d22)
d10: subi 1
d11: jmptbl
d12: jmp .L482(d47)
d13: jmp .L482(d47)
d14: jmp .L482(d47)
d15: jmp .L482(d47)
d16: jmp .L482(d47)
d17: jmp .L482(d47)
d18: jmp .L463(d1d)
d19: jmp .L463(d1d)
d1a: jmp .L463(d1d)
d1b: jmp .L482(d47)
d1c: jmp .L482(d47)
.L463
d1d: dup
d1e: pushs "aaa"
d1f: eqeq
d20: jnz .L482(d47)
d21: jmp .L482(d47)
.L464
d22: dup
d23: lti 51
d24: jnz .L465(d32)
d25: dup
d26: gti 54
d27: jnz .L465(d32)
d28: dup
d29: eqeqi 51
d2a: jnz .L482(d47)
d2b: dup
d2c: eqeqi 52
d2d: jnz .L482(d47)
d2e: dup
d2f: eqeqi 53
d30: jnz .L482(d47)
d31: jmp .L482(d47)
.L465
d32: dup
d33: neqi 100
d34: jnz .L463(d1d)
d35: jmp .L482(d47)
.L466
（省略）
.L482
d47: ret null
d48: halt
出力コードを見るとまだまだ改善点はあるものの、初版としては十分かなー、と。
Switch-Case の魅力はやはり ジャンプテーブル と言っても過言ではない。それが無ければ Switch-Case を使う意味は間違いなく半減するよね。それができることを期待して Switch-Case を選ぶということも多いですし。例えば、Yacc で出力された構文解析器なんかは Switch-Case の塊なので、全ての比較が if-else で行われていたら正直パフォーマンス的にやってられないレベルで遅くなってしまう。つまり、Switch-Case はジャンプテーブル化しないと使い物にならないので頑張った。
おわりに
ここまで読んでいただいてありがとうございます。最後はいつもの以下の定型フォーマットです。
- 最初の動機は スクリプト言語 KINX（ご紹介） を参照してください（もし宜しければ**「
いいねLGTM」**ボタンをポチっと）。 - リポジトリは ここ（https://github.com/Kray-G/kinx） です。こちらももし宜しければ★をポチっと。