Snippets

対抗して作ってみた。

ああ、invokedynamicがな

みなさん、invokedynamic知ってますよね。そう、あの Java8の lambdaで使われてるやつです。

と、振ってみましたが、知らない人も多いような気もします。まあ、とりあえず、動的言語を実装するために JVM7から導入された bytecodeだったけど、Java8の lamdbdaの実装にも使われて、実は JVM6レベルである Android Programmerは lambda使えなくて歯噛みしてるやつです。

ちなみに「がな」は「あったらいいなあ」という意味だと昔ならいました。

という書き出しで始まりましたが、俺の Advent Calendar 8日めの記事です。そんなのだれが気にしてるんだ。あと30分で書かないといかん。

invokedynamicの父

今日なぜそのことを書くかといえば、invokedynamicの父、Charles Nutter 来日記念セミナ として「JRuby loves invokedynamic」という講演があったからです。

Charlesは JRubyの創始者ではありませんが、JVM上で動的言語を実装するのが非効率なのに業を煮やして invokedynamicという動的言語を効率的に実装する仕組みを提案し、見事 Java7に導入されることになったのでした。そういう人が日本で話してくれるとなればいかねばなりません。

invokedynamicとはなにか?

古の JVMにはいろいろなメソッド呼び出しに応じて 4つの invoke bytecodeがありました。 invokestatic, invokevirtual, invokeinterface, invokespecialです。それぞれの内容は名前から推測してください。でも、どれも Javaに向いたもので、Rubyなどのような動的言語を実装するには向いてませんでした。

そこで提案されたのが invokedynamicです。知ってる人には inline method cacheを実装するためのもの、といえばわかるでしょうか。まあ、実際のところ method cacheだけのものではりません。methodを選ぶ仕組みを Java言語自体でカスタマイズできる、まるでリフレクションのような仕組みです。でもリフレクションほど協力ではないので、従来の JVMオプティマイズがきき、inline化とかいろいろできるぜ、っていうのが売りです。

どういう仕組なのか?

MethodHandleCallSite ってのが重要なようです。

各 invokedynamic命令には bootstrapというコードがくっついています。これは最初に一回だけ実行され、CallSite (呼び出し場所) を返します。CallSite は以降、invokedynamicを実行するたびに MethdoHandle を返し、JVMはそれを関数ポインタの用に扱ってジャンプします。

CallSite にはいくつかの子クラスがあり、一番単純な ConstantCallSite だと必ず同じ MethodHandle を返すので、JVMはその事実をもとにいろいろ最適化できるというわけです。

この最適化はヒューリスティックにもとづいています。動的言語では、コードの一つの場所で変数の指すオブジェクトの型は実行時までわかりませんが、実際のところ大抵同じ型がくるので一生懸命 virtual tableみたいなものを見るより速くなる、というわけです。Methodhandle自体もいろいろあって、万が一予想外の型がきた時のためにガードをつけたりもできるようです。

JRubyではどうつかっているか

メソッド呼び出し

これはできた経緯からして当然ですね

正規表現とかの定数

コードに現れた正規表現とかを全部コンパイルしておくのはムダです。本当に使うかわからんからです。 そこで、invokedynamicを使い、最初の bootstrapで正規表現コンパイルするようにします。で、bootstrapの返す CallSiteはできた正規表現オブジェクトをいつも返すようにすれば、その後は分岐とかなしに高速に実行されます。さらには HotSpotの最適化が走って、最初からオブジェクトがおいてあったかのようなコードになるのでしょう。

インスタンス変数の参照

Rubyとかは、インスタンス変数を動的に付け加えられます。で、ここのところを一々名前で呼び出してたのでは遅くてたまらないので、invokedynamicでほげほげしてるらしいです。時間がないので端折ります。

どの程度速くなるのか

ちょっと見せてもらったベンチマークでは、invokedynamicを使わない場合に比べて 2から3倍ぐらい速くなっているようでした。

そもそも JRubyは invokedynamicなしでも CRubyより速いので、invokedynamicつきだと 5倍ぐらいになるよ、と。

お気に入りの例として、RebBlackTreeを実装したときに CRubyはもとより、CRuby + C で書いた実装よりも速くなったと自慢してました。ちょっとかわいい。

Androidにいつくるの?

えーと、会場は Oracleのオフィスでした。OracleAndroidの話をするのは禁じられてるらしいです。

というか、そんなの Google次第だよなあ。きっと、なかではもう invokedynamicのある ARTとか動いてて、でも大人の事情で出せなかったりするんじゃないのかなあ。Oracle

でなんとか間に合った。あしたは dageziさんが Sketch+CircleCiというネタで書くらしいです。って3分後だよ。