LoginSignup
109
49

More than 3 years have passed since last update.

言語実装Advent Calendar 2019Day 12
@sisshiki1969(monochrome)

Rustでつくる（つくれるかもしれない）Ruby

Last updated at Posted at 2019-12-11

この記事は言語実装Advent Calender 12日目の記事です。
言語処理系の作成に興味はあるが具体的なやり方がわからない、という人向けに記事を書いてみました。（というか書いてる本人からしてさほど分かっていない）
自分自身の備忘録的な意味もあるので、参考にした文献やサイトもなるべく載せていきます。
コードはこちらにあります。ビルド・実行にはRust及びそのツールチェーンがインストールされている必要があります。
https://github.com/sisshiki1969/ruruby

要約

RustでRubyの処理系を書いている。CRubyの最適化手法をパクッて実装することで高速化を図っている。楽しいのでみんなで処理系を書こう。
性能評価はこちら

自己紹介

初めまして、monochromeです。非エンジニア・非情報系学部卒ですが、趣味でプログラミングをしていて、特にプログラミング言語の理論と実装に興味を持っています。もともとGoogleエンジニア@rui314 さんのPodcastである turing complete fm のファンで、＠rui314さんが書いている（2019年12月時点で未完成）「低レイヤを知りたい人のためのCコンパイラ作成入門」 を読んでC言語でCコンパイラを書き、自分自身をコンパイルして実行できる状態になりました。
https://github.com/sisshiki1969/monocc

達成感も得られ、C言語の仕様もある程度理解できてすごく良い経験になったのですが、プリプロセッサやビルドシステムなどC言語の闇の部分も体験し、最近はRustを勉強しています。

あと、@uint256_tさんが作ったプログラミング言語処理系が好きな人の集まり というSlackチャンネルで時々情報交換や経過報告、雑談を行っています。ゆるふわなサークルっぽいネーミングですが、初心者からガチの言語開発者や大学教員、プログラミング言語オタ勢などバラエティに富んだ人々が集っています。興味のある方は是非ご参加ください。

[2019/12/14追記] 上記SlackにはこちらのTweetにあるリンクから参加できます。https://twitter.com/uint256_t/status/1147446052150099970

対象とする読者

プログラミング言語の実装に興味があるが、実際に書いたことはないという方々。

対象としない読者

プログラミング言語実装を普通に自分でできる、もしくはできた、もしくは言語処理系の理論と実装に異常に詳しい方々。

動機

もともとVM（仮想マシン）で動くインタプリタ言語の実装には興味を持っていて、謎の高校生@uint256_tさん1が作ったJavaScript処理系 rapidus のコードを読んでRustを勉強しました。

そうこうしているうちに自分でも何か処理系を作って色々実験してみたいなあ、という人間の三大欲求の一つであるプログラミング欲が自然に芽生え、せっかく勉強したRustでRuby処理系をつくることを思い立ちました。今までRubyで本格的なプログラミングをした経験はなく、自作言語を作るなどの選択肢もありましたが、

(1) Rubyは広く使われている言語の一つであり、文法や実行モデルについて豊富な解説記事がある。
(2) リファレンスとなる処理系があり、自作処理系が正しく動作しているか、パフォーマンスがどの程度かを簡単に検証できる。
(3) 処理系を作ると言語仕様にはある程度詳しくならざるを得ないので、この機会にいろいろとユニークな言語機能を持つRubyを勉強してみたいと思った。
(4) 10/6に開かれたRuby Hacking Challenge2という研究会に参加してみたところ、Ruby開発者の笹田さんや遠藤さんのお話が聞け、マニアックな参加者の方々とも話せて予想外に楽しかった。

というのがRubyを選んだ理由です。

実装の方針

現在のRubyの主力処理系であるCRubyの実装と互換なものを（一応）目標としています。なるべくシンプルに作ることを目指しますが、単に作ってみた、だけではなくて実行速度も追求したいので、自分でパフォーマンスの解析を行ないつつユースケースにかかわらず一定の効果が得られそうな最適化は適宜取り入れていく方針としました。

独自の技術でガンガン高速化を図っていく、という技術レベルではないので、まずはすでに知られている理論と技術を自分で実装してみる、そして結果を検証してみる、というのを当面の目的にしています。

ですから、下記の高速化のための手法は、すべて既存のもの（基本的にはCRubyで採用されているもの）であって私が考えついたものでは全くありません。

実装の状況

安直なネーミングですが、rurubyと命名しています。実装状況はGitHubのREADMEを見てください。

基本的なオブジェクト及びリテラルとして整数・浮動小数点数・文字列・配列・手続きオブジェクト（Proc）が使えます。文字列の中にRubyの式を埋め込む式展開もサポートしています。　ハッシュは未実装です。 [2020/1/6]追記 Hashもサポートしました。

