2008-01-01から1年間の記事一覧
追記 2008/12/31http://lambda-the-ultimate.org/node/2259 PICについて面白そうな議論がありました。IOはメソッドルックアップにCuckoo hashingを使っているが、継承木を辿るため継承木のオブジェクト数に対して線形時間かかるようです。yarv2llvmでは継承…
yarv2llvmにメソッドの外もコンパイルして実行できるようにしました。この結果、 ruby19 yarv2llvm.rb hogehoge.rbなんて感じで、hogehoge.rbをコンパイルして実行できます。これで、あたかもruby yarv2llvm.rbという名前のrubyの処理系があるかのように使え…
nbodyを速くしたいなと思い、ブロックをインライン化できるようにしてみました。 yarv2llvmではブロックは別関数にコンパイルし、yieldのタイミングで、呼び出しもとのローカル変数のフレームへのポインタを引数に渡して関数呼び出しをするようにしています…
llvmrubyで大域変数を実現するパッチをTom Bagbyさんにpullリクエストしたら、これまで書いたパッチを全部取り込んでくれました。すごくありがたいです。でも、問題出ないかちょっと心配です。それどころか、yarv2llvmをfolkしてくれました。64bitでは動かな…
とりあえず、こんな感じでProfilerを作ってみました。掛かったクロック数を行毎に表示します。ソースコード兼出力結果です。yarv2llvmで実行するのはただのfibなので、そこだけクロック数が表示されています。後は、Profilerそのもののプログラムです。 以下…
Profilerを作っています。Quantifyみたいなのがいいなって考えています(http://bmrc.berkeley.edu/purify/docs/html/installing_and_gettingstarted/4-quantify.html)。Quantifyのすごいのはサンプリングではなく、プログラム中に計測コードを埋め込んでクロ…
ふと、MagLevとyarv2llvmはどっちが速いんだろう?って思い調べてみました。http://antoniocangiano.com/tag/maglev/に、MagLevのbinary_treesの実行速度がRuby 1.8.6の結果とともに載っているのでこれと比べればいいやと考えました。 結果は、MagLevはRuby1…
trace_funcの実装がうまく行ったので、調子に乗って変数のアクセス時にもフックができるようにしようと考えています。 例えば、こんな感じになります。 module YARV2LLVM # ローカル変数とダイナミック変数の書き込み時に呼ばれる def local_var_write_func(…
yarv2llvmをスピードアップするにはprofilerがいるなーと思い、set_trace_func相当のものを作りました。set_trace_funcのそのままだとtrace_funcが設定されているかどうかを静的にチェックするのが面倒そうなので、YARV2LLVM#trace_funcというメソッドがあれ…
昔、学生のとき(15年くらい前)コンパイラを作っていたのですが、コンパイラがちっとも速くならなくて悩んでいたら、 「コンパイラはできることを全部やらないと速くならないよ」 ってアドバイスをもらったことを今日思い出しました。そのときは結局サボった…
yarv2llvmでnbodyが動きました。まだ、attr_accessorとかサポートしていないので、プログラムに手を加えています。 sample/bm_so_nbody.rbがソースです。(http://github.com/miura1729/yarv2llvm/tree/master/sample/bm_so_nbody.rb)実行速度を測ってみまし…
yarv2llvmでちょっとまとまったプログラムを動かしてみようと思い、bm_so_nbody.rb(http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/benchmark/bm_so_nbody.rb?revision=13548&view=markup)を動かそうとしています。 まだ、Rangeオブジェクトをサポート…
クラスのアドレスから配列のインデックスを求めるメソッドを生成するプログラムを作ってみました。 こんな感じのメソッドを作ることができます。 def klass2idx(klass) add = ((klass.__id__ >> 1) << 2) add = add - 268622760 functab = [:io, :array, :fi…
yarv2llvmではポリモフィズムはやらないとずーっといっているわけですが、Inline cachingはやらなくても効率よくduck typingが出来るような気がしてきたのでブランチを切って試してみようかなと思っています。 まだ、曖昧でただの興味本位なんですがこんな方…
shinhさんの「木ぽいののループ検出」(http://shinh.skr.jp/m/?date=20081202#p01)の木の構造をgraphvizで表示させてみました。(gen-tree 2)の場合です。2の場合でこんなに複雑だと、木そのものが指数関数的に増えているような気がします。共有されていると…
shiroさんのページより http://practical-scheme.net/wiliki/wiliki.cgi?Shiro 最後の "Best solution" にあげられてる「うさぎと亀」はあらゆるLisp/Scheme処理系で使われていると思う。list?は循環リストについても停止しないとならないため。 (CLのlistp…
タイトルは大嘘でベンチマークの為に、トップレベルで定義されたメソッドはselfを渡さないようにしました。これでちょっとベンチマークが速くなります。まあ、ベンチマークだけじゃなくてクラスを使わないプログラムだと恩恵があるのではないかなと思います…
Ruby Insideに取り上げられました!(http://www.rubyinside.com/llvmruby-a-compiler-toolkit-available-to-rubyists-1362.html) フィボナッチ級数のベンチマーク(http://d.hatena.ne.jp/miura1729/20081012/1223785541)がリンクされていてすごい勢いでアク…
すっかりChangeLogと化しています 本日はこんなことをしました。 バグの修正 def tgc i = 320000 b = [1] while i > 0 a = [1, 2, 3, 4, 5, 7, 8] c = [1, 2, 3, 4] i = i - 1 end b end こんなプログラムで、GCをいじめたら落ちてしまいました。GC周りかな…
基本ブロック内の変数畳み込みなどを実装しました。 def array3 a = [1, 2, 3, 4, 5] i = 0 i = i + 0 a[i] = 2 p i a[i] + a[1] + a[2] end がこんな感じに生成されます。pメソッドのの呼び出しのところでRubyでは変数iですが、0であることが静的に判る(本…
yarv2llvmはデータマイニングやグラフィックスなど速度が必要なプログラムで、Hot spotになっているところを高速化するという感じで使うことを考えています。このような場合、行列計算など配列の操作が多いのではないかなと思います。 これまで配列の参照(op…
yarv2llvmはコンパイルするプログラムを文字列で与えています。これは、Rubyでバイトコード列を得るAPIがRubyVM::InstructionSequence.compileとcompile_fileしかなくどちらもRubyのプログラムを文字列で与えるためです。コンパイルするプログラムを文字列で…
yarv2llvmのサンプルを追加しました。自然対数の底を約1000桁求めるというものです。 作っていて色々バグが出たので直しました。引数を渡す順番が違っていて、2つ以上引数を渡すとうまく動かなかったのには我ながら呆れました。 require 'yarv2llvm' YARV2LL…
LLVMって色々なアーキテクチャで動くからネットワークにLLVMのビットコードを流すようにして、プログラムの状態をfirst classで扱うような機能が付けばyarv2llvmでプロセスのマイグレーションができそう。といっても、ここにはLLVMが動きそうなパソコンは1台…
色々調べてllcに-enable-correct-eh-supportなるオプションがあることがわかった。とりあえず、invoke/unwindを使ったbit codeをファイルに落としてllcでX86の機械語に変換してみました。 こんなコードです。 ; ModuleID = 'foo.bc' define i32 @test2() { b…
昨日の日記のアサーションエラーが解決しました。原因はllvmrubyそのものでもLLVMでも無く、使い方の問題でした。 b.invoke(f2, nd, ud) b.return(1.llvm) # ここがだめ と、invoke命令の後にreturnをつけていたのですが、これがいけなかったようです。invok…
llvmrubyはinvoke/unwind命令の生成がまだサポートされていないので、それらの命令のサポートを作っています。作るのはそれほど難しくないのですが、変なアサーションが出ます。 assertion "use_empty() && "Uses remain when a value is destroyed!"" faile…
mandel.rbを動かすためには例外処理を実装する必要があることがわかりました。ブロックの中でbreakを使っていて、これを実行するためには2レベルの関数呼び出し(Range#eachがはさまれる)をreturnする必要があるからです。LLVMの仕様をみてみるといくつか例外…
今回は関数を定義してみたいと思います。llvmrubyで生成したllvmのコードをRubyから実行するには、関数を定義しないといけません。ちょうど、C言語でmain関数を定義しないといけないことと似ています。ただし、llvmrubyでは関数の名前は正しい関数の名前であ…
その2で重要なことを書き忘れていました。LLVM::Module.new('hello')の戻り値のLLVM::Moduleクラスのインスタンスは重要です。llvmrubyで何かを行う場合はたいていこの戻り値に対してメソッドを呼び出す形になります。続いて、実際に実行する命令を定義して…