Rubyプログラムを高速に 実行するための処理系の開発 （東京農工大学 大学院） ささだ　こういち 2005 2/19 IPA 未踏ユース 成果報告会

発表概要 背景 目標 Ruby の特徴 設計と実装 最適化手法 現時点での性能評価 まとめ Smithsonian National Museum of Natural History

背景 オブジェクト指向スクリプト言語Ruby http://www.ruby-lang.org 使いやすいと評判 世界中で広く利用 Ruby-talk ML では一日に百通以上 最近 Ruby on Rails が人気 日本発（主開発者：まつもとゆきひろ（Matz）氏） 日本発で世界に通用する数少ないソフトウェア コミュニティ活動も活発 日本Rubyの会 Rubyist Magazine

背景: Rubyist Magazine 0005 (Feb. 2005) http://jp.rubyist.net/magazine/

背景: 現状の問題点 高速化の必要性 既存のRuby処理系は遅い Ruby の処理系は魔法（by Matz） 誤った常識の流布 たしかに遅いところも 誤った常識の流布 「Rubyって遅いんでしょ？　使えないよ」 あなたが思うほど遅くありません 高速化の必要性 Ruby の処理系は魔法（by Matz） 魔法みたいな処理系のソースコード ソースコード整理の必要性

背景: 今までの試み 他の言語はどうしているの？ いくつかのRubyバイトコード処理系→不十分 バイトコード（仮想マシン型）処理系が適当 Lisp, Java, .NET, Smalltalk 処理系など いくつかのRubyバイトコード処理系→不十分 まつもと氏 平成12年度未踏ソフトウェア創造事業 不完全（命令が不十分・コンパイラも無い） ByteCodeRuby (George Marrows氏) 現状のRuby処理系よりも遅い→ プロジェクト終了 その他、作りかけばかり（新しいプロジェクトは増える）

提案：Rubyプログラムを 高速に実行するための処理系の開発 VM命令セットの設計 コンパイラの設計・開発 仮想機械(RubyVM)の設計・開発 JIT (Just In Time), AOT (Ahead of Time) コンパイラ YARV: Yet Another Ruby VM として開発中（オープンソースソフトウェア）

世界一速いRuby処理系 目標設定 世界中の人に使ってもらえるように いずれは次期Rubyの公式実装 Rite に 基本性能で2倍、JITコンパイラでは5倍 AOTコンパイラでは10倍の性能向上を目指す 世界中の人に使ってもらえるように RubyVM としての十分な機能を実装 いずれは次期Rubyの公式実装 Rite に Ruby2.0 処理系 Rite　（現在 1.9.0 開発中） 本プロジェクトが成功すれば YARV を Rite として採用

Rubyの特徴 インタプリタ クラスベースのオブジェクト指向 ダイナミック 例外処理など大域ジャンプ可能 スレッドのサポート すべてがオブジェクト・実行時に再定義可能 Evil Eval プログラミングは楽に、冗長に 例外処理など大域ジャンプ可能 スレッドのサポート Cによる拡張ライブラリ開発が容易 どれだけ無駄を 省けるかが勝負

YARV 概要 単純なスタックマシン 拡張ライブラリとして実装 既存のRuby と連携して機能を利用 大部分，Ｃ言語で実装 今回新しく作り直さない ガーベージコレクタ Ruby Script パーサ Ruby C API が使える 大部分，Ｃ言語で実装

デモ

Ruby Interpreter YARV コンパイラ VM 生成系 VM AOT コンパイラ JIT コンパイラ YARVの全体像 拡張ライブラリとして利用 YARV Ruby API を利用 コンパイラ 作る VM 生成系 VM AOT コンパイラ JIT コンパイラ

コンパイラ AOT コンパイラ JIT コンパイラ C コンパイラ VM（実行） YARVの動作の流れ Ruby プログラム 機械語 拡張ライブラリ VM（実行）

