1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Kinx 実現技術 - Switch-Case

Posted at

Switch-Case

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、(安定感は AC/DC)」 でお届けしているスクリプト言語 Kinx。作ったものの紹介だけではなく実現のために使った技術を紹介していくのも貢献。その道の人には当たり前でも、そうでない人にも興味をもって貰えるかもしれない。

前回のテーマは構文解析。今回のテーマは Switch-Case。

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 はジャンプテーブル化しないと使い物にならないので頑張った。

おわりに

ここまで読んでいただいてありがとうございます。最後はいつもの以下の定型フォーマットです。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?