試しにフィボナッチ関数を埋め込んだ式展開付き文字列リテラルを評価してみます。irbっぽい対話型実行環境を用意していて、こんな感じで実行できます。

irb:0> x = 20
=> 20
irb:0> f = "fibonacci"
=> "fibonacci"
irb:0> puts("#{f} #{def fibo(x); if x<3 then 1 else fibo(x-1)+fibo(x-2);end;end}(#{x}) = #{fibo(x)}")
fibonacci (20) = 6765
=> nil
irb:0>

Procオブジェクトは今のところラムダ記法(-> (x,y){x+y})のみサポートしています。 まだブロックは使えませんが、ほとんどのケースではProcオブジェクトで代用できると思います。 [2020/1/3]追記 ブロックをサポートしました。

irb:0> def inc
irb:2* a=100
irb:2* ->{a = a + 1; a}
irb:2* end
=> nil
irb:0> inc.call
=> 101
irb:0> inc.call
=> 101
irb:0> inc.call
=> 101
irb:0> p = inc()
=> Proc(Ref(0x7f978bc021f0))
irb:0> p.call
=> 101
irb:0> p.call
=> 102
irb:0> p.call
=> 103

オブジェクト指向機能としてはクラス定義・スーパークラスからの継承・インスタンスメソッド・クラスメソッド・インスタンス変数・initializer・attribute accessorを実装しています。
Moduleは未実装です。[2020/1/3]追記 Moduleをサポートしました。

class Complex_
  attr_accessor :r, :i
  def initialize(r,i)
    @r=r
    @i=i
  end
  def *(c)
    Complex_.new(@r*c.r - @i*c.i, @r*c.i + @i*c.r)
  end
  def +(c)
    Complex_.new(@r + c.r, @i + c.i)
  end
  def abs2
    @r*@r + @i*@i
  end
end

パーサ（構文解析器）

ここからは処理系の概略を説明します。パーサはRubyのプログラムコードを読んでAST（抽象構文木）に変換するパートです。構文ルールからパーサを自動生成するライブラリもありますが、rurubyでは手書きで書いています。Rubyの構文ルールは複雑で、トークン間の空白文字の有無が構文解析に影響したり3、識別子の末尾に?がつくメソッド名が許されていたりする4ので、結構つらいです（現在進行形）。

Rubyの文法ではローカル変数と引数を取らない＆引数の ( ) を省略したメソッド呼び出しが同じ見た目になりますが、「その地点でローカル変数として宣言（≒初期化）されていない識別子はメソッド名」というルールになっているので、パースの段階で区別して扱うようにしています。ただ、左辺に出てきた場合にはこれから宣言しようとしている新しいローカル変数なのか、メソッドなのかがその場では判定できず、いろいろと面倒です。パーサ作成者に優しい一部の言語では、なんと関数呼び出しには ( ) が必須になっているようです。素晴らしいですね。

パーサの実装にあたっては青木峰郎さんの「Rubyソースコード完全解説」が大変参考になりましたが、かなり古い本なので現行のRubyの実装には合致しない記述もあり、注意が必要です。CRubyのパーサのコードを読むのが一番正しいやり方ですが、読んでいるうちに頭痛がしてきたので私は途中で断念しました。知力と視力と集中力に自信がある方はトライしてみてください。

仮想マシン（VM）・コードジェネレータ

コードジェネレータはパーサが作ったASTからバイトコード命令列を生成します。バイトコードの命令体系はスタックマシン用のシンプルなもので、CRubyのそれに似ています（というか基本的にはパクっています）。Rubyでは概念上、整数同士の四則演算も全てオブジェクトに対するメソッド呼び出しですが、そのまま実装すると無茶苦茶に遅くなる5ので、専用命令を用意して数値同士の演算は特別扱いして高速に処理できるようにしています。

VMはひたすらループしてバイトコード命令を読み、実行します。「ループして命令を読み」の部分（命令フェッチ）は純粋にオーバーヘッドになるので、頻出する複数の命令の組み合わせを合体して一つの命令とし、命令数を極力減らす最適化手法があります。具体的には、x - 1みたいな整数リテラルとの演算はPUSH_FIXNUMとSUBという2つの命令に変換されますが、この2つを合併して「整数定数との減算命令」とする特化命令を実装しています6。

バイトコード命令の中で、メソッド呼び出しは特に時間がかかる処理です5。したがって高速化を図る上では非常に重要なポイントになります。何に時間がかかるかというと、レシーバの所属クラスの階層をたどってクラスの持つインスタンスメソッドのテーブルを引き、メソッドの実体を探していく処理に最も時間がかかります。そこで、１回呼び出したレシーバのクラスとメソッドの組を覚えておき、同じレシーバ・クラスのメソッドを呼びに行ったときには即座に前回実行されたメソッドを返すことで高速化が図れます（メソッドキャッシュ）。現在実装作業中ですが、かなりの効果があります。