Ruby プログラム 抽象構文木 a = b + c 今までなぜ遅かったのか？ 現在の Ruby は 構文木を直接実行 a = a = メソッド 呼び出し（＋） メソッド 呼び出し（＋） メソッド 呼び出し（＋） 現在の Ruby は 構文木を直接実行 b b b c c c

b+c a a = b + c b c c b b+c YARV YARV はなぜ速いのか？ Ruby プログラム YARV 命令列 getlocal b getlocal c send + setlocal a YARV スタックマシン

# Ruby program print(“Hello”) # YARV 命令列 putself putstring “Hello” スタック制御、フロー制御、メソッド定義、・・・ # Ruby program print(“Hello”) # YARV 命令列 putself putstring “Hello” send :print, 1 コンパイル

命令記述フォーマット 命令記述フォーマットを定義 各命令をこのフォーマットで記述 具体的な記述部分は C いくつか変数を宣言 VM 実装が非常に楽に いろいろと自動生成

命令記述によるVM生成 命令記述 約2000 行 約60命令分 C プログラム 逆アセンブラ ドキュメント VM 命令記述から生成されるもののまとめ 命令記述 約2000 行 約60命令分 AOT コンパイラ C プログラム 逆アセンブラ ドキュメント VM (22000行・約400命令) これから実装 アセンブラ コンパイラ （主に最適化器） ベリファイア

VM概要 5 つのレジスタ 3つのスタックフレーム PC: プログラムカウンタ SP: スタックポインタ LFP: ローカルフレームポインタ DFP: ダイナミックフレームポインタ CFP: コントロールフレームポインタ 3つのスタックフレーム メソッド・クラス・ブロックスコープを管理

VM概要 – 例外処理 例外処理用テーブルを利用 従来の処理系（before) YARV （after） begin … rescue end ここで毎回 setjmp begin … rescue end なにもしない 例外が起きたら スタック巻き戻し ＆例外テーブルチェック 例外が起きたら そこで longjmp

YARV での最適化（高速化） 一般論 冗長性の除去 計算強度の軽減 トレードオフ マシン（その他）に依存の最適化 一度やったことは二度しない（キャッシュなど） 計算強度の軽減 もっと簡単にやろう トレードオフ 頻繁に実行するものを速く その代わりあんまり実行しないものを遅く マシン（その他）に依存の最適化 マシンレジスタの利用，分岐予測の考慮，コンパイラの最適化の予測（確認）

YARVでの最適化 インラインキャッシュ 命令オペランドにデータを埋め込み，キャッシュ 定数アクセス メソッド検索 A::B::C は4命令必要（定数アクセスが３回も） 各定数アクセスも結構遅い メソッド検索 現在のRuby処理系は1つのハッシュでキャッシュ

定数アクセスの最適化 Ruby プログラム getinlinecache A::B::C putnil getconstant A getconstant B getconstant C setinlinecache コンパイル 最適化 putnil getconstant A getconstant B getconstant C 2回目以降の実行をスキップ

YARVでの最適化(cont.) スタックキャッシング スタックトップの2つをキャッシュ 5状態 命令数は5倍（各状態ごとに命令を用意） putself_xx_ax putself_ax_ab putself_bx_ba putself_ab_ba putself_ba_ab

b+c v1 b+c v2 regA v1 = v2 + v3 v2 v3 v3 regB スタック操作無し！ YARV スタックキャッシングはなぜ早いのか b+c v1 Reg A Ruby プログラム b+c v2 regA v1 = v2 + v3 v2 Reg B YARV命令列(SC) getlocal v2 getlocal v3 send + setlocal v1 YARV 命令列 v3 v3 regB getlocal_xx_ax v2 getlocal_xx_ab v3 send_ab_ax + setlocal_ax_xx v1 スタック操作無し！ YARV スタックマシン

