Hatena::ブログ(Diary)

miura1729の日記 このページをアンテナに追加 RSSフィード

2014-10-15

全くコンピュータの知らない人にTracing JITコンパイラを説明する試み (その1)

19:28 |  全くコンピュータの知らない人にTracing JITコンパイラを説明する試み (その1)を含むブックマーク  全くコンピュータの知らない人にTracing JITコンパイラを説明する試み (その1)のブックマークコメント

少し忙しいのですが、なんとなく全くコンピュータのことを知らない人にTracing JITを説明する文章が書きたくなったので、書いてみます。うまくいくかなー

私はTracing JITコンパイラを書いているわけですが、インターネット上ではなくリアルで会う人にJITコンパイラと言ってもほとんどの場合、通じません(通じる人もいる)。世の中そんなものだと思ったのですが、JITコンパイラとうっかり発したとしても、その後話が続くとどんなに素晴らしいことでしょう。

コンピュータとは?

 世の中にはコンピュータというものがあって、広く使われています。これを読んでいる人は携帯電話を使っている、もしかしたらスマートホンを使っている人がいるかもしれませんが(私はスマートホンを使っていませんが)、これはコンピュータの応用品というかほとんどコンピュータです。

コンピュータは日本語で電子計算機と訳されることからわかるとおり、計算をする機械です。計算というとお金の計算とか以外何に役に立つの?とか思うかもしれませんが、いろいろな物を数に置き換えると計算でいろいろなことができるのです。たとえば、携帯電話は声を数に変えることで遠くの人に声を伝えています。声を聞き取りやすくしたりそういうことも計算で出来ます。

コンピュータは計算が速く正確に出来るのですが、あまり難しいことはできません。出来ることは、足し算とか掛け算、せいぜいルートとか三角関数くらいです。でも、コンピュータはとても難しい計算をしているのはなぜでしょう?

コンピュータは単純な計算しかできませんが、計算を繰り返したり計算結果を記憶しておくことができます。このようなコンピュータの機能を利用すると、どんなに複雑な計算も簡単な計算の組み合わせることで、可能になるのです。

では、簡単な計算を組み合わせて複雑な計算にするのはだれがやるのでしょう?それは、人間です。そのようなことを行う人はプログラマーと呼ばれています。

社長の苦悩

  コンピュータにこういう計算をしなさいと命令するのは大変なことです。ここで、プログラマの仕事を会社の社長に例えてプログラマの苦労を説明したいと思います。

あまり、融通のきかない新入社員のM君(コンピュータの例え)は自分では何も考えません。でも、言われたことは非常に正確にこなします。今も昔も新入社員は自分で考えない、指示待ちだと言われるのは変わらないわけですが、M君はレベルが違います。右ひじを10度曲げろとか、親指の第二関節を15度動かせとかそんな感じじゃないと動かないのです。社長はほかにもやることがいっぱいあるのにM君の指示をするのに精いっぱいです。その代わり、指示されたことはどんなにたくさんあっても、素早く正確にこなすことができます。

 社長はM君の扱いに困り果ててしまいましたが、ある日いいことを思いつきました。係長のB君にM君の命令係をやってもらうことです。社長が、B君に「隣の部屋から茶碗をとってこい」と命令すると、B君はM君に命令して手足を動かして茶碗を取ってくるように動かすのです。これで満足と思ったのですが、B君は社長に比べて命令の仕方が下手で、M君はときどき意味もなく腕をぐるぐる回したりして、社長が直接命令するより作業に時間がかかるのです。

B君のような存在が、実際のコンピュータではプログラミング言語と呼ばれているものです。現在ではプログラマコンピュータを直接命令するようなことはまれで、プログラミング言語を使ってコンピュータに命令することがほとんどです。