上記のような基本的な最適化手法に関してはRubyのVM（開発当初YARVと呼ばれていたもの）の開発者の笹田さんの記事がまとまっていて読みやすいです。いずれも古い記事ですが、基本的な実装は現在でも大きくは変わっていないはずです。もちろん、現在のRubyでは更なる最適化が施されています。
YARVアーキテクチャ
るびま・YARV Maniacs
Ruby VM アドベントカレンダー

オブジェクトの内部表現・メモリ管理

オブジェクトは所属クラスの情報やインスタンス変数のテーブル等を持つ結構大きな構造体ですし、メソッドを抜けた後もアクセスされる可能性があるので、一般的にはヒープに格納する必要があります。しかし整数や浮動小数点数のような情報量の少ない「小さな」オブジェクトも同じように扱おうとするとその都度ヒープへのアロケーションが起こってしまい、時間を取られる上にメモリを圧迫することになります。また、コピーするたびに大きなコストがかかります。そこで、「小さな」オブジェクトとポインタを、扱いやすい64ビットデータの中に押し込めてしまう手法を採り、特定のビットをフラグとしてポインタと整数、浮動小数点数を区別できるようになっています。

具体的には前述のRuby Hacking ChallengeでCRubyで使われている内部表現形式についていろいろと教えていただき、例によってそのままパクりました。詳細はWEB+DB PRESS Vol.110で笹田さんが詳しく解説されています。WEB＋DB PRESSの連載記事はGCの構造や配列の実装と最適化など、毎回面白い話題をわかりやすく、かつ手抜きなく解説して下さっていますので、Rubyを使う使わないは別にして、処理系の話が好きな方には是非一読を勧めます。

また、当初の実装ではメソッドの実行コンテキスト7を常にヒープ上にアロケートしていました。Rubyのようにクロージャを作れる言語としてはその方がシンプルに作れるからです。ただ、この実装だとメソッド呼び出しのたびにアロケーションが発生するので遅くなります。そこで実行コンテキスト構造体をスタック上に置き、クロージャを作るときのみヒープにコピーするようにしたところ、メソッド呼び出しが100%高速化しました(CRubyも同じような実装になっているはずです)。スタックに不定長のデータを置いて管理するのは難しいので、ローカル変数の個数は固定として上限を超えた分はヒープに確保するようにしています。速くなるだけでなく、GCにも優しいですね。

GC(ガベージコレクション、ヒープ上の不要になったオブジェクトを回収する仕組み)はまだ実装していません。現在勉強中です。これもRustに既存のライブラリがありますが、せっかくなので自作したいと思っています。[2020/6/17]追記 GCを自作して実装しました。
素人が自分で作るとすごく遅そう[2020/6/17]訂正 遅かった。

性能評価

[2020/6/17]追記　最新のベンチマークはGitHubのWikiにあります。

基本的な実行速度の評価として、3つのベンチマークを使いました。

  • so_mandelbrot.rb
    マンデルブロ集合の計算スクリプト、これは浮動小数点数の演算をひたすら行うものです。ローカル変数のみ使用し、ユーザー定義オブジェクトやメソッドは使いません。VMの基本的な実行性能を評価します。

  • fib.rb
    フィボナッチ数列を計算するスクリプト、ひたすらメソッド呼び出しと整数演算を行います。メソッド呼び出しの性能評価が目的です。

  • app_mandelbrot.rb
    最後に、オブジェクト指向機能の実行性能（オブジェクトの生成、インスタンス変数へのアクセスやインスタンスメソッドの呼び出しなど）を評価するための、前述のマンデルブロ集合計算を複素数クラスを自前で定義してオブジェクト同士の演算として行うスクリプトです。

青いバーがCRuby、黄色いバーが我がrurubyです。真ん中の赤いバーは現在実装中のメソッドキャッシュを有効にしたバージョンです。

CRuby vs ruruby (数値が大きいほうが遅い) (2).png

測定環境：WSL2 on Windows 10Pro(64bit)
intel Core i7-8700K 3.70GHz RAM:16GB
ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-linux-gnu]
rustc 1.40.0-nightly (22bc9e1d9 2019-09-30)

……はい。遅いですね。単純な演算とローカル変数へのアクセス・ループだけであればCRubyと遜色ありませんが、もう少し複雑なことをやると一気に遅くなります。