YARVでの最適化(cont.) 命令融合 オペランド融合 融合するものを指定すれば，自動的に生成 プロファイラ 頻出する連続した命令列を1命令に putobject putobject → putobject_x2 オペランド融合 putobject true → puttrue 融合するものを指定すれば，自動的に生成 命令記述を解析すれば可能 コンパイラ（変換器）も自動生成 プロファイラ

YARVでの最適化(cont.) 特化命令 if（a と b は整数か？） if（整数の + メソッドは再定義されていないか？） 単純な命令を特殊化 a + b → opt_plus if（a と b は整数か？） if（整数の + メソッドは再定義されていないか？） return a+b; 通常のメソッド呼び出し a.+(b) を実行

最適化を含むコンパイラの仕事まとめ Ruby スクリプト Ruby パーサ 構文木 YARV 命令列 基本コンパイラ 特化命令最適化 スタックキャッシュ命令 に変換 オペランド融合最適化 命令融合最適化 その他最適化 YARV コンパイラ

JIT コンパイラ VM評価関数 の実体 （機械語） 機械語コード コピー 実行時に YARV 命令列を機械語に変換 コードを切り貼り（機械語を直に触りたくない） Intel i386で、いくつかの命令だけ対応 VM評価関数 の実体 （機械語） YARV 命令列 A B C JIT コンパイル 機械語コード A を処理するところ A を処理するところ コピー B を処理するところ B を処理するところ C を処理するところ C を処理するところ

JIT コンパイラ (cont.) VM評価関数 VM評価関数 の実体 1 の実体 2 比較 コピーするとき、相対ジャンプしている命令は書き換えなければならない VM 評価関数を同じものを2つ作り、機械語（オペランド)レベルで違いがあれば書き換え VM評価関数 の実体　1 VM評価関数 の実体　2 比較 A を処理するところ A を処理するところ

AOT コンパイラ 命令記述 C プログラム コピー Ruby プログラムを C プログラムに変換 命令記述を変換して貼りつけ（テキスト処理） ほぼすべての命令に対応 命令記述 YARV 命令列 A B C AOT コンパイル C プログラム A を処理する記述 A を処理する記述 コピー B を処理する記述 B を処理する記述 C を処理する記述 C を処理する記述

ベンチマーク結果 評価環境 (1) CPU: Intel Celeron 1.7GHz, Mem: 512MB OS: Windows2000 + Cygwin 1.52 (2) CPU: AMD 64 2.4GHz, Mem: 1024MB OS: Linux amd64 2.6.5-1.358 (Fedora Core 2) コンパイラ: gcc (GCC) 3.3.3 コンパイラオプション：-O2 -f-no-crossjumping 比較対象の ruby 1.9.0 (2005-02-17)

ベンチマーク結果(cont.) プログラム x86(Celeron) x86_64(AMD64) whileloop 7.66 11.17 times 1.88 1.89 const 16.80 17.89 method 5.96 5.93 poly_meth 3.39 3.37 block 5.00 4.50 Rescue 71.80 72.4 Rescue2 1.44

ベンチマーク結果(cont.) プログラム x86(Celeron) x86_64(AMD64) fib 10.90 7.90 tak 7.73 5.73 tarai 4.94 3.95 matrix 2.12 2.41 sieve 4.92 4.46 ackermann 11.18 13.00 count_words 1.12 1.03 pentomino 2.09 2.02

ベンチマーク結果(cont.) AOT コンパイラの効果 whileloop 81.2 6.0 (x 11.8) 0.8 (x 102.0) プログラム Ruby YARV YARV AOTed whileloop 81.2 6.0 (x 11.8) 0.8 (x 102.0) fib 9.6 1.2 (x 8.0) 0.9 (x 10.8) メソッド呼び出しが本質的に遅い （バックトレース用情報などが必要になるため） 高速化手法を検討中

ベンチマーク結果(cont.) JIT コンパイラ def m 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 end jitcompile(self, :m) i=0 while i<1000000 i+=1 m normal YARV: 0.454000 0.000000 0.454000 ( 0.443000) JITed YARV: 0.375000 0.000000 0.375000 ( 0.398000) #=> 21% 高速化

