近年,多様化するソフトウェア需要に応えるため,開発効率の良いプログラミング言語が求められている.その中で,オブジェクト指向スクリプト言語Rubyが実用的で開発効率の良い言語として注目されている.しかし,従来のRuby処理系は抽象構文木を辿る単純な実装のため実行が遅いという問題点があった.そのため高い性能が必要となるソフトウェアの開発には用いることができなかった.

本研究はRubyを高速に実行する処理系の実現手法を研究し,プログラミング言語Rubyの可能性を広げることを目的とする.そして,世界中で利用されるような実用的なソフトウェアを開発することを目標とする.

高速なRuby処理系を実現するための課題として,まず従来のRuby処理系の抽象構文木を辿る単純な実行方式の改善がある.従来の方式は,実現は容易であるが性能に問題があることが知られている.動的型システムおよび強力なリフレクション機能に代表されるRubyの動的特性は,Rubyプログラミングに柔軟性を与えるが,静的解析による最適化が不可能となるため,Ruby処理系に適した実行時最適化技術の開拓が必要となる.さらなる高速化を目指すためには,近年とくに普及してきたマルチコア,マルチプロセッサを利用したメモリ共有型並列計算機による並列実行の実現が重要である.しかし,過去のプログラム資産を生かすためにはスレッドセーフでない機能の扱いが問題となる.

上記の課題に加え,実用的なRuby処理系を実現するため,互換性,保守性,移植性が開発全体での課題となった.実際的なプログラミングを行うためには過去の豊富なプログラム資産を活かさなければならない.そのため従来の処理系との互換性の維持が必須である.とくにRuby処理系を拡張するためのC拡張ライブラリと,C拡張ライブラリを記述するために必要となるRuby C APIの実現が課題となった.また,言語処理系は複雑なソフトウェアであるため,保守性の向上が重要である.そして,移植性の維持は多くの計算機環境で動作する実用的な処理系とするために重要である.

高速なRuby処理系を実現に関するこれらの課題を解決するために,本研究ではYARV: Yet Another RubyVMという仮想マシン方式によるRuby用言語処理系を新たに開発した.まず,Rubyプログラムを正しく表現できるYARV命令セットを設計し,RubyプログラムをYARV命令セットで構成されたYARV命令列へ変換するコンパイラを作成した.YARV命令列を実行するための仮想マシンYARVは仮想マシンアーキテクチャとして一般的なスタックマシンとした.例外処理は実行時にオーバヘッドが不要となる表引き法を採用したが,Ruby C APIの互換性確保のためC言語での大域ジャンプを用いる方式と併用して実現した.

さらに,開発した仮想マシンYARVに実行時最適化技術をRubyプログラムの意味を変更しないよう適用した.とくに,Rubyの動的特性を堅持しながら高速化を行うため,実行時最適化を中心としたRuby処理系に適用可能なさまざまな高速化手法を検討し,特化命令やインラインキャッシュを利用した高速化を行った.また,既知の仮想マシン高速化手法である命令の融合操作,静的スタックキャッシングをYARV命令列に適用した.

仮想マシンの逐次実行の性能評価を行うため,典型的なRubyプログラムを実行して,それぞれの最適化がどの程度性能向上に寄与しているかを調べた.総合的には,仮想マシンを利用しない場合にくらべてマイクロベンチマークで最大20倍,マクロベンチマークで平均1.5倍程度の性能向上を達成したことを確認した.これによって本研究で検討した最適化手法の有効性を示すことができた.

YARVの開発では,VM(仮想マシン)記述言語およびVM生成系を作成することで仮想マシンの開発を容易にし,ソフトウェアの保守性を高めた.作成したVM生成系はVM記述言語で記述されたVM記述からコンパイラやアセンブラ,評価器のプログラム片を自動的に生成する.また,命令の融合操作,静的スタックキャッシングといった機械的に適用可能な最適化に関して,VM生成系を用いて必要な命令を半自動生成することで仮想マシンの高速化を容易にした.この工夫により,本システムの方式検討を容易にし,実際に開発期間を大幅に短縮することができた.

