\newif\ifNTT\NTTfalse \ifx\gtfam\undefined\ifx\gtfamily\undefined\NTTtrue\fi\fi \ifNTT\documentstyle[12pt]{j-article} \else\documentstyle[12pt]{jarticle}\fi \setcounter{secnumdepth}{6} \setcounter{tocdepth}{6} \topsep=0.1cm \parsep=0.1cm \itemsep=0.0cm %\renewcommand{\bf}{\protect\pbf\protect\pdg} \begin{document} \title{ 平成１２年度未踏ソフトウェア創造事業~\\ ~\\ オブジェクト指向スクリプト言語Ruby~\\ 次期バージョンの開発~\\ ~\\ 成果報告書~\\ ~\\ ~\\ } \author{ 松本 行弘~\\ ゼータビッツ(株)\\ } \date{ 平成13年2月28日} \maketitle \medskip \thispagestyle{empty} %\input epsf \newpage \makeatletter \renewcommand*{\l@section}[2]{% \ifnum \c@tocdepth >\z@ \addpenalty\@secpenalty \addvspace{1.0em \@plus\p@}% \setlength\@tempdima{1.5em}% \begingroup \parindent \z@ \rightskip \@pnumwidth \parfillskip -\@pnumwidth \leavevmode \bfseries \advance\leftskip\@tempdima \hskip -\leftskip #1\nobreak\hfil \nobreak\hb@xt@\@pnumwidth{\hss #2}\par \endgroup \fi} \@addtoreset{figure}{section} \renewcommand{\thefigure}{\thesection.\@arabic\c@figure} \@addtoreset{table}{section} \renewcommand{\thetable}{\thesection.\@arabic\c@table} \makeatother \pagestyle{empty} \tableofcontents \setcounter{page}{0} \newpage \pagestyle{plain} \medskip \newpage \section{概要} \label{概要} \medskip \par 本プロジェクトは松本行弘によって開発され、国内外で高い評価を 受けているオブジェクト指向スクリプト言語Rubyの次期バージョンを 開発するにあたり、主に以下の点における改善を行うものである。 \medskip { \renewcommand{\theenumi}{(\arabic{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item インタプリタ実装の改善 \medskip \par 現在のRubyインタプリタは単純な構文木インタプリタをベースにし て作り上げたもので、以下の欠点がある。 \medskip \begin{itemize} \item 処理系がつぎはぎで見通しが悪く、保守性に欠ける \item 構文木のトラバース処理などが負荷となり性能が低い \medskip \end{itemize} \par 本開発ではインタプリタ部分を新規に開発し、保守性、性能ともに 向上させる。 \medskip \item ガーベージコレクタ実装の改善 \medskip \par 現在のRubyインタプリタは古典的なコンサバティブ・マークア ンドスイープ方式のガーベージコレクタ(以下GC)を採用してい るが、状況によっては実行時効率に悪影響を与えていることが 観測されている。 \medskip \par 本開発ではGCのコンサバティブ性を維持しつつ、世代別GCのよ うな、より進んだガーベージコレクション技法を採用する。 \medskip \item 多言語対応(Multilingalization,M17) \medskip \par 現在のRubyでは、日本で広く用いられているASCII、EUC、SJIS、 UTF-8の各エンコーディングを処理することができる。しかし、世 界的に見れば、この４種類のほかにも数多くのエンコーディングが 存在しており、国際化プログラミング機能としては不足していると 考えられる。本開発では、新エンコーディング対応をユーザ定義で きるような枠組みを定義し、APIを開放することによって、他言語 にみられるようなUnicode対応による多言語対応を超えて、積極的 に多言語を処理できる機能を実現する。 \medskip \end{enumerate} } \newpage \section{目的及び背景} \label{目的及び背景} \medskip \par オブジェクト指向スクリプト言語Rubyは、松本行弘によって1993年 より開発されており、1995年の一般公開以来、国内外で広く使われ ている。 Rubyはすべてのデータがオブジェクトであること、そし て充実したクラスライブラリが特長となっている。 \medskip \par Rubyと同様の分野を対象とするスクリプト言語には、他にもPerlや Pythonがあるが、それらと比較するとRubyはPerlよりもプログラム が読みやすく、Pythonよりもプログラムが簡潔になる傾向がある。 また、Rubyは日本製であるため、PerlやPythonよりも日本語表記に 用いられるEUCやSJISなどの多バイト文字列をよく取り扱える。処 理系の性能の面から言えば、実行速度は多くの場合Perlよりは数割 程度劣るが、Python よりは高速である傾向がある。 \medskip \par このように他言語に対して一定の競争力をもつRubyではあるが、今 後の改善の余地は残されている。 \medskip \par その第一は性能である。インタプリタ型言語であるRubyはもともと それほど性能は高くなく、従来はそれを求められてもいなかったが、 スクリプト言語の適用範囲が広まるにつれ、処理系の実行性能に対 する要求は高まりつつある。 \medskip \par 次に、多バイト文字列の扱いに対しての要求もある。現状のRubyは EUC、SJIS、UTF-8という主に日本で扱われるコードセットを扱える に過ぎない。真の意味の国際化という観点から考えるとこれでは不 足である。 \medskip \par しかし、過去の多言語化システムの経験から考えると、Unicode対 応で問題が解決するとは思えない。少なくとも近い将来では解決し ない。既存の多バイト文字列データを活用し、柔軟な枠組みが必要 とされている。 \medskip \par 本開発では、これらの問題を解決を目指し、スクリプト言語のベス トソリューションとして世界的に認知されることを目標とする。 \medskip \newpage \section{全体構成} \label{全体構成} \medskip \par 本開発は以下の部分からなる。 \medskip { \renewcommand{\theenumi}{(\arabic{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item インタプリタ実装の改善 \item GC実装の改善 \item 多言語対応 \medskip \end{enumerate} } \par このうち、「インタプリタ実装の改善」および「GC 実装の改善」 は主にRubyのインタプリタ性能の向上を目的とし、「多言語対応」 は国際化のベースとなる複数言語のためのエンコーディングを扱う 枠組みを提供することを目的とする。 \medskip \subsection{インタプリタ実装の改善} \label{インタプリタ実装の改善} \medskip \par 現在のRubyインタプリタは単純な構文木インタプリタを改造して作 り上げたものである。インタプリタに与えられたプログラムは、ま ず構文解釈部でノードがリンクして構成される構文木に変換される。 文法エラーなどはこの構文木への変換の時点で検出される。 \medskip \par インタプリタのコアはこの構文木をたどりながら解釈実行を行う。 現在の実装では、構文木の枝の解釈は、解釈関数を再帰的に呼び出 すことで実現されている。 \medskip \par この実装は素朴であるが、以下の欠点がある。 \medskip \begin{itemize} \item 処理系がつぎはぎで見通しが悪く、保守性に欠ける \item 構文木のトラバース処理などが負荷となり性能が低い \item 再帰とallocaを多用しているためスタック消費量が大きい \item C言語での再帰のため、末尾再帰などが実現しにくい \item 構文木(ノード)の個数が多いためメモリ消費量が大きい \medskip \end{itemize} \par そこで、この構文木インタプリタを一種の仮想マシンに置き換える ことを考える。このことにより、以下のような改善が期待できる。 \medskip \begin{itemize} \item 再設計による見通しの良さ \medskip \par 現在のインタプリタはRubyの文法と仕様の拡大につれ、つぎは ぎ的に拡張されてきたが、文法や仕様がほぼ安定した現在、再 設計することにより無駄をなくした見通しの良い実装が期待で きる。 \medskip \item スタック消費量の低減 \medskip \par 仮想マシンの実装には再帰を使わないことと、仮想マシン自身 のスタックはヒープにとることになると思われることから、ス タック消費量は画期的に低減することが期待できる。 \medskip \item 命令フェッチコストの低減 \medskip \par プロファイルの結果から現在の実装では、次の命令をフェッチ するためポインタをたぐって構文木をトラバースするコストが 無視できないことが観測されている。仮想マシンを導入するこ とで、命令のフェッチのコストの低減が期待できる。 \medskip \item 実行時のメモリ消費量の低減 \medskip \par ヒープ上に割り当てた構造体のリンクである構文木よりも、仮 想マシンコードの法がメモリ消費量が小さいことが期待できる。 \medskip \item さらなる最適化の可能性 \medskip \par 変形の難しい構文木よりも仮想マシンコードの方が最適化の余 地が大きいことが期待できる。 \medskip \end{itemize} \par このような予想されるメリットが大きいので、インタプリタのコア として仮想マシンの導入を考える。ただし、現在のRubyの仕様は相 当複雑であり、今回の開発の期間ではとうてい全体を完成させるこ とはできない。そこで、今回はコアの仮想マシンのごく一部を実装 し、これらの期待が本当かどうかを検証する。 \medskip \subsection{GC実装の改善} \label{GC実装の改善} \medskip \par 現在のRubyインタプリタはコンサバティブなマークアンドスイープ 方式のGCを採用している。このGCは、他スクリプト言語で多く採用 されているリファレンスカウント方式と比較すると以下の利点があ る。 \medskip \begin{itemize} \item マークアンドスイープ方式ではC言語によるメソッドの実装で オブジェクト参照数を維持する必要がなく、リファレンスカウ ント方式でしばしば発生する参照数の更新忘れに由来するメモ リリークが発生しない。 \medskip \item マークアンドスイープ方式ではリファレンスカウント方式によっ て回収できない、オブジェクトが直接、間接に自分自身を参照 することによって発生するサイクル構造に対しても、問題が発 生しない。 \medskip \end{itemize} \par 一方、マークアンドスイープ方式にはデメリットもある。 \medskip \begin{itemize} \item マークアンドスイープ方式では、処理を一時中断し、オブジェ クト群をスキャンすることで、すでにどこからも参照されてい ないオブジェクトを発見する必要がある。このスキャンによる 処理時間が現時点で使われているオブジェクト数と最後のスキャ ン処理以降に生成されたオブジェクト数の合計に比例するため、 大量にオブジェクトが生成される局面では、実行効率に問題が ある。 \medskip \end{itemize} \par このデメリットにより、マークアンドスイープ方式を採用している Rubyのような言語はリファレンスカウント方式を採用しているPerl やPythonのような言語と比較して、大量のオブジェクトを生成する タイプのプログラムの実行性能が低い傾向があることが知られてい る。 \medskip \par 本開発では、この点を改善するために世代別方式のGC を実装する。 \medskip \par オブジェクトの振舞いを観測すると、生成されたオブジェクトのほ とんどは比較的寿命が短く、割合の少ない長寿命のオブジェクトは、 ほとんどプログラム全体にわたって生存するという性質が一般的で ある。世代別方式とは、この性質を利用して、生成されて間もない 「若い」オブジェクトを重点的にスキャンする方式である。 \medskip \par 本開発では、世代別GCの開発にあたって、現状のマークアンドスイー プ方式の良い性質を維持しつつ、特定の局面での実行効率を向上さ せることを目指す。 \medskip \newpage \subsection{多言語対応} \label{多言語対応} \medskip \par 現在のRubyではユーザが明示的に指定することにより、ASCII、EUC、 SJIS、UTF-8の各エンコーディングを処理することができる。しか し、現段階では一般的な日本語処理に十分であるというレベルであ り、国際化プログラミング機能としては不足していると考えられる。 \medskip \par PerlやPythonでは、多言語化の問題に対して、文字集合の和を目指 すUnicodeを利用して対応しようとしている。しかし、Unicodeの範 囲内で表現できない数万から数十万文字を含むGTコードや文字鏡の ような大文字集合の存在を考えると、PerlやPythonで行われている ようなUnicodeを採用することによる国際化対応には限界があると 思わざるをえない。 \medskip \par また、日本では多バイト文字データの扱いの歴史、特に複数文字集 合の並立の歴史が長く、Unicodeと各エンコーディングの間の変換 規則が一意に定まらないケース(yen sign problemなど)も問題とな る。そして、既に存在する大量のUnicode以外のデータ処理を考え るときに、その変換に伴う処理速度の低下も決して無視できない。 \medskip \par 本開発では、他言語にみられるような単なるUnicode対応に過ぎな い多言語対応を超えて、積極的に多言語を処理できる機能を実現す る。具体的にはマルチバイト文字列のエンコーディングをユーザが 定義できることを許し、複数のエンコーディングを変換なしで同時 に取り扱うことを許す。 \medskip \par 過去のRuby開発の経験から、マルチバイト文字列の操作は実はいく つかの基本関数をそれぞれのエンコーディングごとに定義するだけ で、比較的効率良く実現できることが分かっている。そこでそれを 自由にユーザ定義できるAPIを開放することを考える。 \medskip \par このことによって、ユーザは拡張ライブラリを定義することによっ て自分が使いたいエンコーディングをサポートする機能をRubyに追 加できる。 \medskip \newpage \section{動作環境} \label{動作環境} \medskip \par 今回の開発に用い、動作確認を行った環境は以下の通りである。 \medskip { \renewcommand{\theenumi}{(\arabic{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item ハードウェア \medskip \par IBM互換機を用いる。 \medskip \begin{description} \item[CPU:]Intel Pentium III 650 MHz \item[メモリ:]128MB \item[HDD:]20GB \medskip \end{description} \item ソフトウェア \medskip \begin{description} \item[OS:]Linux 2.2.18 \item[Cライブラリ:]glibc 2.2.2 \item[Cコンパイラ:]gcc 2.95.3 \medskip \end{description} \end{enumerate} } \newpage \section{外部仕様} \label{外部仕様} \medskip \subsection{入出力仕様} \label{入出力仕様} \medskip { \renewcommand{\theenumi}{(\arabic{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item インタプリタ実装の改善 \medskip \par インタプリタ実装の改善は性能の向上だけを実現し、外部仕様 は現状のRubyと等しい。現状のRubyの仕様に関しては \medskip {\par\baselineskip=10pt \begin{verbatim} http://www.ruby-lang.org/ja/doc.html \end{verbatim}} \medskip \par を参照のこと。 \medskip \item GC実装の改善 \medskip \par GC実装の改善は性能の向上だけを実現し、外部仕様は現状の Rubyと等しい。現状のRubyの仕様に関しては \medskip {\par\baselineskip=10pt \begin{verbatim} http://www.ruby-lang.org/ja/doc.html \end{verbatim}} \medskip \par を参照のこと。 \medskip \newpage \item 多言語対応 \medskip \par 現状のRubyの仕様に、以下の点を追加する。 \medskip \begin{itemize} \item コマンドライオプション -K \medskip \par 現在、euc, sjis, utf-8, none(ASCII)のエンコーディングの 指定が可能だが、これをユーザ定義を含む任意のエンコーディ ングを指定できるようにする。 \medskip \item Stringクラスのencodingメソッドおよびencoding$=$メソッド \medskip \par encodingメソッドが文字列のエンコーディングを取得し、 encoding$=$メソッドがエンコーディングを設定する。 \medskip \item Regexpクラスのencodingメソッドおよびencoding$=$メソッド \medskip \par encodingメソッドが正規表現のエンコーディングを取得し、 encoding$=$メソッドがエンコーディングを設定する。 \medskip \item IOクラスのencodingメソッドおよびencoding$=$メソッド \medskip \par encodingメソッドがIOから読み込んでくる文字列のエンコー ディングを取得し、encoding$=$メソッドがエンコーディン グを設定する。 \medskip \end{itemize} \par また、Stringクラスの以下のメソッドが「文字」単位で動作するよ うに変更する。 \medskip {\par\baselineskip=10pt \begin{verbatim} length, [], []=, ==, index, rindex, succ, slice, gsub, sub, replace, reverse, include?, inspect, dump, upcase, downcase, capitalize, swapcase, tr, tr_s, delete, squeeze, count, split, strip, scan \end{verbatim}} \medskip \end{enumerate} } \newpage \subsection{要求仕様} \label{要求仕様} \medskip { \renewcommand{\theenumi}{(\arabic{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item インタプリタ実装の改善 \medskip \par 再帰を多用するプログラムにおいて処理速度が50\%以上向上するこ と。消費メモリが著しく増大しないこと。 \medskip \item GC実装の改善 \medskip \par オブジェクトを大量に割り当てるプログラムにおいてGC処理時 間が有意に向上すること。また、その際の消費メモリ空間の増 大が20\%以内であること。 \medskip \item 多言語対応 \medskip \par 現状のマルチバイト文字列処理と比較して、文字単位の個々の処理 速度の低下が１０％以内であること。 \medskip \end{enumerate} } \newpage \section{内部仕様} \label{内部仕様} \medskip \subsection{インタプリタ実装の改善} \label{インタプリタ実装の改善} \medskip \subsubsection{仮想マシンの構成} \label{仮想マシンの構成} \medskip \par プログラムは仮想マシンコードとして表現される。仮想マシンは以 下のレジスタを持つ。 \medskip \begin{itemize} \item self \medskip \par 現在実行中のメソッドの実行主体オブジェクト。 \medskip \item pc \medskip \par 現在実行中の仮想マシンコードのアドレス。 \medskip \item sp \medskip \par スタックポインタ。スタックはlongの配列であり、GC時にはコ ンサバティブなスキャンが行われる。 \medskip \item acc \medskip \par アキュムレータ。最後の演算結果が格納される。 \medskip \item env \medskip \par 現在実行中のメソッドの環境を含むオブジェクト。 \medskip \item pool \medskip \par 実行中のメソッドの定数の保管場所を示すポインタ。 \medskip \item locals \medskip \par 実行中のメソッドのローカル変数の保管場所を示すポインタ。 \medskip \end{itemize} \subsubsection{仮想マシンコードの仕様} \label{仮想マシンコードの仕様} \medskip \par 仮想マシンコードは、C言語のintの配列として実装する。今回実装 する仮想マシンコードの命令を以下に示す。 \medskip {\par\baselineskip=10pt \begin{verbatim} STOP インタプリタを停止させる。 DEFUN i n poolのn番目のデータからメソッドiを定義する。 FCALL i メソッドを呼び出す。iはメソッド名(ID)。 RETURN メソッドを終了する。 JMP_FALSE n accが偽ならジャンプする。nは符号付き整数。 POP スタックの先頭をaccに入れる。 PUSH_ACC accレジスタの値をスタックにプッシュする。 PUSH_SELF selfレジスタの値をスタックにプッシュする。 PUSH_LIT n poolのn番目のリテラル値をスタックにプッシュする。 PUSH_CONST n 定数nをスタックにプッシュする。 PUSH_LVAR n n番目のローカル変数の値をスタックにプッシュする。 LOAD_LVAR n n番目のローカル変数の値をaccに入れる。 LOAD_INT n 整数nをaccに入れる。 \end{verbatim}} \medskip \par 今回の実装では仮想マシンは、現在の*pcの値で分岐する一つの大 きなswitch文で実装される。 \medskip \par 各命令の実装は以下の通り。 \medskip \begin{description} \item[STOP:]~ \medskip \par インタプリタを停止させる。 \medskip \item[DEFUN i n:]~ \medskip \par *pcからi(int)とn(int)を取り出し、poolのn番目のデー タをメソッドテーブルに名称iで登録する。 \medskip \item[FCALL n:]~ \medskip \par *pcからn(ID)を取り出し、メソッドテーブルからメソッ ドを検索する。新しいenvを割り当て、戻り番地をセットしてか ら、メソッドを呼び出す。 \medskip \item[RETURN:]~ \medskip \par envから戻り番地を取り出し、現在のenvを取り除く。それからpc に戻り番地をセットする。sp, pool, localsの各レジスタの値も 復旧する。 \medskip \item[JMP\_FALSE n:]~ \medskip \par *pcからn(int)を取り出し、accの値が偽であればpcに加 える。真であれば、そのまま次の命令を実行する。 \medskip \item[POP:]~ \medskip \par スタックトップの値をaccに代入し、spをデクリメントする。 \medskip \item[PUSH\_ACC:]~ \medskip \par accレジスタの値をスタックにプッシュする。 \medskip \item[PUSH\_SELF:]~ \medskip \par selfレジスタの値をスタックにプッシュする。 \medskip \item[PUSH\_LIT n:]~ \medskip \par *pcからn(int)を取り出し、pool[n]をスタックにプッシュ する。 \medskip \item[PUSH\_CONST n:]~ \medskip \par *pcからn(VALUE)を取り出し、スタックにプッシュする。nは Fixnum, True, Falseなどの即値。 \medskip \item[PUSH\_LVAR n:]~ \medskip \par *pcからn(int)を取り出し、n番目のローカル変数 の値をスタックにプッシュする。 \medskip \item[PUSH\_LVAR n:]~ \medskip \par *pcからn(int)を取り出し、n番目のローカル変数 の値をaccに代入する。 \medskip \item[PUSH\_LVAR n:]~ \medskip \par *pcからn(int)を取り出し、n番目のローカル変数 の値をaccレジスタに格納する。 \medskip \item[PUSH\_INT n:]~ \medskip \par *pcからn(int)を取り出し、accレジスタに格納する。 \end{description} \newpage \subsection{GC実装の改善} \label{GC実装の改善} \medskip \subsubsection{世代の実装} \label{世代の実装} \medskip \par 本開発の世代別GCでは２つの世代(新世代、旧世代)を扱うこと とする。新世代はと旧世代の区別は以下の２点で行う。 \medskip \begin{itemize} \item 旧世代オブジェクトはマークビットがセットされている。 \medskip \item すべての新世代オブジェクトは１本の単方向リストとして リンクされている。各オブジェクトは新世代オブジェクト としてリンクされるための新世代リンク領域を持っている。 \medskip \end{itemize} \par オブジェクトが新世代GCを生き延びた場合、マークビットがセッ トされ旧世代に分類される。新世代オブジェクトのリンクリス トはスイープ時に用いられる。 \medskip \subsubsection{新世代GCの実装} \label{新世代GCの実装} \medskip \par 新世代GCは以下の手順で行われる。 \medskip { \renewcommand{\theenumi}{(\alph{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item 割り当て済みのオブジェクトのリンクであるフリーリスト が空になったタイミングで起動される。 \medskip \item ルートから直接、間接に参照できる新世代オブジェクトに マークを付ける。 \medskip \item 新世代オブジェクトのリンクリストをたどり、マークが付 いていない新世代オブジェクトを開放し、フリーリストに つなぐ。 \medskip \item マークが付いていたオブジェクトのマークを残したままに することで、旧世代オブジェクトとする。 \medskip \end{enumerate} } \newpage \subsubsection{旧世代GCの実装} \label{旧世代GCの実装} \medskip { \renewcommand{\theenumi}{(\alph{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item 新世代GC終了後、フリーリストにつなげられたオブジェク トの数が定数FREE\_MIN\_MINOR以下であれば、旧世代GCを起 動する。 \medskip \item 全オブジェクトのマークを外す。 \medskip \item ルートから直接、間接に参照できるオブジェクトにマーク を付ける。 \medskip \item マークが付いていないオブジェクトを開放し、フリーリス トにつなぐ。 \medskip \item マークが付いていたオブジェクトのマークを残したままに することで、旧世代オブジェクトとする。 \medskip \item 旧世代GC終了後、フリーリストにつなげられたオブジェク トの数が定数FREE\_MIN以下であれば、新たにヒープから領 域を割り当て、定数HEAP\_SLOTS個のオブジェクトをフリー リストに追加する。 \medskip \end{enumerate} } \subsubsection{世代間の参照の実装} \label{世代間の参照の実装} \medskip \par 旧世代オブジェクトから新世代オブジェクトへの参照が発生し た場合、その参照はルートとして保護する必要がある。以下の 手順で旧世代から新世代への参照を保護する。 \medskip { \renewcommand{\theenumi}{(\alph{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item インタプリタ内でオブジェクトの参照を付け替える部分す べてに新世代に対するチェックを追加する。チェックでは 以下のb, cの処理を行う。 \medskip \item 参照元の旧世代オブジェクトが配列またはハッシュ以外で あった場合、そのオブジェクトのマークを外し、リフレッ シュドリストに追加する。リフレッシュドリストに追加さ れたオブジェクトは新世代リンク領域を使ってリンクされ る。リフレッシュドリストはGC時にルートとして扱われる。 \medskip \item 参照元の旧世代オブジェクトが配列またはハッシュであっ た場合、参照先の新世代オブジェクトをリファレンスドリ ストに追加する。リファレンスドリストはGC時にルートと して扱われる。リファレンスドリストに追加されるオブジェ クトは元々新世代オブジェクトであるため、新世代リンク 領域は使えない。別にリンクリストを用意する必要がある。 \medskip \item オブジェクトタイプがT\_DATAであるオブジェクトは他のオ ブジェクトに対する参照を含む可能性があり、旧世代に属 するT\_DATAオブジェクトが更新された場合は保護の対象と する必要がある。そこで、マクロData\_Get\_Struct()によっ て構造体ポインタが取り出された場合は、参照が更新され た可能性があるので、リフレッシュドリストに追加する。 ただし、T\_DATAオブジェクトからのマーク用関数ポインタ であるdmarkメンバが初期化されていない場合には、そも そも他のオブジェクトへの参照を含まないことが明らかな ので、この処理は必要ない。 \medskip \end{enumerate} } \subsubsection{明示的なリサイクルの実装} \label{明示的なリサイクルの実装} \medskip \par 現在のRubyの実装では、他から参照されていないことが明らか なオブジェクト(メソッドの呼び出しフレームなど)は明示的に フリーリストに戻されている。世代別GCではこのままフリーリ ストに戻す処理では、新世代リンクが不整合を起こすので、専 用のリサイクルドリストに追加する。リサイクルドリストは新 世代リンク領域を用いたリンクリストである。リサイクルドリ ストは第二のフリーリストとしてオブジェクトの割り当て時に 用いる。 \medskip \newpage \subsection{多言語対応} \label{多言語対応} \medskip \par 7つの必須関数と5つの補助関数、2つの補助属性を定義することに よって新規のエンコーディングをサポートすることができる。7つ の必須関数以外は省略することができる。 \medskip \par 現在の実装レベルでは、実行効率の達成のため、扱うエンコーディ ングに対して以下の制限を課す。 \medskip \begin{itemize} \item 対応するエンコーディングがステートレスであること、つまり、 あるコードに対応する文字が文脈によらず一意に決まること、 また、同一の文字列に対する表現が一意に決まること。 \medskip \item 対応する文字集合がASCIIのスーパーセットであること、つま りASCIIに含まれる文字のコードがASCIIでもコードと等しいこ と。 \medskip \item 対応するエンコーディングがASCIIのスーパーセットであるこ と、つまりASCIIに含まれる文字を表現するバイト列が、１文 字あたり１バイトであり、文字コードも一致すること。 \medskip \end{itemize} \newpage \subsubsection{エンコーディング定義API} \label{エンコーディング定義API} \medskip \par エンコーディング定義APIを以下に示す。 \medskip \begin{description} \item[必須:]~ \medskip {\par\baselineskip=10pt \begin{verbatim} m17n_encoding *m17n_define_encoding(char *name): エンコーディングを表現する構造体を割り当てる。 void m17n_encoding_func_mbclen(m17n_encoding *enc, int (*func()): ある文字コードが何バイトを占めるかを返す関数を指定する。 関数のプロトタイプは int (*func)(int c, struct m17n_encoding* enc) void m17n_encoding_func_codelen(m17n_encoding *enc, int (*func)()): あるバイト値から始まるマルチバイト文字が何バイトを占める かを返す関数を指定する。関数のプロトタイプは int (*func)(int c, struct m17n_encoding* enc) void m17n_encoding_func_mbcspan(m17n_encoding *enc, int (*func)()): ある文字コードが何バイトを占めるかを返す関数を指定する。 関数のプロトタイプは int (*func)(uint c, struct m17n_encoding* enc) void m17n_encoding_func_islead(m17n_encoding *enc, int (*func)()): あるバイト値がマルチバイト表現の先頭バイト以外に登場しな いかどうかを判定する関数を指定する。関数のプロトタイプは int (*func)(int c, struct m17n_encoding* enc) void m17n_encoding_func_codepoint(m17n_encoding *enc, uint (*func)()): マルチバイト文字列から先頭の文字コードを取得する関数を指 定する。関数のプロトタイプは uint (*func)(uchar *p, uchar *e, struct m17n_encoding* enc) void m17n_encoding_func_firstbyte(m17n_encoding *enc, int (*func)()): ある文字コードのマルチバイト表現の先頭バイトを返す関数を 指定する。関数のプロトタイプは int (*func)(uint c, struct m17n_encoding* enc) void m17n_encoding_func_mbcput(m17n_encoding *enc, void (*func)()): ある文字コードのマルチバイト表現を指定したアドレスに格納 する関数を指定する。格納するアドレスに空間があることは事 前にm17n_mbcspan()で確認する必要がある。関数のプロトタイ プは void (*func)(int c, uchar *p, struct m17n_encoding* enc) \end{verbatim}} \medskip \newpage \item[省略可能属性:]~ \medskip {\par\baselineskip=10pt \begin{verbatim} void m17n_encoding_mbmaxlen(m17n_encoding *enc, int n): マルチバイト文字の占める最大長を指定する。省略可能関数の デフォルト定義で高速化のために用いられているだけなので、 省略しても効率にしか影響しない。 void m17n_encoding_asciicompat(m17n_encoding *enc, int n): エンコーディングがASCIIの上位互換であるときに非ゼロを指 定する。現在の実装ではエンコーディングはASCIIの上位互換 である必要があるので、指定に意味はない。 \end{verbatim}} \medskip \item[省略可能関数:]~ \medskip \par 省略可能な関数は必須関数から定義される。エンコーディング特 有の性質からより高速な関数が定義できる場合に指定する。 \medskip {\par\baselineskip=10pt \begin{verbatim} void m17n_encoding_func_strlen(m17n_encoding *enc, int (*func)()): マルチバイト文字列の長さを返す関数を指定する。関数のプロ トタイプは int (*func)(uchar *p, uchar *e, struct m17n_encoding* enc) void m17n_encoding_func_nth(m17n_encoding *enc, uchar *(*func)()): マルチバイト文字列のn番目の文字の始まる位置を返す関数を 指定する。関数のプロトタイプは uchar *(*func)(uchar *p, uchar *e, int n, struct m17n_encoding* enc) void m17n_encoding_func_ctype(m17n_encoding *enc, int (*func)()): ある文字コードの種別を判定する関数を指定する。関数のプロ トタイプは int (*func)(uint c, uint code, struct m17n_encoding* enc) void m17n_encoding_func_toupper(m17n_encoding *enc, uint (*func)()): ある文字を大文字に変換した文字コードを返す関数を指定する。 関数のプロトタイプは uint (*func)(uint c, struct m17n_encoding* enc) void m17n_encoding_func_tolower(m17n_encoding *enc, uint (*func)()): ある文字を小文字に変換した文字コードを返す関数を指定する。 関数のプロトタイプは uint (*func)(uint c, struct m17n_encoding* enc) \end{verbatim}} \medskip \end{description} \newpage \subsubsection{エンコーディング操作API} \label{エンコーディング操作API} \medskip \par 指定した関数の呼出しはエンコーディング構造体を経由して、以下 の関数(実際はマクロ)を用いて行う。 \medskip {\par\baselineskip=10pt \begin{verbatim} void m17n_mbmaxlen(enc) void m17n_asciicompat(enc) void m17n_strlen(enc,p,e) void m17n_mbclen(enc,c) void m17n_codelen(enc,c) void m17n_mbcspan(enc,p,e) void m17n_islead(enc,c) void m17n_nth(enc,p,e,n) void m17n_codepoint(enc,p,e) void m17n_firstbyte(enc,c) void m17n_mbcput(enc,c,p) \end{verbatim}} \medskip \subsubsection{Ruby M17N} \label{Ruby M17N} \medskip \par 前節までで規定した、エンコーディングAPIをベースにして、Ruby の組み込みクラスに対して以下の修正を行う。 \medskip { \renewcommand{\theenumi}{(\alph{enumi})} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item -Kオプションで指定するものを単なる整数定数から、エンコー ディング構造体の名称に変更する。 \medskip \item StringクラスおよびRegexpクラスのオブジェクトにそれぞれ エンコーディング構造体を関連づける。 \medskip \item Rubyの文字を対象として処理を行うすべてのメソッドにおい て、文字の切り出しなどの操作をすべて上記のマクロを用い て行うように書き換える。また、レシーバのStringオブジェ クトと引数のStringオブジェクトのエンコーディングが等し いかどうかのチェックを追加する。 \medskip \item 正規表現ルーチンを上記のマクロを用いるように書き換える。 \medskip \item IOクラスのオブジェクトにエンコーディング構造体を関連づ ける。 \medskip \item IOクラスのオブジェクトからの入力データに、(e)で関連づ けられたエンコーディング構造体を関連づけて文字列を生成 する。 \medskip \end{enumerate} } \newpage \section{検査方法} \label{検査方法} \medskip \subsection{インタプリタ実装の改善} \label{インタプリタ実装の改善} \medskip \par 再帰テスト用関数 tak を改善前のruby 1.6.3と仮想マシンプロ トタイプとで実行し、timeで計測した実行時間を比較する。tak.rb は竹内関数tak(18,12,6)を20回計算するものとする。 \medskip \par takの定義は以下の通り。 \medskip {\par\baselineskip=10pt \begin{verbatim} def tak(x, y, z) if y >= x z else tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y)) end end \end{verbatim}} \medskip {\par\baselineskip=10pt \begin{verbatim} def test_tak() tak(18, 12, 6) end \end{verbatim}} \medskip {\par\baselineskip=10pt \begin{verbatim} test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() test_tak() \end{verbatim}} \medskip \par 今回のプロトタイプにはこのコードがハンドコンパイルされ、ソー スコードに組み込まれている。よってruby-vmはプログラムを引数 としてとらない。試験手順は以下の通り。 \medskip {\par\baselineskip=10pt \begin{verbatim} cd ruby time ruby tak.rb cd ../ruby-vm time ruby-vm \end{verbatim}} \medskip \newpage \subsection{GC実装の改善} \label{GC実装の改善} \medskip \par 大量のオブジェクトを生成するプログラムを実行し、その実行 による実行速度とメモリサイズを測定する。GCの性能を測定す るためにログを出力するようプログラムを修正するパッチを適 用する。 \medskip \par 試験スクリプトoccur.rbの内容は以下の通り。 \medskip {\par\baselineskip=10pt \begin{verbatim} start = Time.now freq = Hash.new(0) while gets() for word in $_.split(/\W+/) freq[word] += 1 end end \end{verbatim}} \medskip {\par\baselineskip=10pt \begin{verbatim} for word in freq.keys.sort! print word, " -- ", freq[word], "\n" end p Time.now - start p $$ sleep \end{verbatim}} \medskip \par このファイルはRubyのソースコードアーカイブに sample/occur.rbとして含まれている。ログ出力用のパッチは 世代別GCのソースコードとおなじところから入手できる。 \medskip \par 試験手順は以下のとおり。 \medskip {\par\baselineskip=10pt \begin{verbatim} cd ruby-gc time ruby occur.rb *.[chy] > /dev/null \end{verbatim}} \medskip \newpage \subsection{多言語対応} \label{多言語対応} \medskip \par ３種類のエンコーディングに対応した試験スクリプトを実行する。 試験スクリプトは以下の点をチェックする。 \medskip \begin{itemize} \item Stringのメソッドが文字単位で動作するかどうか \item 正規表現がマルチバイト文字列にマッチするか \medskip \end{itemize} \par 試験スクリプトはM17N化Rubyのソースコードアーカイブの中に 含まれる。ファイル名はそれぞれtest-e.rb(EUC)、 test-s.rb(SJIS)、test-u.rb(UTF-8)である。これらの試験の 各項目は試験に成功した場合に"."を、失敗した場合にはその 行番号と理由を表示する。 \medskip \par 試験手順は以下の通り。 \medskip {\par\baselineskip=10pt \begin{verbatim} cd ruby-m17n ruby -Ke test-e.rb ruby -Ks test-s.rb ruby -Ku test-u.rb time /usr/bin/ruby -Ke test-re.rb time ruby -Ke test-re.rb \end{verbatim}} \medskip \newpage \section{評価，今後の課題，展望，} \label{評価，今後の課題，展望，} \medskip \subsection{インタプリタ実装の改善} \label{インタプリタ実装の改善} \medskip \par 今回は開発期間の関係上、インタプリタ実装は満足の行くレベ ルの実装は叶わなかった。期間内には仮想マシンの設計と実行 系の一部の実装にとどまった。今回のプロトタイプはtak関数 がハンドコンパイルされて埋めこまれている。 \medskip \par tak関数の実行時間は以下の通りである。 \medskip \begin{table}[htbp] \begin{center} \begin{tabular}{|l|c|} \hline 従来のRuby & 5.122sec\\ \hline プロトタイプ & 0.922sec\\ \hline \end{tabular}\\ \end{center} \end{table} \medskip \par プロトタイプはいくつかの重要な処理(たとえば構文解析) を 行っていないため、この数値は参考値に過ぎないが、今後より 高速なインタプリタの実現の可能性を示唆している。 \medskip \par Rubyインタプリタのコア部分は本質的に複雑で、今回実装した プロトタイプは実用的なレベルではない。今回実装したのは、 メソッド定義、ローカル変数参照(一部)、メソッド呼び出し部 のみである。このプロトタイプでは測定に用いたtak関数以外 のプログラムはほとんど正常に動作しない。 \medskip \par 今後はこのプロトタイプをベースにより高速な実用レベルのインタ プリタを完成させる予定である。 \medskip \subsection{GC実装の改善} \label{GC実装の改善} \medskip \par 今回の世代別GCの実装により、occur.rbの実行時間は以下のよ うになった。 \medskip \begin{table}[htbp] \begin{center} \begin{tabular}{|l|c|} \hline 従来のRuby & 4.517sec\\ \hline 世代別GC & 3.879sec\\ \hline \end{tabular}\\ \end{center} \end{table} \medskip \par これにより、世代別GCが実行速度向上に有効であることが明ら かになった。また、GCのログからは以下の結果が得られた。 \medskip \begin{table}[htbp] {\list{}{\leftmargin=4ex}\item[] \begin{tabular}{|l|r|r|r|} \hline & GC回数 & スキャン数 & 総オブジェクト数\\ \hline 従来のRuby & 111回 & 21403 & 20000\\ \hline 世代別GC & 82回 & 683411 & 20000\\ \hline \end{tabular}\\ \mbox{}\endlist} \end{table} \medskip \par 今回計測したoccur.rbは、大量のオブジェクトを生成し、ゴミ がほとんど発生しないという、世代別GCにとって理想的な状況 ではあるが、その他のプログラムにおいても５％から５０％程 度のGC 処理時間の減少が観測されている。メモリ消費量につ いても、最悪のケースでも１０％強程度の増加でとどまってい ることが明らかになった。 \medskip \par しかし、この世代別GCにはいまだバグがあり、ごくまれにインタプ リタが異常終了する。今後はこのバグを発見・修正したい。 \medskip \newpage \subsection{多言語対応} \label{多言語対応} \medskip \par 今回の開発によって、たとえば、フレームワークを利用して EUC-JP対応を追加するために必要なコード量はCプログラムで わずか109行であった。UTF-8の場合にはもう少し多くて132行 であった。 \medskip \par このエンコーディングサポートのフレームワークによって、現時点 ではサポートしていないBig5(台湾)やEUC-KR(韓国)、KOI-8 (ロシ ア)のようなエンコーディングも、同様にわずかの記述で実現でき ると考えられる。 \medskip \par ただし、現在の仕様では、-Kオプションで指定するデフォルト 以外のエンコーディングを用いる場合には、プログラム中で頻 繁に明示的なエンコーディングの指定を必要とする。これはプ ログラムの簡潔性と明瞭さを疎外する可能性があるので、今後 もユーザの立場からより使いやすい仕様を検討する必要がある。 \medskip \par また、現在存在する以下の制限が緩和できるかどうかについて、さ らなる検討が必要だと思われる。 \medskip \begin{itemize} \item 対応するエンコーディングがステートレスであること \medskip \item 対応する文字集合がASCIIのスーパーセットであること \medskip \item 対応するエンコーディングがASCIIのスーパーセットであること \medskip \end{itemize} \par 現時点の感触では、ファイルエンコーディングとしては、最初の制 限以外は緩和することが可能であると思われる。最初の制限につい てはなんらかのコード変換することで対応するものと考えられる。 \medskip \par プログラムを記述するエンコーディングとしては、上記３つの制限 はいずれも緩和できそうにない。しかし、最後の制限を満たさない UTF-16およびUCS4 はそのエンコーディングとしての地位の重要性 から、特別にサポートすることは考えられる。 \medskip \newpage \subsection{期待される効果} \label{期待される効果} \medskip \par 今回の開発により、性能面での改善のめどが立ったので、対象領域 がオーバーラップするPerlやPythonなどと比較して、実行性能での 競争力が向上すると考えられる。また、性能の向上は、インタプリ タ型なので遅いというイメージの改善に寄与すると思われ、今まで 以上にRubyの適用範囲が広がることが期待できる。 \medskip \par また、多言語化対応機能の開発により実現された、ユーザが自由に エンコーディングが定義できるインタプリタ言語は他に例がないの で、今後の国際化プログラミングにおいて、他の言語をもってして 代えがたい、重要な位置を占めることが期待される。 \medskip \subsection{今後の課題} \label{今後の課題} \medskip \par 現状では、今回開発した３つの改善点はまだリリース版のインタプ リタに統合されていない。その主な理由は、実装の不安定さによる ものである。上で考察したとおり、これらの改善はRubyにとって重 要な改善であるので、できる限り早い時期の安定化と統合を目指し、 実現させることが当面の急務である。 \medskip \newpage \section{操作手順書} \label{操作手順書} \medskip \par Rubyの操作手順書(リファレンスマニュアル)は以下のURLを参照の こと。 \medskip \par http://www.ruby-lang.org/ja/doc.html \medskip \section{入手方法及びインストール方法} \label{入手方法及びインストール方法} \medskip \par Rubyの入手法は \medskip \par http://www.ruby-lang.org/ja/download.html \medskip \par を参照のこと。また、そのインストール法は \medskip \par http://www.ruby-lang.org/ja/install.html \medskip \par を参照のこと。今回、開発したソースコードは近日中に開発版に統 合され、公開される。統合前の個別のソースコードは以下から入手 可能にするである。 \medskip \par http://www.ruby-lang.org/\verb+~+matz/ipa/index.html \medskip \par なお、検査スクリプトのうちoccur.rbは、rubyのソース配布中に sample/occur.rb として添付されている。 \end{document}