成果物一覧 YARV ソースコード 機能一覧 C ソースコード：17 ファイル 約 7500行 Ruby ソースコード：5 ファイル 約 1200行 機能一覧 ○：変数/制御構造・クラス/メソッド定義・メソッド呼び出し ○：多くの組み込み関数・組み込みクラス ○：高速化のためのさまざまな最適化 △：yield（ブロック呼び出し/2.0仕様）/ defined? ×：内部構造に関わる組み込み関数（Thread や send）

品質管理 Ruby の各構文要素毎にユニットテストを作成 ベンチマークプログラムの動作を確認 10 ファイル テスト数：103、アサーション数：282 ベンチマークプログラムの動作を確認 ベンチマークプログラム数：53 速くなるのを見てニヤニヤする

対外発表など（YARV の宣伝） 8月 LL weekend 8月 まつもとさん訪問 10月 Ruby Conference 2004（バージニア） 10月 関西オープンソース 2004 1月 プログラミングシンポジウム 2月 RHG 読書会 これから：3月 情報処理学会　全国大会 これから：3月 オープンソースカンファレンス これから：Rubyist Magazine vol. 6 （5月）～

7月 8月 9月 10月 11月 12月 1月 2月 見落とし発見 積み残し 命令設計 VM 設計 VM 実装 VM 基本部分最適化 開発スケジュール（過去） 7月　8月　9月　10月　11月　12月　1月　2月 見落とし発見 積み残し 命令設計 VM 設計 VM 設計 実装 VM 設計 実装 VM 実装 VM 基本部分最適化 AOT コンパイラ JIT コンパイラ 本業（研究会原稿）

YARV 開発について（現在） 0.1.1 released ホームページ メーリングリスト http://www.atdot.net/yarv/ インストール方法などもここに メーリングリスト Yarv-dev （日本語） Yarv-devel （英語）

Ruby 2.0 （Rite） リリース 開発スケジュール（未来） はやいうちに（来年度目標） できるだけはやいうちに 現在の処理系と YARV の統合 きちんとした JIT・AOT コンパイラ Ruby 以外の言語 on YARV → YARV 可能性検証 ほかいろいろ（アセンブラ、プリコンパイル、…） できるだけはやいうちに Ruby 2.0 （Rite） リリース 夢 YARV OS（with OSKit） 組み込み機器向け YARV

Ruby Interpreter 評価器 YARV コンパイラ VM JIT コンパイラ 現在の処理系と YARV の統合 拡張ライブラリとして利用 Ruby API を利用 VM 評価器 Ruby Interpreter

Ruby Interpreter - Ruby 2.0 (Rite) 現在の処理系と YARV の統合 YARV JIT コンパイラ コンパイラ VM Ruby Interpreter - Ruby 2.0 (Rite) 世代別 GC 多言語化 Selective Namespace … コンパイルされた 標準ライブラリ

現在はあまり速くなってない＆あまり対応できてない 開発成果のまとめ 各種最適化により順調に高速化　10倍の性能も 世界一速いRuby処理系 基本性能で2倍、JITコンパイラでは5倍 AOTコンパイラでは10倍の性能向上を目指す 世界中の人に使ってもらえるように RubyVM としての十分な機能を実装 現在はあまり速くなってない＆あまり対応できてない プリミティブはほぼ実装 大規模なプログラムはまだ デバッグデバッグ

反省点 よかった点 ～ よくできました 悪かった点 ～ もうすこし頑張りましょう いろいろと宣伝した 考えていた最適化をいちおう全部試せた→知見を得た 予想以上に高速化ができた→予想どおりに Ruby が遅かった 悪かった点 ～ もうすこし頑張りましょう 大規模アプリケーションの目標をきちんとたてなかった ロードマップを明確化するべきだった Ruby 2.0 の仕様にしたが、それだと動かないプログラムばっかり（現在の仕様に準拠すべきだった）