メモリ共有型並列計算機上での並列実行による高速化を行うため,Rubyスレッド処理機構を計算機システムが提供するネイティブスレッドを利用して構成し,Rubyスレッドの並列実行をサポートした.対応したネイティブスレッド処理機構はPOSIX ThreadおよびWindowsスレッドの2種類である.Rubyスレッドとネイティブスレッドの対応は,移植性を重視し,1対1対応とする方式をとった.ネイティブスレッドを利用したRubyスレッド処理機構を実現するためには,とくにRubyスレッドに対する割り込みが問題となるが,ブロック解除関数を登録する方式を採用することで解決した.

Rubyスレッドの並列化にあたっては,スレッドセーフでない既存の拡張機能が問題となった.本研究では,このような膨大なプログラム資産をそのまま利用するためにスレッドセーフでない機能を呼び出すときにだけジャイアントロックを利用し,そのほかは細粒度ロックを利用して並列に動作するシステムを構築した.しかし,既存のスレッドセーフでない機能を順次スレッドセーフな処理に書き変えていくことで,段階的に並列度を向上することができるシステムとした.Rubyのようなオープンソースソフトウェアとして開発を進められている言語の性能や機能を継続的に発展させていくためには,この方法が適している.こうした上で,ジャイアントロックや細粒度ロック導入によるオーバヘッドを削減するためにデータ構造を最適化し,ロックを考慮したRubyスレッドスケジューリングを実現した.これを実際にマルチコアプロセッサを搭載したメモリ共有型並列計算機上で実行し評価した結果,逐次実行に比べて利用するプロセッサコア数に応じた実行時間の短縮を実現出来たことを確認した.

本研究で開発した仮想マシンYARVは公式Ruby処理系に取り込まれることが決定しており,オープンソースソフトウェアとして公開される予定である.本研究によって世界中で多くの人に利用されるソフトウェアを開発するという実用的な面での貢献も行うことができた.今後はより詳細な解析や実行時フィードバックを利用した高速化,Ruby向けの新しい並列化手法の検討が必要である.

計算機システムの需要の増大とともに,ソフトウェアに対する要求も大きくなり,迅速な開発が求められている.本研究は,近年急速に普及している記述力の高いプログラミング言語Rubyを高速実行する仮想マシンとその並列化について述べたものである.

1.仮想マシンYARVの構築 (第2章~第5章)

高速なRuby用仮想マシンの設計と評価について述べている.高速なRuby処理系開発に必要な課題を解決するために設計したのが,Ruby用仮想マシンYARV (Yet Another RubyVM) である.YARVの特徴は以下の4点である.

(1) 実行時にRubyプログラムをコンパイルしてYARV命令列へ変換・実行する.YARVの計算モデルはスタックマシンである.

(2) 例外処理は,例外が発生しない限り余計なオーバヘッドを生じない例外表方式と,従来型 (setjmp/longjmp) のハイブリッド方式とした.

(3) 静的解析を必要としない実行時高速化技術を用いた.また,C言語レベルで実現できる移植性の高い最適化を行い,環境によらず高速に実行できるようにした.

(4) スタックマシンモデルの仮想マシンのオーバヘッドへの対処法は以下の通り.

・命令ディスパッチ:ダイレクトスレッデッドコードの適用

・命令オペランドのフェッチ:上記と,頻出命令パターンから新規命令を生成するオペランド融合と命令融合の利用

・スタック操作:スタックトップを特別なレジスタに格納する静的スタックキャッシングの実装

・命令本体の実行:メソッド検索結果を命令列中にキャッシュするインラインメソッドキャッシュの採用と,メソッド本体の小さい整数演算などを置き換える特化命令の採用