Cさん登場

 M君に命令するのに自分でやっていたら大変、B君に頼んだらM君の力を生かせられない。困った社長の前にCさんが登場しました。Cさんは、B君のように逐一M君に寄り添って命令する代わりに、「隣の部屋からお茶碗取ってこい」と命令すると徹夜で"隣の部屋からお茶碗持ってくる完全マニュアル"を作るのです。次の日、M君に渡すとM君はそれを読んで、社長が直接命令するくらい素早く茶碗を取ってくるのです。

一晩じっくり考えたマニュアルだけあってあまり無駄な動きはありません。むしろ社長の命令の方が無駄があるくらいです。

CさんもBさんのように、人間が楽な手段でコンピュータに命令するようにするものなので、プログラミング言語と呼ばれます。そして、Cさんのようにあらかじめコンピュータ理解しやすいマニュアルを作るのをコンパイラ、B君のように逐次コンピュータに命令するのをインタプリタと呼びます。

 今お茶が飲みたい

 これですべて解決と思ったわけですが、人間の欲望とは限りないものでございます。社長はお茶が飲みたくて茶碗持ってこいと命令したのに、お茶が飲めるのは次の日の朝ということになってしまいます。これならB君の方がましだとも思ったものでした。

そんなとき、S君が名案を思いつきました。C君の作る"隣の部屋からお茶碗持ってくる完全マニュアル"には、「核攻撃を受けた時、首相官邸に連絡して危機管理センターのメンバーを招集する」とか、あまり使わない状況の命令も入っているのですが、たとえば「歩く」とか良く使う命令だけマニュアル化すればいいのではないかと。

でも、何が良く使う命令なのか普通は分かりません。また、突然核攻撃を受けるとか可能性の低い事態が起こるかもしれません。そこで、S君は初めはB君のようにM君に逐一命令を出します。命令を出しながらM君がどういう動作をたくさんやっているかもメモしていきます。隣の部屋からお茶碗を持ってくるという動作だと多分、「足を動かして歩く」あたりになるでしょう。そして、たくさんやっている動作が分かったら、M君にしばらく寝て貰って、その場でマニュアルを書くのです。マニュアル作成は「歩く」とか限定されたものだから速くできるでしょう。

また、お茶碗を取りに行ったときに核攻撃を受けた場合はS君がまた登場し、首相官邸危機管理センターのメンバーを招集するように、逐一命令を出すようにします。

こんな感じで社長は一晩待たないでもお茶が飲めるようになりました。めでたしめでたし。

S君のように良く使うところだけ実行中にマニュアルを作成するのをJITコンパイラと呼びます。JITとはJust In Timeの略で"ちょうど良いときに"とかそんな意味です。

さらに無駄を省く

S君の方法(JITコンパイル)でも大体いいのですが、もっとマニュアルを書く時間を省く方法があります。たとえば、「歩く」でマニュアルを書くわけですが、歩くにも足音をたてないようにすり足にしたり、競歩で速く歩くとかいろいろ場合があるわけです。その中でお茶碗を隣の部屋に取りに行く歩き方だけをマニュアルにすればもっと早くマニュアルができます。

また、M君はただ歩くだけではなく、社内のかわいこちゃん(死語)のDさんがいないか確認する必要があります。見つけたら、「相変わらず可愛いね。今度、一緒に飯でもどう?」と声をかけるためです。これも一緒にマニュアル化したいとか考えると、、通り一遍に「歩く」をマニュアル化するのでは無駄が生じるしDさんを見ることが漏れてしまいます。

そこで、新たにM君の上司に任命されたTさんはM君の命令をしつつ、M君の行動をつぶさに観察します。そして、この動作を繰り返しているというものを発見したら、それをマニュアル化します。たとえば、「隣の部屋からお茶碗を持ってくる」だったら、「一歩踏み出して、Dさんがいないか確認する」ことを繰り返しているので、これだけをマニュアル化するのです。

Tさんのように動作を観察して、動作を繰り返しているところだけをマニュアル化する方法をTracing JITと呼んでいます。こうすると、Tracing JITは万能のようですが、もちろんそんなわけはありません。気が向いたらがあればもっと効率を上げる方法、Tracing JITにつきもののガードとか説明したいと思います。

