Ruby に任意の形式のアーカイブなどからファイルを require 出来るようにしよう,という仕様をまとめるために,Python の似た様な仕様をサーベイ.
まとまらず,メモ書き.
finder と importer がいて,finder は importer を返す様な構成になっている.ただ,finder の定義がイマイチわからんのよな.finder.find_module の定義がわからん.path には何が来るんだこれ.
なるせさんと西山さんに教えてもらいながら,iPhone でアプリケーション開発をする方法を教えてもらった.といっても,開発者のライセンス(だっけ?)を買う金はないので,HTML5 で.
要望としては,
といったところ.(1),(2) は,アプリケーションキャッシュというものを使えば良いというのを教えてもらった.というか,HTML5 ってそんなことまで決めてるのか.
(3) については,web clip というものを教えてもらった.また,apple-mobile-web-app-capable というものを使えばいいということも教えてもらった.
で,作ったアプリというのが http://www.atdot.net/~ko1/nums/nums.html.いや,今英会話教室(英語発音)に行ってるんですが,ランダムな数字を5個出せ,とか言われて,いやそんなのさっとでないよ,と思って,作りたかったのです.
しかし,JavaScript でなんか書こうと思うと,毎回「あれ,文字の連結ってどうやんだっけ」みたいな感じでぐぐっている.どうしたもんかな.djs 使いたいぜ(でもサーバサイド使いたくないな).
ruby -> js のいい加減な変換器を書くか....しんどそうだよなぁ.
世界に 3 人くらいはいるかもしれない Ruby VM アーキテクチャに興味がある人のために YARV Maniacs 出張版.
■概要:finish フレームを無くしました.代わりに,フレームに「finish」フラグを付けるようにしました.
■目的
□これまでのあらすじ
メソッドを呼んだり,ブロックを実行したりすると,「制御フレーム」というものを積みます(rb_control_frame_t).メソッドの場合はメソッドフレーム,ブロックの場合はブロックフレームというように呼んでいます.フレームの種類は,フレームに埋め込まれている flag という領域に識別子を埋め込んでいます(正確には,rb_control_frame_tのflag メンバ変数の最初の 8 bit).具体的には,VM_FRAME_MAGIC_METHOD とか,なんとかです.magic とついているのは,マジックナンバーとか,そんなニュアンスです.
で,その1つに finish フレームというものがありました.メソッドでもブロックでmない,特殊なフレームです.これを説明するには,もうちょっと説明が必要になります.
(C)Ruby では,Ruby で定義できるメソッドはもちろんですが,C でメソッドを定義することもできます.例えば,String や Array のメソッドは,すべて C で実装されています.
その中で,C メソッドが,さらに Ruby メソッドや,Ruby で記述されたブロックを呼び出すことがあります.たとえば,Integer#times は,Ruby で記述されたブロックを呼び出します.例えば,3.times{|i| p i} という文は,3 回 Ruby で記述された {|i| p i} というブロックを呼び出す,という処理ですが,この処理を C で書いてあります.つまり,C -> Ruby という呼び出しです.もちろん,Ruby がさらに C を呼ぶこともあります.つまり,Ruby と C が重なり合ってる感じです.
Ruby で記述された部分を処理するときには,もちろん我らが VM を用いて動かすわけですが,この VM というのは命令列(バイトコード)をがある間,繰り返して命令を実行する関数として実行されていまして,この繰り返しをすることから,VM ループ 関数,と呼ぶことにしましょう(参考:YARV Maniacs 【第 2 回】 VM ってなんだろう).
Ruby メソッド(などの Ruby で記述されたコード)をさらに呼び出しても,同じ VM ループ関数で処理を続けるようにしています(*1).そして,VM ループ関数を呼び出したときに始めた Ruby の処理が終わる(たとえば,メソッドから抜ける)と,この VM ループ関数も終了します.
(*1) 別の設計としては,メソッド呼び出しが行われたら,必ず新しい VM ループ関数を呼び出す,という方法も考えられますが(Ruby 1.8 はそういう感じで実行していた),それだと,色々な面で遅いので,Ruby の処理が重なる間は VM ループ関数を新しく作らないようにしています.いろいろ理由はあるんですが,直感的にわかりやすい理由は「VM 関数の起動は遅い(ことが多い)」ということがあります.でかい C の関数なんで,初期化とか結構しんどいんです.例外処理しやすいとかもあります.
さて,ここで VM ループ関数の途中で C メソッドを呼び出すことを考えましょう.C メソッドは C の関数として実装されているわけで,VM ループ関数から C の関数を呼び出すことになります.ここでは Cfunc1 という関数を呼び出すことにしましょう.マシンスタック(C の関数呼び出し)は,大ざっぱに次のような感じになります.VM ループ関数(VM loop と表記)の下には,C の main() やらなにやら,色々ありますが,まぁそういうのは省略しています.
Cfunc1 VM loop ------------ <- machine stack bottom
さて,ここで Cfunc1 から Ruby のメソッドを呼び出すことを考えて見ましょう.Ruby の C API である,rb_funcall() を使うと,簡単にそれが実現できます.なんて クソ仕様 便利なんでしょう (*2).これを図にすると,下記のようになります.
VM loop Cfunc1 VM loop ------------ <- machine stack bottom
つまり,VM ループ関数がネストしていることがわかります.
(*2) なお,別のデザインとして,Cfunc1 からいったん抜けて,VM ループ関数に戻って Ruby の処理を続け,それが終わったら Cfunc1 の続きの処理を行う,という選択肢もあります(Gauche なんかはそうやってる).が,それを実現するためには,技術的な問題点があります.いくつか方法は考えられますが,(1) Fiber が用いているような継続の保存,復帰による方法や,(2) コンパイル時に前処理と後処理に分割する方法(CPS 変換),(3) ユーザが Cfunc1_before(),Cfunc2_after() のように前処理,後処理に分割する手法,などが考えられます.ただし,(1) はまともに動くかあまり自信がない(あと,明確に C の仕様を逸脱している),(2) はコンパイラをちゃんと書くのがしんどい,(3) はもちろん書くのがだるくなります.というわけで,VM ループ関数を呼び出すのは,性能を考えなければ筋がいい解なわけですが,俺は性能改善がしたいんだよ! さて,これをなんとかする方法の 1 つとして,以前研究でやってた Ricsin というのがあるんですが,あれをもうちょっと進めて,そして 2.0 に入れられるようにしたいなぁ....
さて,先ほど「VM ループ関数を呼び出したときに始めた Ruby の処理が終わる(たとえば,メソッドから抜ける)と,この VM ループ関数も終了」と書きました.「VM ループ関数を呼び出したときに始めた Ruby の処理」というのは,どうやって判定するといいでしょうか.
そこで,finish フレームの出番です.VM loop 関数の最初には,Ruby メソッドのフレームではなく,専用のフレーム finish フレームを積むようにしておきます.
Ruby: m4 Ruby: m3 finish VM loop Cfunc1 Ruby: m2 Ruby: m1 finish VM loop ------------ bottom
こんな感じ.このとき,Ruby メソッドである m4 を抜けても,そのまま VM ループ関数は実行を継続しますが,Ruby メソッド m3 を抜けると,その後 finish フレームが待ち受けており,finish フレームは finish 命令を実行するように設定されています.この finish 命令というのが VM ループ関数から抜ける,という処理を行うようになっており,そんな感じで実行されるわけです.
Ruby メソッドから抜けるときは,leave という命令が実行されます.この leave で VM ループ関数を抜けるかどうかをチェックする必要が無くなるので,ちょっと速くなりそうじゃないですか?
ちなみに,VM の制御フレームは 1 本しかない,という感じで説明をしてきましたが,これを linked list にしてやるって手もありますね.VM ループ関数が実行するごとに,新しい VM スタックを生成していく(スタックトレースを生成するためには,これらをつなげる,つまり linked list にしておく必要はあるわけです).そうすると,スタックの底に来たときに leave は VM ループ関数を抜ければいいというのがわかるわけです.が,それは結局スタックの底かどうかをチェックする必要があるわけで,あまり賢く無さそうですね.VM ループ関数を呼ぶごとに VM(制御フレーム)スタックを生成しなければならない,というのも減点です.
□振り返り
まぁ,そういうふうに考えて,1つの分岐を減らすために色々頑張ってたんですが, finish フレームを用いる方式には次の問題点があります.
これらの問題点は,圧倒的に実行回数の多い leave 命令をちょっと速くすることに比べていいかなぁ,と思ってたんですが,どうやら finish フレームを積む機会が予想以上に多いので,やっぱり効かないかなぁ,と思ってやめることにしました.
あと,分岐 1 個削ることができるのが利点なわけですが,最近のプロセッサだったら分岐一個くらいほとんどかわんねーかなぁ,というのが大きな理由だったりします.
というかね,leave ではデバッグ用(cfp の一貫性チェック)に無駄な分岐がそもそも 1 個あったりしたんだよね.いやはや.
■設計
というわけで,finish フレームをやめました.では,どうやって VM ループ関数から抜けるかどうかを判断するかというと,上述の rb_control_frame_t#flag に,1 bit,このフレームで VM ループ関数から抜けるよ,と leave 命令でチェックするようにしたのでした.
語彙としては,finish フレームという言葉は,この bit がたっている制御フレームのことを言うことにしました.
なお,あるフレーム(cfp で指されるフレーム)が finish フレームかどうかは,VM_FRAME_TYPE_FINISH_P(cfp) でチェックできるようにしました.
■評価
実際にベンチマークを走らせて評価をしてみました.
旧来に比べて,どれだけ速くなったか,ということを示しており,1 より大きければ速いです(直前の版の実行時間 / 修正後の版の実行時間).比率しか出していないので,数値を比較するときには実時間も注意しなければなりません(あまりに短いベンチマークだと,有意な数値ではない可能性がある,つまり誤差で比較している可能性があるため).
まぁ,1秒超えるようなベンチマークだったらいいんですけど,例えば vm1_const なんかは,有意に遅くなっている(ように思える)のです.ありゃらりゃ.ちなみに,loop_for が速くなってるのは,想定通り,って感じですね(イテレータからのブロック呼び出しが若干速くなっている).
で,この遅くなったベンチマークはなぜ遅くなったのか.結論から言うとよくわかりませんでした.というのも,このベンチマークって定数参照を繰り返すだけのものなのですが,今回の finish フレームとは一切関係ないんですよ.少なくとも,C の字面上は.
で,アセンブラレベルでトレースを取って(どんな命令が実行されたかをじっと眺めて),比べてみたりしたんですが,レジスタの使い方とか,コンパイル結果が若干変わったようでした.なんだよー,って感じですが,まぁよくあることではあります.VC だとまた違った結果が出てきたし.
この辺,見落としがあるかもしれないので,最後のチューニングはもう一度この辺を見直すことかもしれません.
■まとめ
というわけで,finish フレームを取り除きました.まぁ,性能が本当によくなったのか,評価で述べた通り微妙なんですが,まぁ1個余分な制御フレームを積むことがなくなった分,(VM の)スタックオーバーフローに,ちょっとだけなりづらくなったんじゃないかとおもいます.
途中でめだかボックスを読み始めてしまって,これを書くのに徹夜してしまった... orz
あらすじが長すぎである.
require の機能拡張の提案を計画しています.
書き殴り.ユーザ定義の形式で,ファイルをロードできるようにする仕様.オレオレ jar が作れる(かもしれない).
乱立すると,まずいから,こういうのは自由にさせないほうがいいのかなぁ?
# インターフェースは require だけ # mock def require_with_file feature, opt p [feature, opt[:feature_name]] end def require_with_string feature, opt p [feature, opt[:feature_name]] end module FeatureName def feature_names feature if /(\.rb|\.so)\z/ =~ feature yield feature else yield feature + '.rb' yield feature + '.so' end end end class FileLoader include FeatureName def require path, feature feature_names(feature){|name| filename = File.join(path, name) if File.exist?(filename) return require_with_file filename, feature_name: name end } false end end class GzFileLoader include FeatureName require 'zlib' def require path, feature feature_names(feature){|name| filename = File.join(path, name) gz_filename = filename + '.gz' if File.exist?(gz_filename) return require_with_string Zlib::GzipReader.open(gz_filename){|gz| gz.read}, feature_name: name end } false end end class EncryptedFileLoader include FeatureName def require path, feature feature_names(feature){|name| filename = File.join(path, name) br_filename = filename + '.br' if File.exist?(br_filename) return require_with_string File.read(br_filename).reverse, feature_name: name end } false end end class PStoreLoader include FeatureName require 'pstore' def require path, feature return false unless /\.pstore\z/ =~ path db = PStore.new(path) db.transaction{ feature_names(feature){|name| if script = db[name] return require_with_string script, feature_name: name end } } false end end class HttpLoader include FeatureName require 'open-uri' def require path, feature return false unless /https?\:\/\// =~ path feature_names(feature){|name| begin uri = URI.parse(path) script = open(uri + name).read # should make some verification return require_with_string script, feature_name: name rescue OpenURI::HTTPError # skip end } false end end $LOADERS = [PStoreLoader.new, EncryptedFileLoader.new, GzFileLoader.new, HttpLoader.new, FileLoader.new] def new_require feature $LOAD_PATH.each{|path| $LOADERS.each{|loader| return true if loader.require path, feature } } raise LoadError.new(feature) end $:.unshift 'lib/' $:.unshift 'lib/db.pstore' $:.push 'http://localhost/script/' new_require 'fileutils' new_require 'foo' new_require 'bar' new_require 'baz' new_require 'file_in_cloud'
世界に 3 人くらいはいるかもしれない Ruby VM アーキテクチャに興味がある人のために YARV Maniacs 出張版.
■概要:制御フレーム(control frame)ごとに積んでいた LFP, DFP というのをやめて,EP(Environment Pointer)というものだけにしました.
■1. 目的
これまで,メソッド呼び出しごとに LFP,DFP を積んでいたかというと,ダイナミックフレーム(block で積んだフレーム)から,直接ローカルフレーム(メソッド呼び出し時に作ったフレーム)で作った環境へアクセスしたかったからです.
環境にはローカル変数とかが詰まっています.ブロックのスコープだけで有効なローカル変数をブロックローカル変数といいます.
def m a = 1 1.times{ b = 2 1.times { c = 3 } } end
このとき,a は m のローカル変数,b, c はブロックローカル変数,ということになります.まぁ,ここではそう呼ぶと考えて下さい(b, c もローカル変数と言えるから).
で,a を参照するときは,ブロックの中でも lfp[index_of_a] で参照できます.c を参照するときは,c の制御フレームを指すポインタ cfp から cfp->dfp[index_of_c] と参照できます.c の制御フレームを指すポインタを持っているとき,環境は親環境への参照を cfp->dfp[0] に持っているので,cfp->dfp[0][index_of_b] とアクセスすればいいことになります.
実は,cfp->dfp を辿っていくと,cfp->lfp へいつかはたどり着くようになっています.なので,論理的には cfp->lfp は不要なんですが,実装の工夫として残しました(なお,ブロックみたいな構造を持っている処理系では,dfp みたいなものだけ,というのが普通です).
なぜ lfp を残したか,というと,Ruby 1.9 の仕様検討時には(大昔ですね),ブロックローカル変数をなしにしよう,という議論があったためです.つまり,どんなにブロックが深くなっても,変数はすべてローカル変数だけであり,どんなに深くても lfp の参照だけで変数参照ができる,素晴らしい! って話だったのです.あと,基本的にブロックだったり $_,$~ などの特殊変数群は,ローカル変数ごとに独立しているわけです(*1).
(*1) 余談ですが,なので次のコードは多分意図とは違うような結果になります.
class C define_method(:foo){ /(foo)/ =~ 'foo' } define_method(:bar){ /(bar)/ =~ 'bar' foo() p $1 } end C.new.bar
しかし,Ruby 1.9 の仕様は,むしろブロックローカル変数を増やす方向に動きました(ブロック引数とか).そのため,変数アクセスはブロックローカルなことも多くなりました(lfp から直接引くことも少なくなる).ブロック情報とか,$_,$~ などへのアクセスは依然効果はあるが,でも,そんなに回数があるわけじゃないよね.
デメリットとしては,制御フレームに毎回 lfp,dfp 積むことになるコストが挙げられる.ローカルフレーム積むときは,lfp == dfp の状態で積むし,あまり意味が無い.
というわけで,YARV の特徴の1つであった lfp と dfp をそれぞれ持つ構造を,ep 1本にするような,ふつーの処理系にするように変更しようというわけです.
というか,そもそも環境へのポインタだから,(local|dynamic) frame pointer って変だったんだよね.
■2. 設計
というわけで,lfp と dfp を 1 つにまとめた ep というフィールドを制御フレームに作ることにしました.
これまで,dfp としてアクセスしていたのは ep として全て作ることができます.ep[0] に前の環境へのポインタを格納しているところは変わらず.
ここで,lfp がさしていた環境へのポインタを LEP とします.Local environment pointer ですね.
LEP は,ep を親へ辿っていけばたどり着くわけです.ただし,どこまで辿ればいいか,という情報が抜けていました(これまで,n 回辿る,と外部から与えられていました.もしくは,lfp まで辿る,的な).そこで,LEP[0] にはこれまでブロックへのポインタを突っ込んでいましたが,ここに 1 ビット,0x02 を or で入れておくことにしました.これで,LEP かどうかを判断できます.
この辺のマジックナンバーは,すべてマクロで隠蔽してあります(VM_EP_LEP(ep),VM_EP_BLOCK_PTR_P(ep),等).
まぁ,そんな感じで,lfp, dfp を使っているところを全部置き換えたのが http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?revision=36030&view=revision になります.
■3. 評価
えーと,あんまりちゃんとやってませんが,もうちょっと細工したら(コミットはしていない),従来とあまり変わらなかったり,fib とかが 3% 速くなったり,といった感じになりました.やったね.
まぁ,これだけで劇的に速くなったら私の職は無いよな.
■4. まとめ
実は,これからまだまだ弄りますが,ちょっとずつ変えよう,という方針なので,ちょっとずつ,まずはわかりやすい lfp, dfp -> ep という作業をしたのでした.
個人的には,他のインタプリタと違う構造ってことで,愛着があったんですが,性能には勝てない.
次は finish frame を消しちゃおうかな.
adLint を試すため,まずは checkout.
Windows だと,なんかファイル名がぶつかるか何かで落とせなかった.
この状態でデモを動かそうとすると,なんかエラーがでる.
trunk/lib/ruby/2.0.0/rubygems/custom_require.rb:36:in `require': cannot load such file -- adlint/cpp/constexpr (LoadError)
あれー? とおもって見てみると,constexpr.y が.なんと Racc が要るらしい.
というわけで,http://i.loveruby.net/ja/projects/racc/ から checkout してビルド.
svn co http://i.loveruby.net/svn/public/racc/trunk racc cd racc ruby setup.rb
compiling cparse.c cparse.c:15:21: error: version.h: そのようなファイルやディレクトリはありません cparse.c: In function ‘get_stack_tail’: cparse.c:104: error: ‘struct RArray’ has no member named ‘len’ cparse.c:104: error: ‘struct RArray’ has no member named ‘len’ cparse.c:105: error: ‘struct RArray’ has no member named ‘ptr’ cparse.c:105: error: ‘struct RArray’ has no member named ‘len’ cparse.c: In function ‘initialize_params’: cparse.c:332: error: ‘struct RArray’ has no member named ‘len’ cparse.c:332: error: ‘struct RArray’ has no member named ‘len’ cparse.c:333: error: ‘struct RArray’ has no member named ‘len’ cparse.c:334: error: ‘struct RArray’ has no member named ‘ptr’ ...
えー....
Debian で racc コマンドを入れる(1.8用).
そして,rake.
$ rake cannot load such file -- cucumber/rake/task
えー....
Cucumber 関連を全部削除.やっと出来た?
intro_demo までやっとたどり着く.しかし,実行してみると,パスは固定というか,env ruby だった.GNUmakefile を見て,ruby と adlint のパスを変えて,adlint の shebang を変えて,やっと動いた....
構造体のメンバ名とローカル変数の名前が衝突していて警告というのは凄いな.
/share/sample/ruby-1.9.3-p0 というのがあるけれど,さてどう使うんだろう.
To actually run analyses, you need to... 1) download the target software 2) run "./configure && make" on Fedora 14
とあるけれど....Debian だしなぁ.それはともかく,ディレクトリ構造がどうなるべきか,とかよくわからない.
全体的にバランスが悪いですね
Gaucheでも、どうしてもCからSchemeへ(トランポリンを使わずに)再入したい場合は似たような機構を使ってる(boundary frameと呼んでるけど)。確かに制御フレーム一個積む分スタックと時間を消費するんだな。同じ手が使えるかと思ったが通常の制御フレームにフラグを押し込める場所が無いかも…
Ruby の VM の場合,制御フレームが 10 word くらいになってしまい,えらい時間がかかっていました.1, 2 word 書き込み程度なら,問題無かったんじゃないかと思っています.
えーと、「VMループ関数から抜ける」というVM命令を作って、戻ってきたらその命令を実行するようなフレームを積んでおけば、特殊なフレームとかチェックとか要らなくなりませんか?
前田さん:それをやっていたのが finish 命令,finish フレームで,これはそれをやめた,という話です.
おっと、失礼しました。