あなとみー おぶ mrubyのJIT (その13) - miura1729の日記
お久しぶりです。ずいぶんと更新をさぼっていたのですが、ときどきバグるけどmrubyのJITは元気です。さて、この半年、mrubyのJITもいろいろいじっていたのですが、多くの変更が 力技 | 黒魔術 って感じでエレガントな記事を望む皆様にはふさわしくないような気もしました。そこで、コミットログをあさってみたら、型推論もどきでガードを消しちゃうよというネタがちょっとアカデミックで良いのではないかと思って書いてみます。 型を格納する構造体 mrubyのJITでは各RITE VMの命令ごとにいろんなコンパイルやネイティブコードの実行に使う情報を格納するmrbjit_code_infoという構造体を用意しています。*1この構造体はこんな感じの定義です。 typedef struct mrbjit_code_info { mrbjit_code_area code_base; mrb_code *p
あなとみー おぶ mrubyのJIT (その11) - miura1729の日記
とってもお久しぶりです。ずいぶん間が空いてしまいましたが、新たな機能のプリミティブのインライン化が実装できたので再開したいと思います。あなとみー おぶ mrubyのJIT の開始当時オリジナルmrubyの数割速いとか遅くなるとか言っていましたが、現在大体のベンチマークでmrubyの2〜4倍の速度が出ます。その秘密が今回紹介するプリミティブのインライン化です。 Rubyはかなり基本的な機能もすべてメソッド呼び出しで実装されています。これは、必要に応じて動作をカスタマイズしたりして柔軟性をもたらしますが、速度的には大きなハンディになります。とくに、mrubyはメソッド呼び出しのオーバーヘッドが大きいので問題になります。 そこで、mrubyのJITでは良く使うメソッドについてはインライン化して速度を稼ぐようにしました。 インライン化を支えるコード 具体的なコードを見てみましょう。 これは、arr
あなとみー おぶ mrubyのJIT (その10) - miura1729の日記
お久しぶりです。ここんとこしばらくProcオブジェクトのサポートを作りこんでました。これが無いとイテレータとかみんなVMに戻ってしまって性能が上がらないのです。実はProcオブジェクトをサポートしてもあまり性能が上がらなかったのですが…。 で、この作業ですごくとりにくいバグがいっぱい出て数カ月デバッグ三昧という感じでした。おかげてうまく動くようになると却って落ち着かないという状態なのですが、それはそれとしてそのデバッグで作ったツールを紹介したいと思います。全国に31名くらいいると思われるmrubyでJITコンパイラを作っている人たちに参考になれば幸いです。 デバッグしていて困るのはどの命令を実行していた時にバグったのかが分からないことです。vm.cで実行していた場合は命令毎に処理が分かれているのでまだいいのですが、ネイティブコードでバグった場合(例えばセグフォしたばあいとか)、mrubyの
あなとみー おぶ mrubyのJIT (その8) - miura1729の日記
かなり間が空いちゃいました。その間にmrubyのJITをコーティングしたりお祭りの資料を作ったりしていました。結構内容が変わって、例えばこれまで説明していたものがjit.cからvm.cに移ったりしています。そんなこんなで結構速度が上がって(多くがwannabe53さんのおかげ)、もうすぐオリジナルの2倍速くらいか(単純なループなら4倍くらいだけどメソッドコールが入ると速度が落ちる)というところまで来ています。 さて、今回はjitcode.ccの説明です。 const void * mrbjit_emit_code(mrb_state *mrb, mrbjit_vmstatus *status) { MRBJitCode *code = (MRBJitCode *)mrb->compile_info.code_base; const void *rc = mrbjit_emit_code_a
あなとみー おぶ mrubyのJIT (その7) - miura1729の日記
祝その7、前回(ytljitの型推論)も前々回(yarv2llvm)も第６回くらいで挫折したんだよな。まああいつらよりは説明しやすいのですが。 そういうことで、無事にかは知らんけど拡張asmを超えて続きを説明します。ちなみに、今やっているのはjit.cのmrbjit_dispatchです。前回２回使って70行くらいしか説明していなんだな。どうでもいいことだけど。 ネイティブコードを実行して、無事戻ってきたところからです。 irep = *status->irep; regs = *status->regs; n = ISEQ_OFFSET_OF(*ppc); if (irep->ilen < NO_INLINE_METHOD_LEN) { caller_pc = mrb->ci->pc; } else { caller_pc = NULL; mrb->compile_info.nest_l
あなとみー おぶ mrubyのJIT (その6) - miura1729の日記
かなり間があいちゃったけど、予告通りgccの拡張asmをつかったネイティブコードの呼び出し部分の説明を行います。gccの拡張asmはインラインアセンブラのくせに最適化して書いたコードのようにアセンブラを生成してくれないことがあるばかりか、変数が割り当てられたレジスタとかも警告なしで破壊してくれます。自分の足を撃つことができる言語っていうフレーズが良く使われていますが、血管や神経を避けて常に足に向けて撃つのが拡張asmです。 拡張asmは文法が複雑なんですが、さすがにこんなお化けを相手にする人は優秀な人が多くて(ここに例外がいるが・・・)、解説記事はどれも分かりやすいです。たとえば、これとか http://d.hatena.ne.jp/wocota/20090628/1246188338 それでは、具体的に解説していきます。拡張asmやX86の命令の説明をその都度行っていこうかと思います。ネ
あなとみー おぶ mrubyのJIT (その2) - miura1729の日記
前回の1.10001・・・は最初に証明された超越数の10倍でした。 私が積読してあることで名高い「人月の神話」には、つぎのようなくだりがあります。 私にフローチャートを見せられて、テーブルを見せないとしたら、私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せてもらえるなら、フローチャートは大抵必要なくなる そういうことで、mrubyのJITの解説第二回目はデータ構造です。 よく言われることですが、mrubyには大域変数が無く代わりにstate構造体(mrb_state)を定義してそのポインタをほぼすべての関数に引数として渡すようにしています。このような構造はVMを複数作れるとか嬉しいことが多いのですが、mrubyのJITに関しても恩恵にあずかっています。この恩恵については後で説明しますが(伏線回収できるかな？どきどき)、mrb_stateにちゃっかりJITで使う変数も忍ばせています
あなとみー おぶ mrubyのJIT (その1) - miura1729の日記
ふと思い立ってものすごく影の薄いmrubyのJITの内部構造を説明することにしました。mrubyのJITは正式名称がないというとてもかわいそうなmrubyのフォークですが、オリジナルのmrubyの1〜3割(倍じゃないのに注意)速いようです。ここにあります、 https://github.com/miura1729/mruby さて、mrubyのJITはTracing JITなるものを使っています。第一回目はTracing JITの説明をしたいと思います。コードの解説はしないので、そういうのが読みたい人はTwrtter (@miura1729)かコメントで続きはよとつっついてください。 Tracing JITは今やLuaJIT, Pypyをはじめとするいろんな処理系で使われていますが、あまり解説記事はないようです。ただ、http://dodgson.org/omo/t/?date=20080
JIT on Tamarin Tracing - Backnumbers: Steps to Phantasien
前回のつづき. 今日は JIT を眺めてみます. そのまえに少し補足. TT のコードはまだ登場したばかりで, じゃんじゃん書き変わっている. なのでここで書いている内容は早々古くなってしまう. どんな勢いで書き変わっているかというと, たとえば前回紹介した TT Forth の "SUPER:" は もうすぐ撤廃される. (該当bug.) かわりに fc.py が命令列の長さから半自動的に superword を生成するようになる. ついでに Interpreter.cpp に書かれていた IL プリミティブの実装 C++ コードが vm.fs のインラインに埋め込まれるようになる. (semantic aciton みたいなもんですね.) そんなわけなので, あとから照合して「全然違うじゃん!」と怒らないようにしてください > いつかぐぐってやってくる方々. Tracing Tree
Know yourengines velocity2011
1. Know Your Engines How to Make Your JavaScript Fast Dave Mandelin June 15, 2011 O’Reilly Velocity 2. 5 years of progress... 10 JavaScript 7.5 C run time vs. C 5 2.5 0 2006 2008 2011 one program on one popular browser: 10x faster! 3. ...lost in an instant! function f() { var sum = 0; for (var i = 0; i < N; ++i) { sum += i; } } function f() { eval(“”); var sum = 0; for (var i = 0; i < N; ++i) { su
ytljitの型推論の説明(その6) - miura1729の日記
なんだかんだで、2か月以上さぼってました。その6です。 今回はsame_typeの実装の話です。 same_typeはdstというノードがdsigというシグネチャでノードが存在するメソッドやブロックを実行している時、srcというノードのssigというシグネチャでの型と同じになると設定します。same_typeの実際のコードを見てみましょう。 def same_type(dst, src, dsig, ssig, context) if dst.is_a?(BaseNode) then src.ti_add_observer(dst, dsig, ssig, context) end ti_update(dst, src, dsig, ssig, context) end ti_add_observer ti_update の2つのメソッドが出てきました。この2つを順に説明します。 ti_a
ytljitの型推論の説明(その5) - miura1729の日記
今回は、collect_candidate_typeの説明です。candidateとは候補とかそういった意味です。つまり、そのノードの型になる候補(複数かもしれないし0かもしれない)を収集します。前回説明したとおり、この候補から型を選び出すのが、decide_type_onceです。 collect_candidate_typeは引数にcontextを１つとり*1、contextを返します。 collect_candidate_typeの中で別に何をしてもよいのですが、主に行うのは次の3つです。このうち最初の２つの操作については、すべてのノードのスーパークラスのBaseNodeクラスでメソッドが定義されているのでこれを使います。 型候補を加える(add_type) 他のノードと同じ型だよということを設定する(same_type) 他のノードに対して、 collect_candidate_t
ytljitの型推論の説明(その4) - miura1729の日記
ytljitでao benchが動いたらruby-listにアナウンスするんだ！と決めているのですが、なかなか動かなくて苦労しています。 さて、型推論の説明の続きです。ytljitではYARVの命令列をノードと呼ぶオブジェクトのグラフ(VMと呼んでいる)に変換し、その後そのグラフをトラバースして機械語に変換します。ちょうどノードはYARVと機械語の中間くらいの命令に相当します。YARVや機械語のようにシーケンシャル(ジャンプはあるけど)ではなく、グラフ構造になっているのは型推論のためです。関連のあるノードを素早く(O(1)で)アクセスするためです。 型推論はこんな手順で行います データフロー解析を行ってデータの依存関係を調べる。例えば、ローカル変数の参照を表すノードなら、この変数に値を設定したノード(分岐やジャンプがあるので1つとは限らない)を集める 次のようなことを各ノードについて行う。
ytljitの型推論の説明(その3) - miura1729の日記
しつこいようですが、シグネチャーはメソッド呼び出しの際の引数を推論した結果の型オブジェクトの配列です。そして、型推論の際には必ずシグネチャが必要になります。 この2つのことから勘のいい人は気づくかも知れませんが(私はプログラムしてバグるまで気づかなかった)、シグネチャーを作るのにシグネチャーがいるのです。普通のメソッドだとそれほど問題ではないのですが、ブロック付きのメソッドの場合、シグネチャの型が一発で決まらないので、この辺の話が重くのしかかります。これが(その1)で書いたバグの根本の原因であろう(まだ取れてないので想像)と思うのですが、この辺はよくわかってないので分かったら書きます。 次にメソッドの引数の話をします。ytljitではユーザが指定する普通の引数のほかに隠れ引数を渡します。隠れ引数は現在のところ次の3つです(例外処理とかで増えるかもしれない)。 親のブロックまたはメソッドのフ
ytljitの型推論の説明(その2) - miura1729の日記
2回目はシグネチャーを作る話です。シグネチャーはメソッドの引数の型オブジェクトを配列でまとめたものです。型オブジェクトという未定義の言葉が出てきたので、これから説明します。 型オブジェクトはRubyのクラスをWrapしたオブジェクトです。型オブジェクトはBOXING/UNBOXINGの2種類があり、Rubyのクラスと独立して設定できます。つまり、BOXINGなFixnumもUNBOXINGなArrayなんてのも表現可能です。それぞれの型オブジェクトは、次のようなメソッドを持っていて、コード生成時にあんまり型による場合分けとかせずに、型推論の結果による最適化が出来るようになっています。 gen_boxing (BOX化するアセンブラコードを生成する) gen_unboxing (UNBOX化するアセンブラコードを生成する) gen_copy (そのクラスのデータをコピーするコードを生成する)
ytljitの型推論の説明(その1) - miura1729の日記
今、ytljitでうまく推論出来ないプログラムがあっていろいろ直しています。うまくいかないプログラムはこんな感じのものです。 def f yield end f { 1 + 1} f { "abc"} このバグの話の詳細を書くと訳わからなくなるし、詳細はどんどん変わっいるのでそれは書きません。その代り大元の考え方を書いて考えを整理します。つまり、自分のための日記です。 Rubyの型推論ということで余り型を厳しくしてしまうと使いにくくなってしまいます。ytljitのポリシーとして型によるプログラムの検証は一切無視、できるだけオリジナルのRubyのプログラムを受け入れるとします。そうすると例えば、こんな感じのプログラムは推論したいところです。 def id(x) x end id(1.0) id("abc") メソッド単位で型付けをすると考えるとidの戻り値の型は決められない(またはObjec
[VM][JIT]Brainf*ckで学ぶスクリプト言語処理系高速化。インタプリタ→VMインタプリタ→JITコンパイラ。 - hogelogの日記
スクリプト言語処理系を高速化したくてしたくてたまらない少年少女に届け。表題の通りスクリプト言語処理系の高速化について書きます。対象言語はBrainf*ckにします。Brainf*ckというのは Brainf*ck Brainfuck - Wikipedia というような言語です。要は処理系を実装するのが簡単なおもちゃ言語。おもちゃ言語ゆえに他のどんな実用的スクリプト言語処理系にも出てくるような基本的な処理だけでできているので、Brainf*ck処理系の高速化で有用なテクニックは他の処理系でもうんたらかんたら。 じゃあまず叩き台になるような処理系を書いてみましょう。言語はC++です。JavaだのPythonだので高速な処理系を記述するテクニックやらなんやらというのもありますけども、まずはごく簡単にCPUやらメモリといったものと仲の良い言語で記述することで理解を深めましょう。本当はC言語の方が
![[VM][JIT]Brainf*ckで学ぶスクリプト言語処理系高速化。インタプリタ→VMインタプリタ→JITコンパイラ。 - hogelogの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/2769bb4727fa549a477e8806ecae7ad9c2303ec3/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F12704346814673895633%2F12921228815733205071%2F1411114774)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.