続く

2014-08-20

君たちの愛したmruby-profilerは復活した(その3)

20:26 |  君たちの愛したmruby-profilerは復活した(その3)を含むブックマーク  君たちの愛したmruby-profilerは復活した(その3)のブックマークコメント

では、どうやってIREP構造体とprof_irep構造体を結びつけたのでしょうか?この説明の前にIREP構造体とは何かを思い出してみましょう。IREP構造体はVMの命令の一塊をVMが扱いやすいように補助的な情報とともにまとめたものでした。IREP構造体はメソッドとかブロックのVMが扱いやすい形式ともいえます。こういうことから、あるcode_fetch_hookの呼び出しとその前のcode_fetch_hookで渡ってくるIREP構造体が違う場合、次のような原因が考えられます。

つまり、code_fetch_hookにあるIREP構造体(ここではAとします)が渡されたと分かっている時、次に渡ってくるIREP構造体は大体絞られるわけです。つまり、A中で呼び出しているメソッドのIREP構造体か、Aを呼び出したIREP構造体です。また、Rubyの場合あるメソッドがどのメソッドを呼び出すかは変なことをしなければ、大体静的に決まります。

そんな感じで次のような感じで結びつけます。ちょうどコールグラフを作る感じと言うとイメージしやすいかもしれません。

  • prof_irep構造体に次のようなメンバーを加える。prof_irepはmruby-profiler側で定義するのでメンバーの増減は自由自在です。
    • prof_irepに対応するIREP構造体(irep)
    • 現在のIREP構造体(メソッドやブロック)が呼び出したメソッドやブロックのprof_irep構造体(child)
    • 現在のIREP構造体を呼び出したメソッドやブロックのprof_irep構造体(parent)
  • 前回のcode_fetch_hookを呼び出したときのprof_irepを覚えておくcurrent_prof_irep変数(グローバル変数(笑))を用意する。
  • code_fetch_hook中ではcurrent_prof_irepに対応するIREP構造体と引数で渡ってきたIREP構造体が違うか調べる。同じなら問題ない。違うならprof_irep構造体を探さないといけない。探す手順はこんな感じ
    • current_prof_irepのchildメンバーの配列に入っているprof_irep構造体を調べる。もしchild中のprof_irep構造体が探しているIREP構造体に対応するものなら、current_prof_irepをそのprof_irep構造体にして検索終わり
    • childメンバーになければ、parentメンバーに入っているprof_irep構造体を同様に調べる。なければさらにpraentを辿り呼び出し履歴の最後まで調べる。見つかれば、childの時と同じでcurrent_prof_irepに設定する。
    • 見つからなければ、新たにprof_irep構造体を作り、current_prof_irepのchildの配列に加える

いろんな疑問点もあるでしょう。想定問答集です。

  でっかいメソッドを作る方が悪い

  • この方法だとあるIREP構造体に対応するprof_irep構造体がたくさんできない?

  はい出来ます。ただし、無限に出来ることはないはずです。最後に結果を表示するときに集計する必要があるでしょう。逆にgprofのようなコールパスごとの実行時間も得られるはずです。まだ実装していませんが。

  • IREP構造体がGCされちゃったら大丈夫?

  うっ!それは・・・

  • 勘のいいガキは嫌い?

  はい!

そういうわけで、IREP構造体がGCされるとまずいのでIREP構造体中の参照カウンタをいじってGCされないようにしています。mruby-profilerからだとIREP構造体がGCされたかわかる方法が無いので仕方が無いですね。ファイナライザーがあればいいのですが 

と、最後はいいわけになってしまいましたが、無事終わりました。それではごきげんよー

2014-08-19

君たちの愛したmruby-profilerは復活した(その2)

19:48 |  君たちの愛したmruby-profilerは復活した(その2)を含むブックマーク  君たちの愛したmruby-profilerは復活した(その2)のブックマークコメント

昨日の続きで、irepメンバーとIREP構造体中のirepメンバーのインデックスがなぜ必要だったのかを説明します。