では、一体どの命令でどの程度の実行時間を消費しているのか？という疑問ですが、rurubyでは命令毎に処理時間を測定する機能を実装していて、コンパイル時にフラグ--features perfを与えることで解析できます。ただ、１命令実行するたびに回数をカウントし、実行時間を測定するコードが走るので、真の実行時間を正確には反映していない可能性に注意が必要です。

ruruby$bash fibo_perf.sh
+ cargo run --release --features perf -- tests/fibo_perf.rb
    Finished release [optimized] target(s) in 0.47s
     Running `target/release/ruruby tests/fibo_perf.rb`
317811
Performance analysis for Inst:
------------------------------------------
Inst name         count    %time     nsec
                                    /inst
------------------------------------------
END               1028K    10.08       33
PUSH_FIXNUM       1028K     8.49       27
ADD                514K     4.54       29
GT                1028K     9.66       31
SUBI              1028K     8.89       29
GET_LOCAL         2571K    21.78       28
SEND_SELF         1028K    23.01       75
POP                   1     0.00      200
DEF_METHOD            1     0.00      300
JMP                514K     4.07       26
JMP_IF_FALSE      1028K     9.48       31
CODEGEN               1     0.00     6300
EXTERN                1     0.01    33100
------------------------------------------

一番左側の列からバイトコード命令、実行回数、総実行時間（％表示）、1命令実行あたりの時間(nsec)です。
一番下の段のCODEGENとEXTERNはそれぞれバイトコード生成、組み込み関数呼び出し（ここでは最後に結果を出力するputsメソッド）を示しています。

やはりメソッド呼び出し(SEND_SELF)、ローカル変数の取得(GET_LOCAL)に結構時間が取られていることが見て取れます。ただ、GET_LOCALのようにもともと実行時間が短い命令群はこれ以上の速度向上はまず見込めないので、やはりメソッド呼び出しを工夫しないと、という結論になります。

上の例はfiboのものですが、app_mandelbrotを解析してみると、メソッド呼び出しの他、インスタンス変数へのアクセスが遅いようです。メソッドキャッシュを効かせるとメソッド呼び出し（SEND命令）が約30%高速化されましたが、全実行時間への効果を見ると、fiboではそれなりの効果が得られた一方、インスタンス変数のアクセスも大量に発生するapp_mandelbrotでは今一つでした。

今後の課題

メソッドの呼び出しがまだかなり遅いので、CRubyの実装をチラチラみてパクりつつ高速化を図っていくのと、いずれバイトコードを機械語に変換してしまうJIT（実行時コンパイラ）に挑戦してみたいと思っています。
別プロジェクトでRustから動的にx86-64機械語を生成して実行するためのRustライブラリを開発しているので（現時点では64bit整数演算と条件分岐・関数呼び出し・スタック操作ぐらいしかできていませんが）、LLVM等の既存ライブラリに依存することなくJITができるよう頑張ります。

来年のAdvent Calenderでご報告できるとよいのですが。
ではまた来年。

  1. RustでCコンパイラやWebブラウザやJava VMや.NETの処理系を書いて、現在は受験勉強の片手間にLLVMのようなコンパイル基盤を作っている、怪しい高校生。 ↩

  2. Rubyの最新の話題についての講演もあり、かつすごいプログラマの方々と直接お話しできて、いろいろ教えてもらえるという大変素晴らしい研究会(参加無料)です。 ↩

  3. Rubyではメソッド呼び出しの際に引数の（）を省略できるが、これが結構つらい。a+1とa +1で、aがローカル変数として初期化（暗黙の宣言）されていると普通にa+1を評価して返すが、ローカル変数でない場合は前者はa()+1、後者はa(+1)として解釈される。 ↩

  4. aが既出のローカル変数でない場合、a?だとa?というメソッド名、a ?だと三項演算子と解釈される。 ↩

  5. メソッド呼び出しは　レシーバのクラスを確認する→クラスが持っているインスタンスメソッドのハッシュ表を引いてメソッドの実体を取り出す→メソッドが見つからなかったら親クラスをたどってメソッドを探す→引数やselfの準備など、メソッドを呼ぶ準備をする→メソッドへ制御を移す　ということをやるので大変時間がかかる。 ↩

  6. フェッチ１回分と、整数をスタックにプッシュしてからポップするコストを節約できる反面、プログラムが複雑になり、特定の状況でしか発生しない（見つけにくい）バグが入り込みやすい。一般的にメリットしかない最適化というのはなくて、特定の状況では逆に遅くなったり、プログラムが複雑になって保守が面倒になるトレードオフがある。 ↩

  7. メソッド実行に必要な情報をまとめた構造体。引数の個数やselfの値、ローカル変数の値、バイトコード命令列への参照、実行中の命令の位置などが格納されている。メソッドを呼ぶたびに生成される。 ↩

109
49
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
109
49