おわり / ご清聴ありがとうございました Special Thanks IPA Yarv-dev / Yarv-devel ML 参加者の皆様 NaCl　まつもとゆきひろさん 筑波大　前田敦司助教授 産総研　首藤一幸さん And others RHG 読書会参加者の皆様 Ruby Hackers

YARVでの最適化(cont.) インラインキャッシュ(cont.) Global “VM state counter” メソッド再定義 定数再定義 インラインキャッシュ時，このカウンタ値を一緒に格納 キャッシュ参照時，現在のカウンタ値と格納されたカウンタ値を比較 同じならキャッシュヒット 違ったらキャッシュミス

VM概要 – Ensure 例外処理用テーブルを利用 Ensure 節部分をコピー # sample begin A ensure B end Compiled: Start_A: A End_A: B End_B: end ExceptionTable: entry: type: ensure range: Start_A – End_A do: B restart point: End_B restart sp: 0

-f-no-crossjumping switch(cond){ case A: P1; P2; break; case B: 同じようなコードを共有しようとする → ジャンプ命令が増える → threaded code 効果半減 switch(cond){ case A: P1; P2; break; case B: P3; P2; break; } switch(cond){ case A: P1; L: P2; break; case B: P3; goto L; break; }

Rubyの特徴(cont.) # (1) in Ruby [1,2,3].each{|e| print e } クロージャ ブロック付きメソッド呼び出し メソッド呼び出し時，容易に closure を渡すことが可能 # (1) in Ruby [1,2,3].each{|e| print e } ;; (2) in scheme (for-each (lambda (e) (print e)) '(1 2 3))

ベンチマーク結果(cont.) i=0 while i<100000000 # 100M i+=1 end AOT Compiler の効果 i=0 while i<100000000 # 100M i+=1 end Ruby YARV SC YARV AOT 81.2 6.8 (x11.9) 0.7 (x116.0)

ベンチマーク結果（コンパイル時間） if false def m a = 1 b = 2 c = 3 end # 以下 15万行繰り返し ruby 1.546000 0.078000 1.624000 ( 1.648000) yarv 6.718000 0.156000 6.874000 ( 6.913000)

ベンチマーク結果（コンパイル時間） if false a = 1 b = 2 c = 3 ... 繰り返し 16万行 End ruby 1.281000 0.031000 1.312000 ( 1.318000) yarv 96.188000 0.094000 96.282000 ( 96.896000)

命令記述フォーマット(cont.) DEFINE_INSN putobject # 命令名 (VALUE obj) # オペランド () # スタックから取る (VALUE val) # スタックへ置く { val = obj; /* C 言語で実装を記述 */ }

VM概要 – Stack Frames Method Frame Control frame 他のVMとほぼ同様 クラスフレームもほぼ同様 各フレームが持つ レシーバ 命令列情報 継続情報（caller regs） CFP によりアクセス可 Stack … Args Locals Environment Block LFP, DFP CFP Control Self ISeq SP Cont.

VM概要 – Stack Frames (cont.) Block Frame ‘yield’ によって作成 LFP points to method local environment DFP points to current environment DFP[0] == PDFP point to previous environment Stack … … Args Locals … Args Locals LFP Args Locals Block PDFP Ctrl DFP PDFP Ctrl Ctrl CFP SP … …

VM概要 – Proc Object Proc オブジェクトの生成 要するにクロージャ LFP, DFP はヒープ上を指す 環境をヒープに保存 LFP, DFP はヒープ上を指す スタック上の値は遡って張り直す Stack … Proc Args Locals LFP Block Ctrl CFP Env. Env. SP # Proc sample def m arg; x = 0 iter{|a| i=1 iter{|b| j=2 Proc.new }}; end Struct ProcObject: VALUE self; VALUE *lfp; VALUE *dfp VALUE iseqobj; Env. DFP