プロファイル情報はどこにあるの?

  プロファイラはかかった時間とか実行回数を(メソッド、行、命令)レベル(Profilerによる)で数えて後から分かりやすく表示するソフトです。ですので、どこかに数えた結果を持っていなければなりません。

mruby-profilerの場合はVMの命令ごとに実行時間を数えます。VMの命令はIREP構造体に格納されているので、命令毎の実行時間もIREP構造体に入れておくのが一番いいのですが、mruby本体に手を入れる必要があり、メモリ制約の厳しいmrubyにプロファイル用のメンバーを入れて貰うのは期待できません。

そこで、mruby-profilerはprof_irep構造体というプロファイルのための構造体をIREP構造体ごとに用意して、そこに実行時間などを格納するようにしました。この方法だと、問題が1つ残ります。IREP構造体とprof_irep構造体をどうやって結びつけるかです。

命令の実行時間を計測するために、code_fetch_hookの仕組みを使うのですが、code_fetch_hookは現在実行中のIREP構造体は引数としてもらえるのですが、それに対応するprof_irep構造体はなんとかIREP構造体から得る必要があります。

やりたいことは単なる連想配列なんですが、実行時に実行対象のIREP構造体はメソッドの呼び出しとかリターンとかで頻繁に変わりますし、VMの命令実行ごとに行われる処理なので、とにかく高速におこなうことが必要です。ハッシュテーブルを作るとかだとおそらくすごく遅くなるでしょう。

これまでの方法

 これはでは、mrb->irepがすべてのIREP構造体が入っている配列であることを利用して、mrb->irep配列と同じ長さのprof_irep配列を用意して、IREP構造体に対応するprof_irep構造体を格納します。こうすれば、prof_irep配列を経由して、IREP構造体からprof_irep構造体が結び付けられるわけです。

こんな感じのコードになります。

  idx = irep->idx                           /* IREP構造体のインデックス値を得る */
  current_prof_irep = prof_irep_array[idx]; /* IREP構造体に対応するprof_irep構造体を得る */

IREP構造体をGC出来ないことを除けば、かなり効率のよい方法です。irep->idxとかmrb->irepが無くなった今、別の方法を考えなければなりません。半年間いい方法が浮かばなかったのですが、ふとこの方法ほどではないのですが効率的な方法が浮かんだのでそれを実装しました。それが、今回の復活の決め手です。

それでは次回、ごきげんよーさようなら

2014-08-18

君たちの愛したmruby-profilerは復活した(その1)