仮想マシンの構築は,文字の置き換えだけで行う簡単なVM生成系を利用して行った.VM生成系はユーザの簡潔な記述から仮想マシン本体のプログラム片やコンパイラ,アセンブラ,逆アセンブラのプログラム片を自動的に生成する.また,融合命令,静的スタックキャッシングで利用する最適化用の命令を自動的に生成する.この仕組みを利用することで保守性が向上し,高速化の試みが容易になった.

YARVは,旧Ruby処理系と比べ,マイクロベンチマークで顕著な性能向上を得ている.特に,整数演算を多用するプログラムでは特化命令により,最大25倍の性能向上を得た.また,他のスクリプト言語の処理系と比較しても,YARVの性能が優れていることを確認した.それぞれの最適化の効果はベンチマークプログラムによって異なるが,多くのベンチマークにおいて,仮想マシン化のみで2倍程度の性能向上を得ることができている.

2.Rubyの並列化 (第6章~第7章)

Rubyの並列化について述べている.マルチコアプロセッサに代表される,コモディティ化した並列計算機上でプログラムを並列実行する高速化の需要は大きい.Rubyは言語レベルで並行実行のためのスレッド処理機構を有している.既存のRubyのマルチスレッドプログラムも並列実行によって性能向上が実現できる.

旧Ruby処理系では,Rubyスレッドを独自実装のユーザレベルスレッドを利用して実現していた.この方式は,移植性は高いが,Rubyスレッドを並列実行することができない.この問題を解決するために,OSなどが提供するネイティブスレッドを1対1で直接的に利用することとした.Rubyスレッドを並列実行するにあたり,仮想マシンがメモリ保護違反などを起こさないようにするには適切かつ軽量な排他制御が必要になる.YARVにおいて排他制御が必要になるのは以下の4点である.

(1) スレッド間で共有するデータ: データ管理表へのアクセスを排他制御した.

(2) オブジェクトの管理: 排他制御を激減するスレッドローカルなオブジェクト管理を行った.

(3) インラインキャッシュ: キャッシュを更新する際に毎回新しいキャッシュエントリを生成する.アクセス時に排他制御が必要ない点で有利.

(4) スレッドセーフでないネイティブメソッド: 膨大なプログラム資産と互換性を保ちつつ,徐々に細粒度排他制御をもつスレッドセーフな実装に移行するための過渡的手段として,既存のネイティブメソッドの実行時はVMに一つあるジャイアントロック (GL) を使う.ただし,GL競合を監視し,競合回数が閾値を越えると,利用するCPUを制限して性能低下を抑える.

Rubyスレッドの生成,合流に関しては,OS依存のオーバヘッドによる性能低下があったが,スレッド切り替えは旧Ruby処理系に比べ6~11倍高速になった.8プロセッサコア上での並列実行により,最大7.4倍の性能向上を得,台数効果が確認できた.ただし,台数効果が制限される例もある.また,GLの競合が頻発する場合も性能低下が発生したが,動的な利用CPU制限により,最悪値に比べて性能低下を1/3.4に抑えることができた.

本研究は,近年注目されているプログラミング言語Rubyの高速化に挑戦し,次期のRuby公式リリース (Ruby 1.9.1) に採用される高い性能と,信頼性・保守性を含めた高い品質を達成した.本研究によって開発されたRuby処理系がオープンソースソフトウェアとして公開された暁には,世界中のRubyプログラマに利用・参照されることとなる.すなわち,これまで実行が遅いためにRubyを利用することが出来なかったユーザに対し,速度の問題を緩和し,利用可能領域を広めるという研究の目的を達成することができた.特に,Rubyの並列化は,並列計算機がコモディティ化している現在,インパクトのある成果となった.

以上のように,本研究は実用的なプログラミング言語処理系に関して世界的に認められる高いレベルの貢献を果たした.すなわち,本研究は情報理工学に関する研究的意義とともに,情報理工学における創造的実践に関して高い価値が認められる.よって,本論文は博士(情報理工学)の学位請求論文として合格と認められる.