switch文の最適化

CPUのエミュレータを高級言語で実装する場合、switch-caseを多用して実装する場合が多いと思います。その場合は、エミュレーション対象のCPUの1命令を実行するたびに、switch文を1回実行することになります。
そのため、switch文をコンパイルしたときに、どんな命令に落ちるかは、パフォーマンス上とても重要です。

Javaにおいてswitchをコンパイルした場合に出力されるバイトコードは、tableswitchかlookupswitchになるようです。

tableswitchでは、ジャンプテーブルを使った分岐が行われます。
lookupswitchは、case句の値が離散的な場合など、ジャンプテーブルをうまく作れないような場合に、こちらが使われます。

lookupswitchが、JVMでどのように処理されるかにもよるでしょうが、tableswitchの方が高速なはずです。

http://www.tani.cs.chs.nihon-u.ac.jp/g-2003/satoshi/report.pdf
大学生の卒論ですが、lookupswitchの処理についての実験と考察が書いてあります。
lookupswitchは、JRE1.1.8では線形探索、JRE1.4.1ではもうちょっと効率がよい何かのアルゴリズムで実装されてるっぽいっていうことが書いてあります。
もうちょっと深く追求してくれるとありがたかったんですが…

しかし、古い実装のJVMでは、lookupswitchが線形探索になるっていうのは、なかなかショッキングです。線形探索ということは、

if (a == 0) { ... }
else if (a == 1) { ... }
else if (a == 2) { ... }

という風に書いたのと、性能的に変わらないわけですから。

PC上で動作するJREの場合は、数年前からソースが公開されてますので、lookupswitchがどのように処理されるかを調べるためには、ソースを読めばいいわけです。しかし、携帯のJVMについては、各社がどんな処理系を使っているかがそもそも不明です。携帯Javaの場合は、テストコードを実機上で走らせて、処理時間から使われているアルゴリズムを推測するしか無さそうです。

ところで、tableswitchとlookupswitchの使い分けの条件は、どうやって決まるのでしょうか。

http://blog.livedoor.jp/lisper/archives/16161645.html
こちらのページに情報がありました。
引用すると、

「虎」と呼ばれる店で調査してみました。
case のラベルで埋まっている個数を n として、その間の数値で空いている個数を e とします。
そのときの店主の判断は以下のようになります。
n * 4 - 10 >= e ∧ n > 3 のときは tableswitch
そうでないときは、lookupswitch ということが秘密裏に判りました。

とのことです。
「虎」っていうのは、Java5のコードネームがTigerだからですね。
式が書いてあるのがありがたいのですが、∧はEXORのことでいいのでしょうか。良く分からないです。

こうなってくると、Javacのソースコードを読むしかなさそうです。
http://openjdk.java.net/
ここから、JDKのソースらしきものをとりあえずダウンロードしてきました。JDK全体のソースなので、かなり巨大です。ちょっと見てみたのですが、ソースのどこでswitchのコード生成を行っているのか特定することが出来ませんでした。

JDKは巨大すぎるということで、他のJavaコンパイラの実装について調べてみることにしました。
EclipseにはECJというJavaコンパイラが付属していますが、こっちのソースの方が分かりやすい感じでした。
ECJで、switch文のコード生成を行っている部分は、
http://kickjava.com/src/org/eclipse/jdt/internal/compiler/ast/SwitchStatement.java.htm
このページで見れます。
tableswitchとlookupswitchの使い分けですが、このソースの185行目に注目です。

if ((long) (caseCount * 2.5) > ((long) max - (long) min)) {
   // tableswitchを生成
} else {
　 // lookupswitchを生成
}  

っていう処理になってます。
caseCountはcase句の数です。maxはcaseに指定した値の最大値、minは最小値です。

case句の最大と最小の差が、case句の数の2.5倍より小さくなるようにしてやれば、tableswitchが生成されるようですね。

これで分かってきたことは、Javaコンパイラの種類によっても、tableswitchとlookupswitchの使い分けが異なるっぽいですね。

Javaパフォーマンスチューニング 第2版

この前、この本を買ってきました。
この本では、switch文で確実にtableswitchが使われるようにするために、

1. ダミーのcase句を挿入して、caseの値を連番にする
2. case句の値が大きく飛ぶ場合は、switchを複数に分割する

という興味深い最適化手法が紹介されていました。

この本には、tableswitchとlookupswitchの使い分けは、case句の値が連番になってるかどうか、としか書いてありませんでした。
色々な条件でswitch文を書いて、javapにて逆アセンブルして確認したのですが、連番になっていなくても、tableswitchが使われる場合があることを確認しています。
どうやら、2003年の本ということで、すでに内容が古いようです。

私が作成したソフトを使ってファミコンの6502のコードを逆コンパイルすると、不連続なcase句の値を持つ、巨大なswitch文が出力されます。
それをjavacにかけるとlookuptableにコンパイルされています。

lookuptableが携帯のJVMでどの様に処理されるかがいまいち不明なので、それが効率よく処理されることを期待してると裏切られそうな感じがしてきました。

「Javaパフォーマンスチューニング」に紹介されていた手法を使用して、確実にtableswitchでジャンプテーブルにて分岐させるようにしたいところですが、javaコンパイラによっても条件が変わるとなると、なかなか難しいですねえ。

DoJaの場合、DoCoMoが保証しているのはJDK1.4.2までの様ですので、JDK1.4.2のjavacに対象を絞ってしまうのも手かと思います。
実際は、JDK5以降のコンパイラでも、携帯の実機上で問題なく動作しているみたいですが。

…と思ったのですが、JDK1.4.2はオープンソースになる前だった気がするので、ソースが公開されてないかもしれません。そうなると、switchのコード生成について調べるのが難しいですね。
結局、いろんなパターンでswitchを書いて、逆アセンブルして調査するしかなさそうです。しんどいなあ…

ふと思ったのですが、javacに頼らないで自前でclassファイルを生成するようにすれば、確実にtableswitchを使うようにできますねえ…
そこまでやるかっていう話ですが、最終的にはそれもアリかもしれません。