20:20 |  君たちの愛したmruby-profilerは復活した(その1)を含むブックマーク  君たちの愛したmruby-profilerは復活した(その1)のブックマークコメント

  お盆休みの一部を利用して、mruby-prpfiler(https://github.com/miura1729/mruby-profiler)を復活させました。

mruby-profilerって何?

mruby-profilerはVMの命令ごとに実行時間を数えていて、rubyソースコードVMの命令レベルで実行時間を表示してくれるというものです。フィボナッチを実行すると、こんな感じの出力が最後に出ます。


0000 0.00000 # Fib 39
0001 0.00000
0002 0.00000 def fib n
0003 4119.25760   return n if n < 2
             204668309 586.53534    MOVE
             204668309 666.29443    LOADI
             204668309 927.08844    LT
             204668309 1377.01244    JMPNOT
             102334155 562.32694    RETURN
0004 5941.06001   fib(n-2) + fib(n-1)
             102334154 301.43419    LOADSELF
             102334154 375.47193    MOVE
             102334154 472.92432    SUBI
             102334154 1341.11332    SEND
             102334154 318.84731    LOADSELF
             102334154 347.61494    MOVE
             102334154 446.54848    SUBI
             102334154 1346.05755    SEND
             102334154 364.15757    ADD
             102334154 626.89040    RETURN
0005 1139.70203 end
             204668310 1139.70185    ENTER
                     1 0.00008    LAMBDA
                     1 0.00010    METHOD
0006 0.00000
0007 0.00508 puts fib(39)
                     1 0.00003    LOADSELF
                     1 0.00000    LOADSELF
                     1 0.00002    LOADI
                     1 0.00015    SEND
                     1 0.00011    SEND
                     1 0.00477    STOP

1カラム目から始まる行がRubyレベルで、行番号、実行時間、Rubyレベルのソース。インデントされているのがVMレベルで、実行回数、実行時間、命令(オペコードとかは表示されない今後改善予定) です。

実行時間の単位はrdtscの出力をそのまま使っているのでよくわかりません。大きい数字なら時間がかかっているということで。

これを見れば、どこを直せば速くなるか一目瞭然ですね。そんな、甘くはないのですけど。

復活って?動かなかったの?

mruby-profilerは去年の10月に出来ていたのですが、今年の3月ごろに使えなくなりました。その理由はmrubyが変わってしまったため。もっと具体的に言うと、mrb_state構造体にirepというメンバーが無くなったためです。

irepメンバーはすべてのIREP構造体が入っている配列です。しかも、IREP構造体にはirepのどこに入っているかのインデックスがありました。IREP構造体は、mrubyのソースコードVM命令にコンパイルした結果が、リテラルテーブルとかシンボルテーブルなんかの実行に必要な情報とともにまとまっている構造体です。

なぜなくなったかと言うと、IREP構造体もGCの対象になるようにしたからです。irepメンバーにすべてのIREP構造体が入っていればどこにも指されないという条件は常に成り立たないわけです。irepメンバーが無ければ、必要のないIREPは死んでもらえるわけです(そう、花●とアンのように)。

ところが、mruby-profilerはirepメンバーとIREP構造体のirepメンバーのインデックスに大いに依存して作られていました(過去形)。

今日は炎天下の草取りで疲れたので、この辺で。ごきげんよう、またお会いしましょう。

2014-05-27

水道屋の僕が無人島に持っていきたい本

12:20 |  水道屋の僕が無人島に持っていきたい本を含むブックマーク  水道屋の僕が無人島に持っていきたい本のブックマークコメント

@matsumotoryさんの面白い記事 「インフラエンジニアの僕がキーボードのすぐ隣に置いておきたい本」 http://blog.matsumoto-r.jp/?p=4279 をぱくって記事を書いてみました。

手元に置いておきたいが、置いているわけじゃない5冊

Common Lisp 第二版 (http://www.amazon.co.jp/dp/4320025881)

一見、無味乾燥ですが面白い本です。「処理系の注」と「論理的根拠」のところをしっかり読みましょう。世の中には深く深くものを考える人がいるのだなと分かります。

初めてのRuby (http://www.amazon.co.jp/dp/4873113679)

プログラミング言語を使えるようになるだけならいろんな本もあるし、ネットでただで手に入れることもできるわけですが、言語のバックグラウンドにある思想も含めた優れた解説はなかなかお目にかかりません。

ハッカーのたのしみ (http://www.amazon.co.jp/dp/4434046683)

はっきりいってここで解説されている技法を仕事で使ったら、その仕事がコンパイラOSの開発じゃなければ9割がた怒られるでしょう。でも、プログラムの限界というのはそう自明じゃないことを教えてくれます。

Winnyの技術 (http://www.amazon.co.jp/dp/4756145485)

高速なシステムを作るのにこの本以上に役立つ本はなかなか無いでしょう。この作者の才能をつぶした京都府警は「ばかじゃないの?」としか言えないです。

素晴らしき数学世界 (http://www.amazon.co.jp/dp/4152093021)

進歩の速いコンピュータの世界(本当かな?)で長くとどまるには、コンピュータが扱う「数」というものに固定概念を持つべきではないと思います。この本はあらゆる角度から数に関する固定概念を崩してくれることでしょう。

 まとめ

当然ですが、ほかにも面白い本はたくさんあります。また、こんな記事が書けるほど素晴らしい本に出会いたいです。