サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
掃除・片付け
miura1729.hatenadiary.org
今回はオブジェクト作成のメソッドnewのインライン化のお話です。newのインライン化はそれほど規模が大きくないのですが、mrubyのJITの大きな転換点になっています。 前回取り組んだytljitがRubyの型推論(ブロックや要素ごとに違う型が格納できる配列などを含む)やオブジェクトのスタック割り付けなどを行って複雑すぎて手に負えなくなっちゃったことがありました。その反省を踏まえて、できるだけオーソドックスに分かりやすく気を使っていました(結果どうなったかは知らない)。 ところが、aoベンチでオブジェクトの生成がボトルネックっぽいと分かったことでnewをインライン化を初めて、検討の結果またも悪魔に魂を売り渡してしまいました。その、技法とは「バイトコードの書き換え」です。 newの難しいところはオブジェクトを生成した後、initilaizeメソッドを呼ばないといけないところです。簡単じゃない
少し忙しいのですが、なんとなく全くコンピュータのことを知らない人にTracing JITを説明する文章が書きたくなったので、書いてみます。うまくいくかなー 私はTracing JITコンパイラを書いているわけですが、インターネット上ではなくリアルで会う人にJITコンパイラと言ってもほとんどの場合、通じません(通じる人もいる)。世の中そんなものだと思ったのですが、JITコンパイラとうっかり発したとしても、その後話が続くとどんなに素晴らしいことでしょう。 コンピュータとは? 世の中にはコンピュータというものがあって、広く使われています。これを読んでいる人は携帯電話を使っている、もしかしたらスマートホンを使っている人がいるかもしれませんが(私はスマートホンを使っていませんが)、これはコンピュータの応用品というかほとんどコンピュータです。 コンピュータは日本語で電子計算機と訳されることからわかると
とってもお久しぶりです。ずいぶん間が空いてしまいましたが、新たな機能のプリミティブのインライン化が実装できたので再開したいと思います。あなとみー おぶ mrubyのJIT の開始当時オリジナルmrubyの数割速いとか遅くなるとか言っていましたが、現在大体のベンチマークでmrubyの2〜4倍の速度が出ます。その秘密が今回紹介するプリミティブのインライン化です。 Rubyはかなり基本的な機能もすべてメソッド呼び出しで実装されています。これは、必要に応じて動作をカスタマイズしたりして柔軟性をもたらしますが、速度的には大きなハンディになります。とくに、mrubyはメソッド呼び出しのオーバーヘッドが大きいので問題になります。 そこで、mrubyのJITでは良く使うメソッドについてはインライン化して速度を稼ぐようにしました。 インライン化を支えるコード 具体的なコードを見てみましょう。 これは、arr
追記 LuaJITの作者Mike Pall氏より、twitterで次のようなアドバイスをいただきました。 1. No compiler is allowed to make this optimization. Floating-point arithmetic ist NOT associative. 2. Please use 'local' functions when publishing Lua benchmarks. 3. Please use the current version of LuaJIT. 訳(かなり怪しい) 1.このような最適化出来るコンパイラは無いよ。浮動小数点数の算術命令は結合的じゃないから 2. Luaのベンチマークを取るなら局所関数を使ってください 3. 最新バージョンのLuaJITを使ってください そういうわけで、ベンチマークを取り直します。 ベンチ
お久しぶりです。ここんとこしばらくProcオブジェクトのサポートを作りこんでました。これが無いとイテレータとかみんなVMに戻ってしまって性能が上がらないのです。実はProcオブジェクトをサポートしてもあまり性能が上がらなかったのですが…。 で、この作業ですごくとりにくいバグがいっぱい出て数カ月デバッグ三昧という感じでした。おかげてうまく動くようになると却って落ち着かないという状態なのですが、それはそれとしてそのデバッグで作ったツールを紹介したいと思います。全国に31名くらいいると思われるmrubyでJITコンパイラを作っている人たちに参考になれば幸いです。 デバッグしていて困るのはどの命令を実行していた時にバグったのかが分からないことです。vm.cで実行していた場合は命令毎に処理が分かれているのでまだいいのですが、ネイティブコードでバグった場合(例えばセグフォしたばあいとか)、mrubyの
今回からプログラムの説明です。今回はmrubyのVMの命令実行部分、vm.cのmrb_runにどうパッチを当てているかを見てみます。mrb_runは大まかに言ってこんな感じになってます。 初期化 命令取出し 取出した命令に当たる処理にジャンプ 命令の実行 2に戻る 3のジャンプはswitch/caseの場合とgotoの場合があります。mrubyのJITはgotoの場合( DIRECT_THREADED)の場合だけをサポートします。その理由は後で(珍しくこの回の中で)説明します。 JITを組み込んだ場合次のようになります。 初期化 命令の取り出し 命令がコンパイルされていればそれを実行する。全部コンパイルするわけではないので戻ってくる。この場合、2で取出した命令とは違うので再度命令を取出して5に飛ぶ もし可能ならば命令をコンパイルする。 取出した命令に当たる処理にジャンプ 命令の実行 2に戻
前回の1.10001・・・は最初に証明された超越数の10倍でした。 私が積読してあることで名高い「人月の神話」には、つぎのようなくだりがあります。 私にフローチャートを見せられて、テーブルを見せないとしたら、私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せてもらえるなら、フローチャートは大抵必要なくなる そういうことで、mrubyのJITの解説第二回目はデータ構造です。 よく言われることですが、mrubyには大域変数が無く代わりにstate構造体(mrb_state)を定義してそのポインタをほぼすべての関数に引数として渡すようにしています。このような構造はVMを複数作れるとか嬉しいことが多いのですが、mrubyのJITに関しても恩恵にあずかっています。この恩恵については後で説明しますが(伏線回収できるかな?どきどき)、mrb_stateにちゃっかりJITで使う変数も忍ばせています
謝辞を忘れていました。mrubyのJITはXbyak(http://homepage1.nifty.com/herumi/soft/xbyak.html)を使わせてもらっています。今まで、C言語の生成、LLVM、Rubyで書いた自作アセンブラなどでコンパイラを使っていましたが、Xbyakは一番使いやすいです。 某出版会(http://tatsu-zine.com/books/llvm)には大変申し訳ないのですが、個人的には速度とか移植性を考えないコンパイラならLLVMよりXbyakの方がお勧めです。移植性とか最適化したいとかの話になると途端にXbyakはハードルが上がりますが… 作者のherumiさんにはmrubyのJITを試し戴いてデバッグの協力まで戴きました。 https://github.com/miura1729/mruby/issues/1 本当にありがとうございます。 ちなみに
ふと思い立ってものすごく影の薄い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
Garbage Collection Advent Calendarの5日目の記事です。 私はGCが嫌いです。GCは幼稚で礼儀知らずで気分屋で 甘やかすといつまでも動き、ほったらかすとセグフォする。 そんなGCのために、私達人間は何もする必要はありませんよ ♪ ということで、GC撲滅の1方法としてLinear Lispなるものを紹介します。Linear Lispは線形論理という論理に基づいたLisp処理系です。 元論文はこれです。 Lively Linear Lisp -- 'Look Ma, No Garbage!' http://home.pipeline.com/~hbaker1/LinearLisp.html 線形論理については、ここのページが感動的なほどわかりやすいです。 線形論理って何? (情報科学演習 III 課題紹介(小林研究室)) http://web.yl.is.s.u
Garbage Collection Advent Calendarの3日目の記事です。 2日目の@nari3さんの記事を読んで、これまだ続きが書けるよとtwitterでつぶやいたら書くことになってしまいました。口は災いの元。 さて、@nari3さんの記事ですが面白いですね。メモリリークしたところが分かって便利ですね。でも、ちょっと考えてみてください。はたしてメモリリークしたオブジェクトに都合よくどこに所属しているか書いてあるでしょうか?そういうことで、どこの変数に格納されたオブジェクトかも探すようにしました。 これです。 #!ruby -W0 require 'objspace' def find_pilferer(leak_id, bind) eval("local_variables", bind).each do |nm| val = eval(nm.to_s, bind) rea
>>> @miura1729 RT @yppp: あーあ、llvm使って言語作りたいけどバイトコードの 組み立てかたがわからない・・・・・・、 あとBoehm GCの組み込みかたも・・・・・・、まずはASTを作れって話なんだけどなw ああ、やる気がほしいhttp://twitter.com/repeatedly/status/29599415588 ご指名戴いて嬉しかったのでちょっとまとめてみます。かなり間違い、偏りもあると思いますが、教えてもらえると嬉しいです。 LLVMを使ってコンパイラを書く場合、LLVMの命令を知らないと話にならないのでまずは、LLVMの命令を覚えます。 http://llvm.org/docs/LangRef.html でも、これ全部読んでも余り使わないと思います。とりあえず、 NamedTypes http://llvm.org/docs/LangRef.htm
YTLJitはコンパイル速度を上げるために、コンパイル途中の情報(VMと呼んでいる)をファイルに保存できるようにする予定です。VMはProcオブジェクトを多用しているので、ProcオブジェクトをMarshal出来るようにしました。結構込み入った話で、忘れそうなので仕組みを書いてみます。ProcオブジェクトのMarshalのソースはytljitの ext/ytljit.c lib/ytljit/ytljit/marshal.rbにあります。ytljitのソースコードは、 http://github.com/miura1729/ytljit です。 Procオブジェクトはオブジェクトが生成された環境を保持しているので、ProcオブジェクトをMarshalするにはその環境もMarshalしなければなりなせん。ところが、環境そのものはbindingメソッドで生成できるfirst class obj
kwatchさんの日記を読んで( http://d.hatena.ne.jp/kwatch/20100616/1276650107 )、未使用変数を指摘するプログラムを考えてみました。バイトコードを解析するという方針で、プログラムを作ってみました。Ruby1.9でしか動かないです。 http://gist.github.com/501900 こんな感じで使います。ちなみに、プログラム中にわざと1つ未使用変数が入れてあります。 bash-3.2$ ruby varcheck.rb varcheck.rb Unused variable 'a' in VarChecker#unused_check
私の知る範囲の動的に型づけされた言語の実現方法の資料をまとめてみました。英語は苦手なんで日本語中心です。 こういうのがあるよとか、こんなところにリンクしないでくれとかありましたら教えてください。 思い出したら追加します。 変更履歴 2009/12/13 初版 美しい日本のMLコンパイラを追加 動的言語を動的に型づけされた言語に変更 TAO/KCLを追加 2009/12/25 マルチパラダイム言語TAO追加 Garbage Collection http://wiki.livedoor.jp/author_nari/ Gauche http://practical-scheme.net/wiliki/wiliki.cgi?Gauche http://practical-scheme.net/chaton/gauche/ http://www.nicovideo.jp/watch/sm7543
MozReplでいろいろ遊んでいます。なかなか難しいですが、だんだん面白くなっています。MozReplを経由してちょうどWin32OLEみたいにRubyのオブジェクトとして、Javascriptのオブジェクトを扱えるようなクラスJSobjectを作ってみました。 こんな感じでまるでRubyを使っているかのようにJavascriptのオブジェクトが扱えます。 # サンプル # Helloのダイアログを出す $window.alert("Hello") # DOMを操作してみる puts $document.childNodes.item(0) # 自分の見ているURLの表示(高速インタフェース研究会より) puts $content.location.href ソースコードを下に晒しますが、とても汚いつくりです。特に、Rubyで参照したオブジェクトはGCされずにどんどんJavascriptの
不完全ですが、yarv2llvmからRuby/SDLを介してSDLが使えるようになりました。こんな手順で使えます。 Ruby/SDLをインストールしてください(http://www.kmc.gr.jp/~ohai/rubysdl.html) yarv2llvmについては、ここのもの(SDLブランチ)を使ってください(http://github.com/miura1729/yarv2llvm/tree/sdl) ruby yarv2llvm.rb -r y2llib/sdl.rb プログラム名と、-rオプションをつけて起動してください Ruby/SDLに添付されているサンプルを動かそうとするとほとんど動きません.少なくともrequire 'sdl'はコンパイルエラーになるので、削除してください。Ruby/SDLはy2llib/sdl.rbで読み込んでいます. 取り合えず、sampleディレク
今、LLVMのソースを読んでいます。そしたら、recompileAndRelinkFunctionなるメソッドを見つけました。後は、実行中のフレームを書き換える目処が付いたらLLVMでon-stack replacementできそうです。フレームを書き換えるところは、GC APIが有望そうなのですが、果たしてどうなることか・・・。 この日記は、Wikiみたいにすると後でいろんなページに飛ばなくて済むから便利かなと思って、新しいエントリーを起さずに更新を繰り返しています。更新履歴を書くようにしました。最後に更新した小項目を前に持ってくるようにしました。ただし、更新履歴, yarv2llvmへの応用のまとめは常に先頭です。 更新履歴 2009/04/06 ShadowStackについて更新しました。 2009/04/06 更新履歴を作りました。 yarv2llvmへの応用のまとめ 結局、gcr
LLVM勉強会の途中で笹田さんたちと話した内容です。 さ ささださんたち み 私(みうら) 互換性をUPさせる方策 さ トップレベル環境はあえてコンパイルしないようにすると互換性が取りやすいのではないか。例えば、 if $debug then def foo デバッグバージョン end else def foo リリースバージョン end end という感じのプログラムはコンパイルせずにインタープリタで実行すると却って効率がよさそう み メソッドが再定義される場合はトップレベルじゃなくてもありえるから結局再コンパイルは必要。だからトップレベルでもコンパイルして必要なら再コンパイルしたほうがすっきりすると思う。 on stack replacement さ 再コンパイルするとon stack replacement(実際にはこの言葉私は知らなかったので呼び出し元を書き換えられるかという感じで
今回は型推論の話の簡単なところです。Rubyは素直に型推論できるようにできていないので、yarv2llvmではいろいろad-hocな例外を組み込んでいますが、今回はそれらは一切無視です。素直に型が一意に決まり、決まらないときはエラーで弾く場合を想定しています。 型の管理を行うため、yarv2llvmでは扱うすべてのデータに対して、1つづつRubyTypeクラスのオブジェクトを用意しています。扱うデータとは、例えば変数、リテラル、引数、戻り値などがありますが、それだけではなくブロック、if、whileの値などもそうです。RubyTypeは次のようなインスタンス変数・クラス変数を持っています。 @name データの名前(変数名とかリテラルの値そのものとか)、デバッグ・エラーメッセージ用 @line_no データが定義されたファイル名・行番号、デバッグ・エラーメッセージ用 @type 型オブジェ
yarv2llvmがとりあえず1段落しました。今後しばらくは、大きな新機能は追加せず、こまごました機能追加とBug fixを行おうと思います。安定してきたら、多相メソッド起動を作りたいと思います。なんか思いついたら、新機能を入れるかもしれないですが。 yarv2llvmの内部構造のドキュメントが無いので、内部構造の説明を書いていこうと思います。今日はyarv2llvmの大まかな概要です。 yarv2llvmは、Ruby1.9のVM(かってYARVと呼ばれていました。以下、Ruby1.9のVMのことをYARVと(おそらく間違っていますが便利なので)呼びます)のバイトコードをllvmのbitコード列に変換するソフトウエアです。YARVとllvmはどちらも仮想計算機と呼ばれる種類のソフトウエアですが、大きな違いがあります。 YARV スタックベース 動的型付け 命令が高機能(ほぼRubyの1命令
InfoQの記事にコメントが入っていて、Ludicrous JIT Compiler なるものが紹介されていました http://rubystuff.org/ludicrous どうもかなり完成度が高そうです。 ソースがgithub(http://github.com/cout/ludicrous/tree/master)にあるので、見てみました。型推論はやってないだろうなー、と思ったらなんかやってるみたいだし、ひょっとしてyarv2llvmいらない? みたいな 追記 型推論かなと思ったところ、(lib/native_functions.rbのrb_typeメソッド) は型推論じゃなさそうです。
llvmrubyのサンプルで何か作りたいなと思い、正規表現コンパイラを作ろうと思い立ちました。 調べてみたらomoさんがllvmで正規表現コンパイラを作っていましたhttp://www.dodgson.org/omo/t/?date=20071215。これをllvmrubyに移植しようと思ったのですが、コードを読んでも全然わからない。 昔のオートマトンの講義(確か単位落としたような気がする)を思い出して自分で作ってみました。何か、就職できなくて自分で会社を作ったのび太のような気分です。 正規表現は必要最低限のものだけです * 0回以上の繰り返し . 任意の文字 \文字 エスケープ(文字列で表すので実際には\\と入力する必要があります。)llvmにコンパイルする版を作る前に、Rubyにgotoを入れたRuby66にコンパイルするようにしてみました。 例えば、 ".*cc\\*dd*a"は次の
キャッシュを無効化(正確には汚染を少なくする)と299秒となりました。何もしないのが309秒なので、10秒早くなりました。 それにしても、GCをキャッシュを効かないようにしてわざと遅くすると、全体的には速くなるとは・・・。GC奥が深すぎる。 追記 すでに同じようなことをやっていた人がいらっしゃいました。 http://d.hatena.ne.jp/hyoshiok/20061002 このページからリンクされていた次のページが大変役に立ちました。 追記の追記: リンクされているのではなく、ページ中で言及されていた__builtin_prefetchをぐぐった結果でした。 http://www.yoh.u-tokyo.com/pukiwiki/?x86%2F%BE%AE%BC%EA%C0%E8%BA%C7%C5%AC%B2%BD ソースをさらしておきます。 static inline stru
authorNariさんのスーパーマリオブラザース(http://d.hatena.ne.jp/authorNari/20080422/1208880928)すごいですね。Rubyを知っている人はソースをぜひ読んでみてください。美しい!シンプル!スーパーマリオってこんなにシンプルに記述できるんだ!って思いました。 さて、authorNariさんといえばGC。スーパーマリオブラザースはちょうどいいベンチマークになるんじゃないかなと思い、Replay機能をつけてみました。 使い方 1 main.rb中の$replayの代入文を $replay = :record にします 2 普通にプレーします。多分、反応が鈍くなってるんじゃないかと思います。 3 終わるときは必ずESCキーで終了してください。 4 main.rbのあるディレクトリにkey.logなるファイルが出来ています。これは、キー入力の
結局、Cygwinでjemallocを動かす努力はなんか気が乗らないので、jemallocを読んでみようということにしました。色々勉強になりそうです。最初のコメントを訳してみます。英語は苦手なんで誤訳が一杯あると思います。指摘してくださると幸いです。 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4 -*- */ /*- * Copyright (C) 2006-2008 Jason Evans <jasone@FreeBSD.org>. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following con
このページを最初にブックマークしてみませんか?
『miura1729の日記』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く