サーバサイド向け JavaScript 処理系の ためのマークスイープごみ集め

平成 27 年度
学士学位論文
サーバサイド向け JavaScript 処理系の
ためのマークスイープごみ集めの
設計と実装
Design and Implementation of a Mark Sweep
Garbage Collection on a Server Side JavaScript
Virtual Machine
1160326
高松 裕樹
指導教員
鵜川 始陽
2016 年 2 月 26 日
高知工科大学 情報学群
要 旨
サーバサイド向け JavaScript 処理系の
ためのマークスイープごみ集めの
設計と実装
高松 裕樹
Web ブラウザの高機能化に伴って，Web ブラウザ上で動作する Web アプリケーションが
普及している．Web アプリケーションは，Web ブラウザ上で JavaScript のプログラムとし
て動作し，Web サーバ上のプログラムと通信しながら高度なサービスを提供する形態をと
る．近年，Web アプリケーションのサーバ側のプログラムの開発言語として JavaScript が
普及してきている．そのため，サーバ上で動作する JavaScript（サーバサイド JavaScript）
の処理系の高速化の研究が盛んに行われている．サーバ上では大規模なプログラムを動かす
ことが多いと予想される．その際にプログラムの処理時間に大きく影響を与えるのが，ガ
ベージコレクション（以下，GC）である．GC とは，メモリ領域上のプログラムが利用し
なくなった領域を回収して，再度利用可能にする処理である．GC 実行中はプログラムの処
理が停止しているため，GC の時間はそのままプログラムの実行時間に影響を与える．本研
究では，サーバサイド向け JavaScript 仮想機械である SSJSVM の GC について，他の処
理系に比べて高速かどうか調べた．その結果，既存の SSJSVM の GC は他の処理系の GC
に比べて遅いことがわかった．そこで，GC の性能改善を狙って SSJSVM にマークスイー
プ GC を実装した．本研究で実装した GC の性能を調べるために，既存の SSJSVM と実行
時間を比較した．その結果，本研究の GC は SSJSVM の性能を改善しないことが分かった．
さらに調査した結果，本研究の GC はメモリ割り当てが遅いことがわかった．
キーワード
JavaScript，ガベージコレクション，マークスイープ，BoehmGC
–i–
Abstract
Design and Implementation of a Mark Sweep Garbage
Collection on a Server Side JavaScript Virtual Machine
Yuki TAKAMATSU
With the high functionality of Web browsers，Web applications widely spread．
Web applications are written in JavaScript and work on Web browsers．A Web application communicates with a program running on the server to provide rich services to
the users．Recently，JavaScript spread as a language for server side programs of Web
applications．Therefore，studies of speeding up JavaScript processing on servers are
conducted flourishingly．On servers，it is expected that we often use large-scale programs．In this situation，it is garbage collection（GC）that greatly affect the execution
times of programs．GC is a routine that reclaims memory areas that are no longer used
so that the user program can reuse the areas．Because the execution of the program
stops during GC，GC affects the execution time of the program directly．In this study，
we investigated whether GC of a server side JavaScript virtual machine，SSJSVM，is
efficient compared to other JavaScript virtual machines．As a result，we found that GC
of SSJSVM was slower．Then，we implemented a mark sweep GC in SSJSVM aiming
the performance improvement．To investigate performance of the GC that we implemented in this study，we compare the execution time of our SSJSVM with that of the
existing SSJSVM．As a result，we found that our GC did not improve performance．
Further investigation showed that memory allocation of our GC was mach slower than
that of the existing SSJSVM．
– ii –
key words
JavaScript，Garbage Collection，Mark Sweep，BoehmGC
– iii –
目次
第1章
はじめに
1
1.1
研究の背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
本研究の内容 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
SSJSVM
4
2.1
SSJSVM とは . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
SSJSVM の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
第2章
第3章
2.2.1
関数フレーム . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2.2
関数テーブル . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.3
JSValue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.4
グローバルオブジェクト
. . . . . . . . . . . . . . . . . . . . . . .
9
2.2.5
オブジェクトの構造 . . . . . . . . . . . . . . . . . . . . . . . . . .
9
SSJSVM の GC
13
3.1
GC の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.2
GC アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.3
BoehmGC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.4
SSJSVM における GC の検証 . . . . . . . . . . . . . . . . . . . . . . . .
16
第4章
4.1
3.4.1
検証方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.4.2
検証結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
マークスイープ GC の実装
20
マークスイープ GC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.1.1
マークフェーズ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
– iv –
20
目次
4.2
4.1.2
スイープフェーズ . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.1.3
メモリ割り当て . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
設計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4.2.1
フリーリスト . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.2.2
GC のタイミング . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2.3
マークフェーズ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
OBJECT 型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
STRING 型，FLONUM 型 . . . . . . . . . . . . . . . . . . . . . .
26
ARRAY 型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
その他の型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
スイープフェーズ . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
実装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.2.4
4.3
第5章
5.1
4.3.1
GC の対象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.3.2
メモリの割り当て . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.3.3
マークの付与 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
4.3.4
オブジェクトの辿り方 . . . . . . . . . . . . . . . . . . . . . . . . .
33
JavaScript のグローバル変数 . . . . . . . . . . . . . . . . . . . . .
33
JavaScript のローカル変数 . . . . . . . . . . . . . . . . . . . . . .
33
C 言語のグローバル変数 . . . . . . . . . . . . . . . . . . . . . . .
33
C 言語のローカル変数 . . . . . . . . . . . . . . . . . . . . . . . . .
33
関数呼び出しの返り値を格納するレジスタ . . . . . . . . . . . . . .
34
汎用レジスタ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
文字列テーブル . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
評価
36
検証方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
–v–
目次
5.2
検証結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
5.3
考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.4
今後の課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
第6章
関連研究
44
第7章
おわりに
45
謝辞
46
参考文献
47
– vi –
図目次
2.1
制御スタックの様子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
関数フレームの様子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
STRING 型と FLONUM 型のオブジェクトの構造 . . . . . . . . . . . . .
11
2.4
STRING 型と FLONUM 型以外のオブジェクトの構造 . . . . . . . . . . .
12
2.5
オブジェクトのヘッダのフォーマット
. . . . . . . . . . . . . . . . . . . .
12
2.6
グローバルオブジェクトとハッシュテーブル，配列の関係 . . . . . . . . . .
12
3.1
GC を持つシステムでのプログラムの実行 . . . . . . . . . . . . . . . . . .
14
3.2
quick 処理系のメモリ割り当て . . . . . . . . . . . . . . . . . . . . . . . .
18
3.3
メモリを多く消費して頻繁に GC が起こるプログラムの実行時間の比較 . .
19
3.4
3 種類の SSJSVM 処理系と Node.js の実行時間の比較 . . . . . . . . . . .
19
4.1
マークフェーズ時のヒープ領域 . . . . . . . . . . . . . . . . . . . . . . . .
21
4.2
スイープフェーズ時のヒープ領域 . . . . . . . . . . . . . . . . . . . . . . .
22
4.3
ヒープ領域上のフリーリストの様子 . . . . . . . . . . . . . . . . . . . . . .
23
4.4
OBJECT 型オブジェクトの構造 . . . . . . . . . . . . . . . . . . . . . . .
25
4.5
STRING 型，FLONUM 型オブジェクトの構造 . . . . . . . . . . . . . . .
26
4.6
ARRAY 型オブジェクトの構造 . . . . . . . . . . . . . . . . . . . . . . . .
27
4.7
スイープフェーズの動作の例 . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.8
C 言語のローカル変数を保存するスタック . . . . . . . . . . . . . . . . . .
34
5.1
オブジェクトの割り当てと malloc 関数で使用したメモリ領域の大きさ . . .
38
5.2
オブジェクトの割り当てと malloc 関数でのメモリ割り当ての回数
. . . . .
39
5.3
本研究の GC を持つ SSJSVM と既存の SSJSVM の実行時間の比較 . . . .
40
– vii –
図目次
5.4
5.5
本研究の GC を持つ SSJSVM の実行時間の内訳と既存の SSJSVM の実行
時間の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
オブジェクトが割り当てられる度にフリーリストを辿る回数 . . . . . . . . .
42
– viii –
表目次
2.1
特殊レジスタ
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
オブジェクトのデータ型 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
5.1
ヒープ領域の大きさに対する GC の回数 . . . . . . . . . . . . . . . . . . .
40
– ix –
第1章
はじめに
1.1
研究の背景
近年，サーバサイドでの Web アプリケーションの開発言語として JavaScript が普及し
ている．Web アプリケーションとは，インターネットを通じて利用可能なソフトウェアで
ある．一般的な Web アプリケーションは，Web ブラウザと Web サーバのプログラムが通
信を行って動作することで，一つのアプリケーションとなって Web ブラウザ上で動作する．
このとき，ユーザが操作する Web ブラウザ側をクライントサイド，Web サーバ側をサーバ
サイドと呼ぶ．今までは，主にクライアントサイドでは JavaScript を使用し，サーバサイ
ドでは PHP などのスクリプト言語を用いてアプリケーションの開発が行われてきた．しか
し，近年では以下のような理由により，サーバサイドでも JavaScript が用いられるように
なってきた．まず JavaScript は，プロトタイプベースのオブジェクト指向言語であり，ク
ラスベースのオブジェクト指向言語とは違って，クラスに縛られずにオブジェクトを扱うこ
とができる．そのため，クラスベースほどプログラムが複雑化せず，単純な設計を行うこ
とができる．また，2000 年代中盤頃に Ajax と呼ばれる，JavaScript による非同期通信を
利用してクライアントサイドとサーバサイドで処理を分散させたり，動的に Web ページの
内容を書き換えることができる技術の登場と共に飛躍的に進化を遂げてきた．これにより，
JavaScript を扱えるプログラマが増え続けている．
次に，最近の JavaScript 処理系のほとんどは Just In Time（JIT）コンパイルと呼ばれ
る高速化の機能が実装されている．これは，プログラムの実行時に，ソースコードや中間
コードなどを機械語にコンパイルすることで実行速度を高速化させるコンパイル手法であ
–1–
1.1 研究の背景
る．JavaScript はこのような高速化の研究が盛んであり，他のスクリプト言語に比べ高速化
の技術が蓄積されている．
このように，扱うことのできるプログラマが豊富であることと，高速な処理系が開発でき
ることからサーバサイドでも JavaScript が注目されている．クライアントサイドと同じく
サーバサイドでも JavaScript を使用することでプログラマが新たな言語を習得する必要が
無く，開発効率の向上が期待できる．そこでサーバサイド向け JavaScript 仮想機械処理系
である SSJSVM（Server Side JavaScript Virtual Machine）[1] が開発された．
JavaScript 仮想機械には通常，ガベージコレクション (以下，GC) と呼ばれる仕組みが
必要である [2]．GC とは，プログラムが使わなくなったメモリ領域 (ごみ) を自動的に回収
する仕組みである．GC があることで，プログラマは手動でメモリの管理をする必要が無く
なり，メモリを気にせずにプログラミングを行うことができるメリットがある．GC が無い
処理系では，利用可能なメモリ領域よりも多くのメモリ領域をプログラムが使用すると，実
行しているプログラムが途中で停止してしまう．そのため，SSJSVM でも GC が実装され
ている． 現在，SSJSVM の GC は，外部ライブラリである BoehmGC[3] を用いて実装さ
れている．BoehmGC とは C 言語で開発された様々なソフトウェアで利用できるように作
られた汎用 GC ライブラリである．BoehmGC は様々なソフトウェアに対して安全に処理
を行うことができるように保守的 GC と呼ばれる手法で設計されている．保守的 GC とは，
対象のメモリ領域が回収対象なのかどうか曖昧な場合は，回収しないで安全に処理するとい
う手法である．そのため，様々な処理系に対して実装するのが簡単であるというメリットが
ある．その代わり，GC に使われるメモリ領域が多くなったり，使用可能な GC のアルゴリ
ズムが限定的で高速な GC アルゴリズムが適用できないため，GC の処理速度は遅い．ま
た，保守的 GC ではプログラムが使っているデータには一切手を加えずに，どこがごみかを
判定したり，使われているメモリ領域どこかを憶えておく必要がある．そのために，管理用
のデータ構造を作り，プログラムにメモリを割り当てたり GC するときに，管理用のデータ
構造もあわせて操作する必要がある．したがって，保守的 GC のオーバーヘッドのために，
SSJSVM に特化した GC を作成した場合に比べて性能が劣ると考えられる．
–2–
1.2 研究の目的
1.2
研究の目的
サーバサイドで大規模なプログラムを動かす際に，プログラムの処理時間に大きく影響を
与えるのが GC にかかる時間である．そのため，GC に時間がかかる処理系は望ましくな
い．そこで，本研究では，サーバサイド向け JavaScript 仮想機械である SSJSVM の GC を
高速化する．
1.3
本研究の内容
本研究では，まず SSJSVM の構造を調査の調査を行う．SSJSVM がどのような処理系
なのか，どのような仕組みで動作しているのかを調べて SSJSVM のプログラムを理解する
（2 章）．さらに，SSJSVM の性能を調査した．また，他のサーバサイド JavaScript 処理
系と処理速度を比較する．その結果から，SSJSVM に専用の GC を実装することで高速化
の余地があることがわかった（3 章）．そこで，SSJSVM に専用の GC を設計し実装した．
SSJSVM の構造にしたがって適したマークスイープ GC の設計をした．設計にしたがって，
SSJSVM にマークスイープ GC を実装した（4 章）．SSJSVM に実装したマークスイープ
GC について，SSJSVM と比較を行い，性能を検証した．この検証から，本研究のマークス
イープ GC は遅いことがわかった．原因は，メモリ割り当てが遅いことである（5 章）．
–3–
第2章
SSJSVM
第 2 章では，SSJSVM がどのような構成で作られている処理系なのかを説明する．
SSJSVM で JavaScript のプログラムをどのように実行するかを説明し，実行時に関わる処
理や SSJSVM の構造について説明する．本研究では SSJSVM に適した GC を実装するた
め，SSJSVM の構造を理解する必要がある．
2.1
SSJSVM とは
SSJSVM は中間コードにコンパイルした JavaScript のプログラムの解釈実行を行うレジ
スタベースの仮想機械である．SSJSVM で JavaScript のプログラムを実行するには，まず
SSJS コンパイラを用いてコンパイルし，JavaScript のプログラムを SSJSVM で実行する
ための中間コードであるバイトコードに変換し，そのバイトコードを SSJSVM によって実
行する．JavaScript の簡単なソースコードの例をソースコード 2.1 に示す．このコードは変
数宣言と整数の加算を行っているコードである．このコードを SSJSVM コンパイラでコン
パイルして出力されるバイトコードをソースコード 2.2 に示す．このバイトコードは，1 行
に 1 つの命令を持つ，各命令は最大 3 つの引数をとる．例えば，14 行目の命令の意味は，8
番レジスタの値と 9 番レジスタの値を足したものを 2 番レジスタに格納するという処理で
ある．
SSJSVM は高速な処理系を目指して開発しており，サーバサイドで動作することを前提
としている．また，SSJSVM は C 言語で開発されている．そのため，現在は SSJSVM の
GC には C 言語に対応した汎用 GC ライブラリである BoehmGC が利用されている [4]．
–4–
2.2 SSJSVM の構成
ソースコード 2.1 JavaScript のソースコードの例
1:
var a;
2:
var b = 10;
3:
a = b + 1;
ソースコード 2.2 JavaScript のバイトコードの例
1:
funcLength 1
2:
callentry 0
3:
sendentry 0
4:
numberOfLocals 0
5:
numberOfInstruction 13
6:
getglobalobj 1
7:
setfl 15
8:
fixnum 2 10
9:
string 5 ”b”
10:
setglobal 5 2
11:
string 10 ”b”
12:
getglobal 8 10
13:
fixnum 9 1
14:
add 2 8 9
15:
string 11 ”a”
16:
setglobal 11 2
17:
seta 2
18:
ret
2.2
SSJSVM の構成
SSJSVM は レ ジ ス タ 操 作 で バ イ ト コ ー ド を 実 行 す る 仮 想 機 械 で あ る ．実 行 時 は ，
JavaScript のプログラムの関数ごとに処理を行っている．関数を汎用レジスタの集合を使っ
て実行する．各関数で使う汎用レジスタを図 2.1 のように制御スタックに積んで，関数ごと
–5–
2.2 SSJSVM の構成
に処理を行う構造になっている．説明のために例として関数内で関数を呼び出す JavaScript
のプログラムをソースコード 2.3 で示す．このソースコードは関数 f の中で関数 g を呼び出
しているプログラムである．以降の SSJSVM 内の構成に関する説明は全て，ソースコード
2.3 のプログラムを実行する時の SSJSVM の動作に基づいて説明を行う．図 2.1 では，関
数内で関数呼び出しを行った際の制御スタックの様子を示している．関数 f が最初に呼び出
されているので，制御スタックには関数 f に関する汎用レジスタ群が積まれる．さらに，関
数 f の中で関数 g を呼び出しているので，制御スタックの関数 f の汎用レジスタ群の上に
関数 g の汎用レジスタ群が積まれる．ただし，関数呼び出しを行っているので，呼び出し元
の関数に戻るために，呼び出し先の汎用レジスタ群が積まれる前に，現在の関数の戻り番地
等の情報を制御スタックに記録しておく．
制御スタックを操作して関数を実行するために，現在実行している関数の実行情報を保持
しておく必要がある．そこで，現在実行している関数に関しては，特殊レジスタが用意され
ており，そこで現在実行している関数の実行情報を保持している．特殊レジスタの概要を表
2.1 に示す．特殊レジスタに格納された値は，制御スタック上の実行中の関数の場所を示す
ものや，関数フレームの参照，関数の返り値など関数の実行に必要な情報が格納されている．
ソースコード 2.3 関数内で関数を呼び出す JavaScript のソースコードの例
1:
var n = 2;
2:
var g = function(t){
3:
var m = t + 1;
4:
return m;
5:
}
6:
var f = function(s) {
return g(s + 1)
7:
8:
}
9:
f(n);
–6–
2.2 SSJSVM の構成
図 2.1
制御スタックの様子
表 2.1
レジスタ名
2.2.1
特殊レジスタ
レジスタが示すもの
fp
実行中の関数のレジスタ群の開始位置を示す．
sp
実行中の関数のレジスタ群の終点位置を示す．
lp
実行中の関数の関数フレームの参照を示す．
cf
関数テーブル内の実行中の関数が保持している命令列の参照を示す．
pc
実行中のプログラムカウンタを示す．
a
関数の返り値を示す．
関数フレーム
SSJSVM では関数を呼び出す度に関数フレームが作成される．関数フレームは関数の引
数を格納するオブジェクトや，ローカル変数，関数が宣言された関数フレームに対する参照，
及び関数内で定義されたローカル変数のオブジェクトなどで構成される．関数フレームの例
を図 2.2 に示す．図 2.2 の prev frame は関数が宣言された場所の関数フレームを指す参照
である．また，auguments は関数の引数を示しており，残りは関数内のローカル変数を格
納している．
–7–
2.2 SSJSVM の構成
図 2.2
2.2.2
関数フレームの様子
関数テーブル
JavaScript プログラム中の全ての関数はプログラム中で宣言された順に関数テーブルに
格納される．関数テーブル内のそれぞれの関数は，その関数に対応するバイトコードの命令
列を保持している．
2.2.3
JSValue
レジスタに格納する値は 64bit のワードであり，真偽値や整数値はデータそのものを表し，
オブジェクトや関数はデータを格納している場所を示す．データには，整数や真偽値，オブ
ジェクトや関数など様々な型がある．そこで，データを示す 64bit のワードの中で，それぞ
れのデータの型とデータを示す場所を表している．データを指すアドレスは必ず 8 の倍数
となっているため，下位 3bit は全て 0 である．そのため，データの型を下位 3bit に埋め込
んで表し，それ以外でデータを指すアドレスを表している．下位 3bit でデータの型を表す
–8–
2.2 SSJSVM の構成
ため，それぞれのデータの型には 3bit で表現できるタグ値が対応付けられている．例えば，
整数 (タグ値 7) は上位 61bit で符号付き 61bit 整数を表現して扱い，オブジェクトや関数な
どはヒープ領域上の割り当てられた領域を指すポインタにタグ値が組み込まれて表現され
る．このような，データを指す 64bit のワードを SSJSVM では JSValue として定義してい
る．SSJSVM のプログラム中では JSValue 型の変数などにデータの参照が格納されている．
2.2.4
グローバルオブジェクト
JavaScript プログラムの関数内のローカル変数など，関数に関するデータは関数フレー
ムに保持されているのに対して，関数外のデータであるグローバル変数などは，グローバ
ルオブジェクトと呼ばれる専用のオブジェクトのプロパティに保持される．SSJSVM には
JavaScript のプログラムのグローバル環境でのデータを保存しておくために，グローバル
オブジェクトと呼ばれるオブジェクトが存在する．グローバルオブジェクトのプロパティに
は JavaScript プログラムのグローバル変数が宣言された順に格納されている．
グローバルオブジェクトや特殊レジスタなど，JavaScript のプログラムを実行するのに必
要な内部情報をまとめたものを実行コンテキストと呼び，SSJSVM ではコンテキスト構造
体として用意されている．グローバルオブジェクトはこのコンテキスト構造体から参照され
ている．
2.2.5
オブジェクトの構造
オブジェクトにも様々なデータ型がある．オブジェクトのデータ型は，全部で 11 種類存
在する．オブジェクトの全てのデータ型にはタグ値が対応付けされており，オブジェクトの
データ型とタグ値の対応付けを表 2.2 に示す．
全てのオブジェクトはヘッダとデータを保持するプロパティを持っている．データ型に
よって保持するプロパティが異なるため，オブジェクトの構造はそれぞれのデータ型によっ
て異なっている．しかし，共通して全てのオブジェクトは必ずヘッダを保持している．オブ
–9–
2.2 SSJSVM の構成
表 2.2
オブジェクトのデータ型
データ型
型の説明
タグ値 (16 進数)
STRING
文字列型
4
FLONUM
浮動小数点型
5
OBJECT
一般オブジェクト型
6
ARRAY
配列型
7
FUNCTION
関数型
8
BUILTIN
組み込み関数型
9
ITERATOR
イテレータ型
a
REGEXP
正規表現型
b
STRINGOBJECT
文字列参照型
c
NUMBEROBJECT
数値参照型
d
BOOLEANOBJECT
真偽値参照型
e
ジェクトのヘッダの大きさは 64bit であり，上位 32bit でオブジェクトのサイズ，下位 3bit
でオブジェクトのデータ型を表している．このときの，オブジェクトのヘッダ部分のフォー
マットを図 2.5 に示す．
データ型は大きく 2 つに分けて考えることができる．STRING 型，FLONUM 型のデー
タ型とそれ以外の全てのデータ型である．STRING 型と FLONUM 型では文字列や浮動小
数点をそのままオブジェクトのプロパティとして保持しているオブジェクトである．それ以
外のデータ型は全て OBJECT 型と同じプロパティを保持しており，それに加えそれぞれの
データ型で必要なプロパティを保持している．STRING 型，FLONUM 型のオブジェクト
の構造を図 2.3 に，それ以外のオブジェクトの構造を図 2.4 に示す．図 2.3 は STRING 型と
FLONUM 型の構造を示しており，ヘッダと値を保持することができる構造になっている．
また，図 2.4 は STRING 型と FLONUM 型以外のデータ型の構造を示しており，OBJECT
– 10 –
2.2 SSJSVM の構成
型のプロパティとそれぞれのデータ型のプロパティを保持することができる構造になって
いる．
STRING 型と FLONUM 型のオブジェクトはそのままプロパティにアクセスすることで
必要なデータを得ることができる．それ以外の型のオブジェクトは，配列でデータを格納し
ており，その配列にアクセスするためにはハッシュテーブルから必要なデータが格納されて
いる場所を探してアクセスする．例としてグローバルオブジェクトにグローバル変数の値
が格納されている時のオブジェクトの様子を示す．このときの，グローバルオブジェクト，
ハッシュテーブル，配列の関係を図 2.6 に示す．図では，map から指されたハッシュテーブ
ル上でグローバル変数 a とグローバル変数 a の値が格納されている prop 配列の場所が対応
付けられている．また，グローバルオブジェクトは numberOfProp，limitOfProp という
2 つのプロパティを保持している．numberOfProp は prop 配列の使われている長さを示し
ており，limitOfProp は prop 配列の長さの限界を示している [5]．
図 2.3 STRING 型と FLONUM 型のオブジェクトの構造
– 11 –
2.2 SSJSVM の構成
図 2.4 STRING 型と FLONUM 型以外のオブジェクトの構造
図 2.5
図 2.6
オブジェクトのヘッダのフォーマット
グローバルオブジェクトとハッシュテーブル，配列の関係
– 12 –
第3章
SSJSVM の GC
第 3 章では，SSJSVM に GC を実装する前に GC がどのような機能を持ったプログラム
なのかを説明する．また，既存の SSJSVM に実装されている BoehmGC がどのような GC
なのかを説明する．その上で，既存の SSJSVM の GC の性能を調査して，SSJSVM に専用
の GC を実装することで性能改善できるかを調べる．
3.1
GC の概要
GC とは，プログラムが使わなくなったメモリ領域 (ごみ) を自動的に回収して再利用可
能にする仕組みである．GC の動作は，まずメモリ領域上のごみを発見して，見つけたごみ
を回収する．そしてプログラムが再度利用できるようにし，再びプログラムからの要求に応
じてメモリを割り当てる．これらの機能を持ったプログラムが GC である．
通常 GC はを持つシステムでは，プログラムの開始時にシステムが必要なメモリ領域を予
め確保しておき，実行中には確保した領域内にデータを配置する．このとき，メモリ領域上
に予め確保しておく領域をヒープ領域と呼ぶ．また，GC によって操作されるこれらのデー
タをオブジェクトと呼ぶ．ヒープ領域に配置されたオブジェクトは GC で操作するため，配
置するオブジェクトにはオブジェクト自体の情報を持たせる必要がある．そのため，オブ
ジェクトにはヘッダを付与して，オブジェクトの情報を保持する．ヘッダに付与される情報
は，主にオブジェクトのサイズやオブジェクトの種類である．また，オブジェクトはプログ
ラムを実行する際に必要なデータを保持している．これらを保持している場所をフィールド
と呼び，プログラムは必要に応じてオブジェクトのフィールドにアクセスしてデータを参照
– 13 –
3.1 GC の概要
したり書き換えたりする．プログラムは一般的に，オブジェクトを参照で連結したデータ構
造を作り，その参照がポインタで実現されている．そのため，GC はそれを利用してポイン
タを辿り，オブジェクトからさらに別のオブジェクトを探索する．整数などのポインタでは
ないものを非ポインタと呼ぶことにする．非ポインタに対しては GC は何も操作しない．
ヒープ領域に割り当てられたオブジェクトのうち，プログラムから参照できて，GC 以降
もプログラム中で使われる可能性のあるオブジェクトを生きているオブジェクト，プログラ
ムからはどうやっても参照できないオブジェクトを死んでいるオブジェクトと呼ぶ．プログ
ラムからどうやっても参照できないため，死んでいるオブジェクトはごみと呼ばれている．
プログラムからの参照の有無でオブジェクトが生きているか死んでいるかを判断するた
め，GC はプログラムからの参照の有無を判断する必要がある．プログラムが持つ参照の元
となる部分をルートと呼ぶ．例えば，グローバル変数が指す先はプログラムから参照可能な
ため，グローバル変数はルートとなる．
プログラムの実行中に GC が起こるとプログラムは処理を停止して GC を実行する．そ
のため，図 3.1 のようにプログラムの実行ではプログラムの本来の処理の合間にメモリの割
り当てとごみの回収を行っていることになる [6]．
図 3.1 GC を持つシステムでのプログラムの実行
– 14 –
3.2 GC アルゴリズム
3.2
GC アルゴリズム
GC は，様々なアルゴリズムのもと作られている．様々なアルゴリズムが存在するが，中
心となっているアルゴリズムは，以下の 3 つのアルゴリズムである．他のアルゴリズムはこ
の 3 つのアルゴリズムを組み合わせたり，応用してできたアルゴリズムしか存在しない．
• マークスイープ GC
• 参照カウント
• コピー GC
GC アルゴリズムは，それぞれのアルゴリズムによって特徴が異なっており，様々なメリッ
トやデメリットを持つ．例えば，マークスイープ GC は，実装が簡単でヒープ領域の使用効
率が良いがメモリ割り当てが遅く，参照カウントは GC が発生してプログラムが停止してい
る時間が短いが実装が複雑でヒープ領域の使用効率が悪い．また，コピー GC は GC1 回に
かかる時間は比較的短いがヒープ領域の使用効率が悪い GC アルゴリズムである．このよ
うにアルゴリズムによって特徴が異なるため，GC アルゴリズムはプログラムに適したもの
を選択する必要がある．本研究では，比較的実装が簡単なため，マークスイープ GC を実装
する．
3.3
BoehmGC
SSJSVM は，C 言語用の GC ライブラリである BoehmGC を使って GC を実装してい
る．BoehmGC は保守的 GC という手法で設計されている．保守的 GC とは，ルートから
オブジェクトを指している値が，ポインタであっても，ポインタでは無いポインタに似た整
数値であっても，生きているオブジェクトとみなす手法で設計された GC である．通常の
GC はオブジェクトをポインタで辿って探すため，非ポインタに対しては何もしない．しか
し例えば，たまたまヒープ領域上のオブジェクトのアドレスと同じ整数値が辿っているルー
トやオブジェクトのフィールド中に存在した場合に，GC はそれを非ポインタであるかポイ
– 15 –
3.4 SSJSVM における GC の検証
ンタであるかを判別することができない．この場合に，ポインタのように見える非ポインタ
が指すオブジェクトも生きているオブジェクトとみなす．このように，ポインタの可能性の
ある値はすべてポインタとみなすので安全に処理を行うことができる．
保守的 GC はポインタを正確に判別することができないため，ヒープ領域上のオブジェク
トを移動させる処理をする GC アルゴリズムは利用できない．例えば，オブジェクトを移動
させる場合は移動前のオブジェクトを指しているポインタを移動先のオブジェクトに指し変
えなければならない．しかし，ポインタと非ポインタを判別することができない保守的 GC
がポインタの値を書き換えると，非ポインタの値を書き換えてしまう恐れがある．そのた
め，保守的 GC はオブジェクトの移動ができない．そこで BoehmGC ではオブジェクトを
移動する処理の無い GC アルゴリズムである，マークスイープ GC が用いられている．
保守的 GC のメリットとしては，プログラムが GC に依存しないため，GC の実装が楽で
あるという点である．そのため，様々なソフトウェアに対して安全に処理を行うことができ
る．しかし，上述したように保守的 GC ではオブジェクトを移動させる処理のある GC ア
ルゴリズムが使えないため，利用できる GC アルゴリズムが限定的になる．そのため，高
速な GC アルゴリズムを適用することができないので，BoehmGC は遅いと考える．特に，
メモリを多く使う処理を行う場合に，専用の GC を備えた他のサーバサイド JavaScript 処
理系に比べて SSJSVM は処理速度が遅くなると考えられる．そこで本研究では，SSJSVM
が本当に遅いかどうか検証する．
3.4
3.4.1
SSJSVM における GC の検証
検証方法
SSJSVM は保守的 GC を利用しているため，GC が遅いと考えられる．なので，本当に
遅いのか検証を行って確かめる．検証では，GC にかかっている時間とメモリ割り当てにか
かる時間を調べたいので，以下の 3 種類の SSJSVM 処理系を用いてプログラムの実行時間
を比較する．
– 16 –
3.4 SSJSVM における GC の検証
• BoehmGC を利用した通常の SSJSVM(BoehmGC 処理系)
• ごみ回収を行わない malloc によるメモリ割り当てを行う SSJSVM(malloc 処理系)
• ごみ回収を行わないが高速なメモリ割り当てを実装した SSJSVM(quick 処理系)
malloc 処理系は，メモリが必要になる度に C 言語の標準ライブラリ関数である malloc 関
数を用いてメモリの割り当てを行う．ただし，ごみの回収を行わないため利用可能なメモ
リ領域以上のメモリ領域を割り当てるプログラムは動作しない．quick 処理系は，最初に
malloc 関数で 2GB 分のメモリ領域を確保し，確保したメモリを端から順に利用すること
で高速なメモリ割り当てを行う処理系である．図 3.2 では，確保した 2GB のメモリ領域を
プログラムからの要求にしたがって，メモリ領域の端から順にメモリを割り当てている様
子を示している．malloc 処理系ではメモリが必要になる度に毎回 malloc 関数の呼び出し
によるメモリの確保を行っていたが，quick 処理系では malloc 関数の呼び出しによるメモ
リの確保を一回しか行わないため，メモリの確保にかかる時間が大幅に減ると考えられる．
quick 処理系も malloc 処理系と同じくごみの回収は行わない．これらの処理系を用いて，
GC が頻繁に起こるようにごみを大量に生成するプログラムを実行する．
BoehmGC 処理系と malloc 処理系はメモリ割り当ての方式が近いため，この 2 つの
処理系を比較することでごみ回収にかかった時間が推定できる．また，malloc 処理系と
quick 処理系はどちらもごみの回収は行わないが，メモリ割り当ての方式が異なるため，こ
の 2 つの処理系を比較することでメモリ割り当てにかかる時間が推定できる．
検証に用いたプログラムは，GC を頻繁に起こさせるために死んでいるオブジェクトを多
数生成するプログラムである．このプログラムを 3 つの処理系で実行して比較した．また，
検証を行った環境は，Ubuntu14.04，Intel Core i5 3.3GHZ，gcc 4.8.4 である．
3.4.2
検証結果
検証結果のグラフを図 3.3 に示す．このグラフは縦軸をプログラムの実行時間，横軸を
生成したごみの数としており，3 種類の処理系の実行時間を表したグラフである．このグラ
– 17 –
3.4 SSJSVM における GC の検証
図 3.2
quick 処理系のメモリ割り当て
フの malloc 処理系と quick 処理系は共にごみ回収を行わずに，メモリ割り当ての方法が
違うことから，実行時間の差はメモリの割り当てにかかった時間であることがわかる．ま
た，BoehmGC 処理系と malloc 処理系は，ごみの回収を行っているか行っていないか
の違いなので，実行時間の差からごみ回収にかかった時間がわかる．これらの結果から，
BoehmGC はメモリの割り当てにかかった時間もごみの回収にかかった時間も遅いので，
BoehmGC は処理が遅いということがわかる．
また，一般的なサーバサイド JavaScript との差を比べるために，V8 JavaScript エンジン
で動作するサーバサイド JavaScript である Node.js との比較を行った．その結果のグラフ
を図 3.4 に示す．このグラフは縦軸をプログラムの実行時間，横軸を生成したごみの数とし
ており，図 3.3 のグラフに Node.js での実行結果を加えたものである．グラフより，Node.js
は GC を含んでいるにもかかわらず高速に処理をしているということがわかる．この結果か
ら，Node.js の GC に比べて BoehmGC は遅いということがわかった．
以上の検証により，BoehmGC はごみ回収もメモリの割り当ても遅いということがわかっ
た．また，専用の GC を持つ Node.js は BoehmGC に比べて速いということがわかったた
め，SSJSVM 専用の GC を実装することで高速化の余地があることがわかった．
– 18 –
3.4 SSJSVM における GC の検証
図 3.3
メモリを多く消費して頻繁に GC が起こるプログラムの実行時間の比較
図 3.4 3 種類の SSJSVM 処理系と Node.js の実行時間の比較
– 19 –
第4章
マークスイープ GC の実装
第 3 章では，BoehmGC が使われている既存の SSJSVM の GC の性能を調査した．その
結果 BoehmGC は遅いことがわかった．BoehmGC は保守的 GC であるため，ヒープ領域
上のオブジェクトを移動させるような処理はできない．そのため，高速な GC アルゴリズ
ムを適用させることができず処理が遅い．そこで本研究では，SSJSVM に保守的では無い
マークスイープ GC を実装する．マークスイープ GC を選んだ理由は，GC アルゴリズムの
中でも比較的実装が簡単であることである．
4.1
マークスイープ GC
マークスイープ GC とはマークフェーズとスイープフェーズの 2 つのステップから成る
GC アルゴリズムである．マークフェーズではヒープ領域上の全ての生きているオブジェク
トに生きていることを示すマークをつける．スイープフェーズは，ヒープ領域上のマークの
ついていないオブジェクトを全て回収する．回収したメモリ領域は，フリーリストと呼ばれ
る空き領域のリストに繋げられる．プログラムからメモリが要求される度に，フリーリスト
からメモリを割り当てる．以下で詳しく説明する．
4.1.1
マークフェーズ
マークフェーズでは，まず最初にアプリケーションから直接参照されているヒープ領域上
のオブジェクトのヘッダにマークをつける．このマークをつけたオブジェクトは生きている
オブジェクトであり，ここから辿れる全てのオブジェクトにも再帰的にマークをつけていく．
– 20 –
4.1 マークスイープ GC
図 4.1 マークフェーズ時のヒープ領域
こうすることで，メモリ領域上の全ての生きているオブジェクトにマークをつけることが可
能となる．再帰的に全てのオブジェクトを辿る際に，マーク済みのオブジェクトに辿り着い
た場合には，そこから先のオブジェクトは辿らないようにすることで繰り返し辿らないよう
にする．
マークフェーズ時におけるメモリ領域の状態を図 4.1 に示す．この図は，プログラムから
参照されるヒープ領域上に割り当てられたオブジェクトのヘッダにマークをつけている様子
を表している．プログラムから直接参照されるオブジェクトだけではなく，オブジェクトか
ら参照されているオブジェクトにもマークしており，プログラムから辿れる全てのオブジェ
クトにマークをつけている．
4.1.2
スイープフェーズ
スイープフェーズでは，まず最初にヒープ領域の一番端のオブジェクトから順に全てのオ
ブジェクトのヘッダをスキャンしていく．そして，ヘッダにマークの付いていないオブジェ
クトを発見すると，回収して再利用可能な空き領域にする．オブジェクトのヘッダにマーク
が付いている場合は，マークを外して次の GC に備える．回収されてできたヒープ領域上の
空き領域は，フリーリストに繋いで確保しておくことで，プログラムからのメモリ要求に備
– 21 –
4.2 設計
図 4.2
スイープフェーズ時のヒープ領域
える．
スイープフェーズ時におけるメモリ領域の状態を図 4.2 に示す．この図は，図 4.1 のマー
クフェーズ時にマークを付けなかったヒープ領域上のオブジェクトを全て回収し，再度利用
可能にするためにフリーリストに繋いだ図である．
4.1.3
メモリ割り当て
プログラムからのメモリの要求に応じるために，ヒープ領域上の空き領域を繋げて確保し
ているリストをフリーリストと呼ぶ．プログラムからメモリの要求があれば，フリーリスト
の先頭から順に必要なサイズ以上の空き領域を探して，空き領域が見つかればその空き領域
をプログラムに渡す．この時，必要なサイズ以上の空き領域が見つからなかった場合は GC
を発生させて，新たな空き領域をフリーリストに確保する．それでも見つからない場合はプ
ログラムは停止する．
4.2
設計
本研究にて実装するマークスイープ GC の概要を説明する．マークスイープ GC に必要
なフリーリストの構造や，GC が発生するタイミング，マークフェーズとスイープフェーズ
– 22 –
4.2 設計
におけるプログラムの動作について示す．
4.2.1
フリーリスト
ヒープ領域上の空き領域には，空き領域のサイズとフリーリストの次の空き領域の先頭ア
ドレスを記憶させておくヘッダを付与する．ヘッダはオブジェクトのヘッダと同じ構造にし
ておく，ヘッダを付与するのは，スイープフェーズの処理で空き領域を見分けられるように
するためである．このときのフリーリストを図 4.3 に示す．図は，ヒープ領域上の空き領域
にヘッダを付与し，ヘッダは空き領域のサイズと次の空き領域を指すアドレスを持つことを
表している．
プログラムからメモリの要求があった場合はフリーリストの先頭の空き領域から順にリ
ストを辿り，要求されたサイズ以上のサイズの空き領域を探す．空き領域が見つかれば，そ
こから必要な大きさの領域を切り取ってオブジェクトを割り当てる．切り取られて余った領
域は再びフリーリストに繋ぐことでヒープ領域の節約をする．ただし，先程も述べたよう
にフリーリストにはヘッダを付与するので，空き領域をフリーリストに繋ぐためには，最低
16Byte の領域が必要である．そのため，切り取られて余った領域が 16Byte に満たない場
合は，その領域にはオブジェクトを割り当てない．ゆえに，プログラムからの要求で空き領
域を割り当てる条件は，要求されたサイズより空き領域が 16Byte 以上大きい場合か，要求
されたサイズと全く同じサイズの空き領域であることである．
図 4.3 ヒープ領域上のフリーリストの様子
– 23 –
4.2 設計
4.2.2
GC のタイミング
本研究では，オブジェクトの作成に必要なメモリの割り当ては全てフリーリストから探し
て割り当てている．フリーリストに要求されたメモリサイズ以上の空き領域が存在しなかっ
た時に GC を行う．
4.2.3
マークフェーズ
本研究で扱うオブジェクトは，64bit のヘッダを保持している．オブジェクトのヘッダの
64bit のうち上位 32bit でオブジェクトのサイズ，下位 3bit でオブジェクトの型を表してい
る．しかし，現在ではヘッダの 64bit 中 4bit 目から 32bit 目までは利用されていない．そこ
で，本研究ではヘッダの下から 5bit 目をマークビットとし，この bit が 0 なのか 1 なのか
を見て判断する．マークビットが 0 であればマークされていない死んでいるオブジェクトで
あり，1 であればマークされている生きているオブジェクトである．
マークフェーズでは，ルートから指されているオブジェクトと，そこから辿れる全てのオ
ブジェクトに再帰的にマークをしていく．生きているオブジェクトを発見したら，そのオブ
ジェクトのヘッダに生きている証のマークを付けるする．SSJSVM において，ルートとな
る場所を以下に示す．
• JavaScript のグローバル変数
• JavaScript のローカル変数
• C 言語のグローバル変数
• C 言語のローカル変数
• 関数呼び出しの返り値を格納するレジスタ
• 汎用レジスタ
• 文字列テーブル
ルートから指されたオブジェクトが見つかったら，そこから再帰的にオブジェクトを辿ら
– 24 –
4.2 設計
なければならない．しかし，オブジェクトのデータ型によって，オブジェクトから辿る先が
異なってくる．そこで，以下では第 2 章の表 2.2 で示したデータ型のそれぞれの辿り方を
示す．
OBJECT 型
OBJECT 型のオブジェクトは，ヘッダ以外に 4 つのプロパティを保持している．それは，
配列にどこまでデータが格納されているかを表す値，配列の限界の長さの値，ハッシュテー
ブル，データを格納する配列の 4 種類である．このうちオブジェクトから辿る必要のあるプ
ロパティはデータを格納する配列である．そして，配列に格納されているデータから指され
ているオブジェクトを辿る．図 4.4 は OBJECT 型オブジェクトの構造を示しており，prop
プロパティで指された配列を探索する．この図では，header がヘッダ，numberOfProp が
配列にどこまでデータが格納されているかを表す値，limitOfProp が配列の限界の長さ，
map がハッシュテーブルを示している．
図 4.4 OBJECT 型オブジェクトの構造
– 25 –
4.2 設計
図 4.5 STRING 型，FLONUM 型オブジェクトの構造
STRING 型，FLONUM 型
STRING 型と FLONUM 型の 2 つのオブジェクトは，それぞれ文字列と浮動小数点を保
持するだけのオブジェクトであるため，このオブジェクトから先に辿るオブジェクトは存在
しない．そのため，この 2 つの型のオブジェクトが見つかった場合はそこから先は辿らない．
図 4.5 は STRING 型，FLONUM 型オブジェクトの構造を示している．図のように，ヘッ
ダと値を保存するプロパティの 2 つのプロパティで構成されているため，これ以上辿る配列
は存在しない．
ARRAY 型
ARRAY 型のオブジェクトは，他のデータ型のオブジェクトと違って，OBJECT 型と共
通のプロパティの配列以外にも辿らなければならないフィールドがある．ARRAY 型のオ
ブジェクトは配列を扱う構造体であるため，配列の中身も辿らなければならない．プログ
ラムから指されている ARRAY 型オブジェクトの構造を図 4.6 に示す．ARRAY 型のオブ
ジェクトは OBJECT 型同様に prop プロパティで指された配列の以外にも，ARRAY 型オ
ブジェクトが表している配列本体である body プロパティで指された配列も探索する必要が
ある．
– 26 –
4.2 設計
図 4.6
ARRAY 型オブジェクトの構造
その他の型
上記に上げた OBJECT 型，STRING 型，FLONUM 型，ARRAY 型の 4 つオブジェク
ト以外のデータ型のオブジェクトについては，オブジェクトの辿り方は OBJECT 型と同じ
である．なぜなら 4 つのオブジェクト以外のデータ型は全て OBJECT 型と同じデータ構造
を持っているため，その OBJECT 型のデータ構造から他のオブジェクトを辿れるためであ
る．そのため，この 4 つの型以外の型は全て OBJECT 型と同じ辿り方で再帰的にオブジェ
クトを辿ることができる．
4.2.4
スイープフェーズ
本研究では，ヒープ領域上にあるオブジェクトとフリーリストに繋がれた空き領域は共に
それぞれの領域のサイズを記憶しているヘッダを持っている．そのため，ヒープ領域の先頭
から，ヘッダに記憶されている領域サイズずつ移動することで全てのオブジェクトまたは空
き領域へアクセスすることができる．
スイープフェーズで行う動作を以下に示す．まず，ヒープ領域の一番端のオブジェクトか
– 27 –
4.3 実装
らヘッダに記述されたサイズごとにヒープ領域を移動して全てのオブジェクトまたは空き領
域を順に辿る．このとき，オブジェクトのヘッダのマークビットが 1 になっていれば，その
オブジェクトは生きているため，そのオブジェクトのマークビットを 0 にして次のオブジェ
クトへ移る．オブジェクトのビットマークが 0 の場合，もしくは元々フリーリストに繋がれ
ていた空き領域の場合 (ヘッダのマークビットは 0) は，どちらも空き領域なのでフリーリス
トのヘッダを付与してフリーリストに繋ぐ．ただし，マークビットが 0 のオブジェクトまた
は空き領域が連続して続く場合は，連続して続いている領域を合計して記憶しておき，次に
マークビットが 1 のオブジェクトが現れたときに，合計した領域にフリーリストのヘッダを
付与してフリーリストに繋ぐ．このようにヒープ領域をスキャンする中で，生きているオブ
ジェクトどうしの間の領域をフリーリストに繋いでいくことで死んでいるオブジェクトを回
収する．
動作の例を図 4.7 で示す．この図では，スイープフェーズ前の死んでいるオブジェクトと
フリーリストに繋がれた空き領域が，スイープフェーズ後には全てフリーリストに繋がれて
いる．また，死んでいるオブジェクトとフリーリストに繋がれた空き領域が連続していた領
域は，スイープフェーズ後にはまとめて大きなサイズの空き領域としてフリーリストに繋が
れている．
本研究ではスイープフェーズに入る度に新たに 1 からフリーリストを作りなおすことでフ
リーリストを作成する．こうすることで，GC が進む度にフリーリストが細分化されてしま
う問題を解決しながら，フリーリストを作成することができる．
4.3
4.3.1
実装
GC の対象
本研究では，GC によってごみ回収を行う対象を，SSJSVM 内で多数生成される 11 種
類のデータ型を持つオブジェクトとする．SSJSVM 内では C 言語の標準ライブラリである
malloc 関数を用いて至る所でメモリの割り当てを行っている．そのため，malloc 関数を用
– 28 –
4.3 実装
図 4.7
スイープフェーズの動作の例
いて割り当てたメモリ領域は GC の対象になるが，今回は時間の都合でオブジェクトのみを
GC の対象にする．例えば，オブジェクトは必要なデータをオブジェクトの持つ配列に格納
して保存しており，その配列にアクセスするためにハッシュテーブルを用いて必要なデータ
が格納されている場所を探してアクセスする．そのため，オブジェクトにはハッシュテーブ
ルが必要なので，オブジェクトが作られる度にハッシュテーブルも malloc 関数を用いて作
成される．しかし，今回はオブジェクトは GC の対象とするが，ハッシュテーブルについて
は GC の対象外としている．
4.3.2
メモリの割り当て
本研究では，最初のオブジェクトが作成される前に，一度だけ任意のサイズのヒープ領域
を確保し，その確保したヒープ領域上にオブジェクトを配置していくことでメモリをオブ
ジェクトに割り当てる．今回実装した GC では，プログラマが自由にヒープ領域のサイズを
決めることができるようになっている．最初にヒープ領域を確保する際は，確保した領域が
フリーリストに繋げられて空き領域となる．
– 29 –
4.3 実装
プログラムからの要求がある度に，フリーリストを端から順に探索していくので，常にフ
リーリストの先頭を指すアドレスを確保している．
4.3.3
マークの付与
本研究では，マークフェーズ時には，マークの付与を行う markObject 関数にルートから
直接参照されているオブジェクトを渡すことで，渡されたオブジェクトから再帰的に生きて
いるオブジェクトをマークするようになっている．そのため，ルートから直接参照されてい
る全てのオブジェクトを markObject 関数に渡す必要がある．
ソースコード 4.1 にて markObject 関数の擬似コードを示す. markObject 関数内で
は，まずソースコードの 2 行目で渡された JSValue 型の値がオブジェクトを指すポインタ
なのかどうかを調べる．equalTag 関数は JSValue 型の値の種類を判別する関数である．
JSValue 型の値は，データの格納している場所を指しており，下位 3bit でデータの種類を
表す型を保持している．そのため，下位 3 ビットを調べて，オブジェクトを指すポインタ
かどうかを判別する．また，4 行目ではすでにマークされているオブジェクトかどうかも
調べる．markCheck 関数は引数のオブジェクトにマークがあるかどうかを判別する関数で
ある．もし，オブジェクトでは無い場合や，すでにマーク済みのオブジェクトである場合
は，その時点でそのオブジェクトには何も操作しない．そして，マークの付いていない正し
いオブジェクトである場合は，ソースコードの 7 行目でオブジェクトにマークを付与する．
objectMark 関数は引数のオブジェクトにマークを付与する関数である．マークを付与する
というのは，オブジェクトのヘッダの下から 5bit 目のマークビットを 1 にするということで
ある．マークを付与したオブジェクトは，さらにそこから辿れるオブジェクトを探す必要が
あるので，ソースコードの 8 行目でオブジェクトのヘッダを調べてオブジェクトのデータ型
を調べる．getObjectHeader 関数はオブジェクトのデータ型を調べる関数である．オブジェ
クトのデータ型にしたがってそこから辿れるオブジェクトを見つけ，それを makrObject 関
数に渡すことで再帰的に処理していく．STRING 型と FLONUM 型はこれ以上オブジェク
トを辿らない．ARRAY 型は prop 配列と body 配列の 2 種類の配列のプロパティを辿る．
– 30 –
4.3 実装
STRING 型，FLONUM 型，ARRAY 型以外のデータ型のオブジェクトは OBJECT 型と
同じ配列プロパティである body 配列を辿る．オブジェクトの持つ numberOfProp プロパ
ティには body 配列の長さの値が格納されており，propCount 変数に格納する．格納された
値にしたがって配列プロパティを辿る．また，ARRAY 型のオブジェクトが持つ length プ
ロパティは prop 配列の配列の長さが格納されており，その値にしたがって配列プロパティ
を辿る．
– 31 –
4.3 実装
ソースコード 4.1 markObject 関数の擬似コード
1:
static void markObject(JSValue objp) {
2:
// オブジェクトを指すポインタか判別
if((!equalTag(objp, 0b000)) | (objp == 0))
3:
4:
return; // オブジェクトを指すポインタでなければ何もしない
5:
if(!markCheck(objp)) // オブジェクにマークがあるかどうか判別
return; // オブジェクトにマークがあれば何もしない
6:
7:
int i, propCount;
8:
objectMark(headNum); // マークビットを 1にする
9:
switch(getObjectHeader(objp)) { // オブジェクトの型を調べて型ごとに処理
10:
case HTAG STRING: break; // STRING 型はこれ以上辿らない
11:
case HTAG FLONUM: break; // FLONUM 型はこれ以上辿らない
12:
case HTAG ARRAY: // ARRAY 型は 2 つの配列を辿る
13:
propCount = objp−>numberOfProp; // 配列の長さを取得
14:
for(i = 0; i <= propCount; i++) { // ARRAY 型の持つ配列プロパティを辿る
markObject(objp−>prop[i]); // markObject 関数を呼び出す
15:
16:
}
17:
for(i = 0; i < objp−>length; i++) { // OBJECT 型の持つ配列プロパティを辿る
markObject(objp−>body[i]); // markObject 関数を呼び出す
18:
19:
}
20:
break;
default: //残りの型はOBJECT 型の配列を辿る
21:
22:
propCount = objp−>numberOfProp; // 配列の長さを取得
23:
for(i = 0; i <= propCount; i++) { //OBJECT 型の持つ配列プロパティを辿る
markObject(objp−>prop[i]); // markObject 関数を呼び出す
24:
25:
}
26:
break;
}
27:
28:
}
– 32 –
4.3 実装
4.3.4
オブジェクトの辿り方
SSJSVM のそれぞれのルートから直接参照されているオブジェクトの辿り方を以下に
示す．
JavaScript のグローバル変数
JavaScript のグローバル変数は，第 2 章の 2.2.1 で述べたようにグローバルオブジェクト
に格納されている．そのため，グローバルオブジェクトへのポインタを markObject に渡す
だけでよい．
JavaScript のローカル変数
JavaScript のローカル変数は，第 2 章で述べた関数フレーム内に保存されている．その
ため，制御スタックから指されている全ての関数フレームを辿ることで JavaScrip のローカ
ル変数を辿ることができる．
C 言語のグローバル変数
C 言語のグローバル変数は，SSJSVM のプログラム内で宣言されているグローバル変数
である．オブジェクトを指す変数の型は JSValue 型であるため，JSValue 型で宣言されて
いる全てのグローバル変数を辿る．
C 言語のローカル変数
GC は SSJSVM の実行中に，どこで発生するかはわからない．そのため，関数内で GC
が発生した場合は，その関数内で宣言されたローカル変数が指すオブジェクトもマークする
必要がある．また，関数内で関数が呼び出された先で GC が起こった場合は，呼び出し先の
– 33 –
4.3 実装
図 4.8 C 言語のローカル変数を保存するスタック
関数内のローカル変数だけではなく，呼び出し元の関数内のローカル変数もマークしなけれ
ばならない．そのため，スタックを用いてローカル変数を保存していく．保存する必要のあ
るローカル変数は，グローバル変数同様に JSValue 型の変数である．例えば，関数 f の中
で関数 g が呼び出された場合は，図 4.8 のように下から関数 f のローカル変数，関数 f が格
納されている場所を示す値，関数 g のローカル変数というふうにスタックに積まれていく．
関数 g から抜け出す際は，関数 f が格納されている場所を示す値にしたがって，スタックを
操作することで関数 f に戻る．
関数呼び出しの返り値を格納するレジスタ
関数呼び出しの返り値が格納されているレジスタは，表 2.1 の a レジスタである．特殊レ
ジスタは第 2 章で述べたコンテキスト構造体から参照することができるため，コンテキスト
から特殊レジスタが持つオブジェクトにも辿ることができる．
汎用レジスタ
制御スタックに積まれている汎用レジスタはオブジェクトを指している．そのため，制御
スタックにある汎用レジスタが指すオブジェクトを辿る必要がある．
– 34 –
4.3 実装
文字列テーブル
JavaScript プログラム内の関数に対応するバイトコードの命令列が関数テーブルに格納
されている．関数テーブルにバイトコードの命令列を読み込ませる際に，文字列テーブルに
文字列のデータを読み込むため，文字列テーブルにある STRING 型のオブジェクトもマー
クをする必要がある．これは，コンテキストから参照されている命令テーブルから辿ること
ができる．
– 35 –
第5章
評価
第 5 章では，本研究の GC を持つ SSJSVM について既存の SSJSVM とオブジェクトを
多数生成するプログラムの実行時間を比較した．その結果，本研究の GC を持つ SSJSVM
のほうが既存の SSJSVM より遅かった．その原因について考察し，本研究の GC を高速化
する方法について検討する．
5.1
検証方法
本研究では，以下の２つの点について BoehmGC を利用する既存の SSJSVM とマークス
イープ GC を実装した新たな SSJSVM の 2 つの処理系を比較して検証する．また，検証を
行う際は，GC を公平に動かすために，本研究の GC を持つ SSJSVM のヒープ領域の大き
さを固定する．検証を行った環境は，Ubuntu14.04，Intel Core i5 3.3GHZ，gcc 4.8.4 で
ある．
• ごみのオブジェクトを多数生成するプログラムの実行時間
• マークスイープ GC を実装した SSJSVM のプログラムの実行時間の内訳
最初にごみのオブジェクトを多数生成するプログラムの実行時間を検証する．BoehmGC で
は任意のヒープ領域の大きさを指定できない．そのため，本研究の GC を持つ SSJSVM は，
BoehmGC で利用されたヒープ領域の大きさに合わせてヒープ領域の大きさを固定する．今
回はヒープサイズを，BoehmGC に合わせて 479232Byte とする．検証に用いるプログラ
ムをソースコード 5.1 に示す．このプログラムは，外側 for ループで生成したオブジェクト
– 36 –
5.1 検証方法
をグローバル変数に格納し，内側 for ループで次々と新しいオブジェクトを生成するプログ
ラムである．こうすることで，外側 for ループで生きているオブジェクトを，内側 for ルー
プで死んでいるオブジェクトを多数生成するオブジェクトである．また，ヒープ領域を生き
ているオブジェクトと死んでいるオブジェクトで断片的に利用する．このプログラムの内側
for ループの回数を 1000 回から 6000 回まで 1000 回ずつ増やして検証を行う．ループの回
数を増やす度に，ごみのオブジェクトが生成される回数が増える．
続いて，マークスイープ GC を実装した SSJSVM のプログラムの実行時間の内訳を調査
する．今回調査する実行時間の内訳は，プログラムの全実行時間，メモリ割り当てと GC
の時間，メモリ割り当ての時間である．検証に用いるプログラムはソースコード 5.1 であ
る．ただし，内側 for ループを 5000 回に固定する．検証のために，本研究の GC を持つ
SSJSVM のヒープ領域を，50KByte から 850KByte まで 200KByte ずつ増やして検証す
る．また，ヒープ領域を 479232Byte に固定した先ほど検証に用いた既存の SSJSVM の実
行時間も示す．
今回の研究では，SSJSVM 内で生成するオブジェクトに対応する GC を実装した．その
ため，既存の SSJSVM はオブジェクトのメモリ割り当てを BoehmGC で処理をして，そ
の他のメモリが必要な処理は malloc 関数を用いてメモリ割り当てを行う．また，本研究の
GC を持つ SSJSVM についても，オブジェクトのメモリ割り当て以外は全て malloc 関数
を用いてメモリ割り当てを行う．オブジェクトの割り当てに使った全てのメモリ領域の大き
さ，malloc 関数を用いて確保した全てのメモリ領域の大きさの関係を図 5.1 に示す．この
図は，縦軸が利用したメモリ領域の大きさで横軸がソースコード 5.1 の内側 for ループの回
数である．また，この図で GC が発生した時に生きているオブジェクトが使用しているメ
モリ領域の大きさは 8KByte ほどである．さらに，オブジェクトの割り当てが起きた回数と
malloc 関数を用いてメモリ領域を確保した回数を図 5.2 に示す．
– 37 –
5.1 検証方法
ソースコード 5.1 JavaScript のソースコードの例
1:
var Cell = function(val, next) {
2:
this.val = val;
3:
this.next = next;
4:
}
5:
var head = new Cell(0, null);
6:
for (i = 0; i < 10; i++) {
7:
head = new Cell(i, head);
8:
for (j = 0; j < N; j++)
new Cell(0, null);
9:
10:
}
図 5.1
オブジェクトの割り当てと malloc 関数で使用したメモリ領域の大きさ
– 38 –
5.2 検証結果
図 5.2
5.2
オブジェクトの割り当てと malloc 関数でのメモリ割り当ての回数
検証結果
ごみのオブジェクトを多数生成するプログラムを 2 つの処理系で比較した結果を図 5.3
に示す．この図では，青色の線が既存の SSJSVM，オレンジ色の線が本研究の GC を持
つ SSJSVM である．図より，本研究の GC を持つ SSJSVM のほうが遅いということがわ
かる．
本研究の GC を持つ SSJSVM の，実行時にかかる全実行時間，メモリ割り当てと GC
の時間，メモリ割り当ての時間，さらに既存の SSJSVM での実行時間をグラフにしたもの
を図 5.4 に示す．この図では，青色の線が本研究の GC を持つ SSJSVM の全実行時間，オ
レンジ色の線がメモリ割り当てと GC の時間，灰色の線がメモリ割り当て時間を示してい
る．また，緑色のバツ印は既存の SSJSVM を示している．緑色のバツ印が 1 点だけなのは，
BoehmGC ではヒープ領域の大きさを任意の大きさに固定できないためである．そのため，
BoehmGC で使われたヒープ領域の大きさから，本研究の GC を持つ SSJSVM のヒープ
領域の大きさを決めている．また，図 5.4 の実験に用いたプログラムを実行したときの，本
– 39 –
5.2 検証結果
研究の GC を持つ SSJSVM のヒープ領域の大きさに対する GC の回数を表 5.1 に示す．図
5.4 と表 5.1 より，メモリ割り当てと GC にかかった時間とメモリ割り当てにかかった時間
の差が小さいことがわかった．また，メモリ割り当ては GC よりも時間がかかっていること
がわかった．
図 5.3
本研究の GC を持つ SSJSVM と既存の SSJSVM の実行時間の比較
表 5.1 ヒープ領域の大きさに対する GC の回数
ヒープ領域の大きさ（KByte）
50
250
450
650
850
GC の回数
131
21
11
8
6
– 40 –
5.3 考察
図 5.4
5.3
本研究の GC を持つ SSJSVM の実行時間の内訳と既存の SSJSVM の実行時間の比較
考察
検証結果より，本研究の GC を持つ SSJSVM が既存の SSJSVM より遅いということが
わかった．GC の性能改善を狙って既存の SSJSVM に保守的ではないマークスイープ GC
を実装したが，既存の SSJSVM より実行時間が遅くなった．図 5.4 から，メモリ割り当て
と GC にかかった時間とメモリ割り当てにかかった時間の差は小さいのに対して，メモリ割
り当てにかかった時間は大きいことがわかる．そのため，メモリ割り当てに多くの時間がか
かってしまい遅くなったということがわかる．
本研究の GC のメモリ割り当ては，プログラムから要求されたメモリ領域以上の領域を，
フリーリストを先頭から探して割り当てる割り当て方式である．そのため，プログラムから
メモリの要求があれば，毎回フリーリストの先頭から必要な空き領域が見つかるまで探索し
ていくため，メモリ割り当てに時間がかかる．そこで，メモリ割り当てが起こる度に必要な
空き領域が見つかるまでフリーリストを辿った回数を調べた．図 5.5 は，オブジェクトにメ
モリを割り当てるために，必要な空き領域が見つかるまでフリーリストを辿った回数を示し
– 41 –
5.3 考察
ている．縦軸はフリーリストを辿った回数，横軸はオブジェクトが割り当てられた回数を示
している．また，この図は本研究の GC を持つ SSJSVM のヒープ領域を 25KByte に固定
し，用いたプログラムはソースコード 5.1 の内側 for ループの回数を 20 回で固定したプロ
グラムである．この図では，合計 2 回 GC が起きている．1 回目の GC が起きるまでは，オ
ブジェクトのメモリ割り当ては常にフリーリストの先頭から行われるので，フリーリストを
辿る回数は 1 回である．1 回目の GC が起こると，必要な空き領域をフリーリストの先頭か
ら順に探して割り当てるので，オブジェクトのメモリ割り当てが行われる度にフリーリスト
を辿る回数が増えていく．そして，フリーリストに必要な空き領域が無ければ GC が再び発
生する．図では，オブジェクトを割り当てる回数が 550 回目ほどに達したときに 2 回目の
GC が発生しており，その時点でフリーリストが新しく作られるので，フリーリストを辿る
回数は一時的に減る．しかし，2 回目の GC が起きてから徐々にフリーリストを辿る回数が
増えていく．この図より，GC が起こるまでフリーリストを辿る回数が増えていくので，フ
リーリストによるメモリ割り当てに時間がかかることがわかる．
図 5.5
オブジェクトが割り当てられる度にフリーリストを辿る回数
– 42 –
5.4 今後の課題
5.4
今後の課題
本研究で実装した GC はメモリ割り当てが遅いことがわかった．そのため今後の課題とし
ては，メモリ割り当てを高速化することが挙げられる．そのための方法としては，フリーリ
ストによるメモリ割り当てを高速化する方法と高速なメモリ割り当てを行う世代別 GC を
実装する方法の 2 通りある．
例えば，フリーリストの高速化はフリーリストを空き領域の大きさによって分けて複数用
意する方法がある．似たような大きさの空き領域どうしを一つのフリーリストにして，空き
領域の大きさごとに異なったフリーリストを用意する．こうすることで，プログラムからメ
モリの要求があれば，要求された領域の大きさによって辿るフリーリストを変えることで，
フリーリストを辿る時間を短縮することができる [8]．
また，メモリ割り当てが高速な世代別 GC を実装する方法もある．世代別 GC とは，オブ
ジェクトに年齢の概念を付与し，多くのオブジェクトは生成されてすぐに死に，長く生き残
るオブジェクトは少ないということを前提に考えられたアルゴリズムである．具体的には，
GC が起こる度に生き残ったオブジェクトは中々死なないので，GC の頻度を下げ，逆に生
成されたばかりのオブジェクトに対しては頻繁に GC することで処理速度を向上させている
GC アルゴリズムである．また，世代別 GC はマークスイープ GC やコピー GC などの基
本アルゴリズムの GC を組み合わせて作られた GC アルゴリズムであり，メモリ割り当て
はメモリ割り当ての速い GC アルゴリズムを利用して，GC の処理にはヒープ領域の使用効
率の良い GC を利用する．このように場面によって適用する GC アルゴリズムを変えるこ
とで処理速度を向上させている．
– 43 –
第6章
関連研究
GC のアルゴリズムは，50 年以上昔から長きに渡って研究が続けられている．長く研究さ
れている分野なので，GC のアルゴリズムには様々なものが存在する．本研究で扱ったマー
クスイープ GC は世界で初めて生まれた GC アルゴリズムである．マークスイープ GC は，
プログラム中で使用されるオブジェクトが多ければ多いほど，マークにかかる時間が増えて
しまって効率が悪い．そのため，オブジェクトを多く生成するような大きなプログラムとは
相性が悪い．
Ruby というオブジェクト指向スクリプト言語も，以前のバージョンではマークスイープ
GC が実装されていた．しかし，オブジェクト指向スクリプト言語が大規模なプログラムで
も利用されはじめるようになって GC の遅さが顕著になった．そこで，マークスイープ GC
より格段に速い世代別 GC が実装された．Ruby の GC をマークスイープ GC から世代別
GC にすることで，GC の処理時間が最大で 92%，プログラムの実行時間が最大 50%短縮
したという結果が出ている [7]．この研究により，GC の処理時間が大幅に減っているので，
世代別 GC が有用であることがわかる．現在では，世代別 GC が実装されている処理系も
多くなっている．特に，V8 JavaScript エンジンで動作する Node.js などはこの世代別 GC
を採用しており，非常に高速な処理を行う処理系である．
– 44 –
第7章
おわりに
本研究では，既存の BoehmGC ライブラリを使った SSJSVM の GC の性能を調査し，
GC の性能が悪いことを突き止めた．さらに，GC の性能改善を狙って SSJSVM にマーク
スイープ GC を実装した．しかし，実装した GC は既存の SSJSVM の GC よりも遅いこと
がわかった．原因としては，本研究の GC ではメモリ割り当てに時間がかかっているためと
考えられる．
SSJSVM のプログラムの中では malloc 関数を用いて様々な所でメモリの割り当てを行っ
ている．しかし，今回はその中でも SSJSVM 内のオブジェクトを GC の対象としている．
そのため，今後 GC の対象になっていない部分についても GC の対象にすることで，より多
くのメモリ領域を使用するプログラムも実行することができるようになる．そのため，今後
の課題として，プログラムが利用する全てのメモリ領域を GC の対象とする必要がある．ま
た，今回の研究では GC の性能改善を狙って新たにマークスイープ GC を実装したが，本研
究の GC を持つ SSJSVM は，既存の BoehmGC を利用している SSJSVM より処理速度が
遅いことがわかった．原因は，本研究の GC を持つ SSJSVM のメモリ割り当てにかかる時
間が遅いことが挙げられる．そのため，フリーリストを高速化するか，メモリ割り当てを高
速に行う GC アルゴリズムを実装することで，性能を向上させることが今後の課題である．
– 45 –
謝辞
本研究を進めるに当たり，研究指導及び論文の執筆に関して，丁寧なご指導をいただいた
准教授の鵜川始陽先生に感謝の意を表し，厚く御礼申し上げます．また，研究活動だけでな
く，就職活動や研究室活動など様々なご指導を頂いたことを心より感謝致します．本論文の
副査として貴重なご意見をいただいた教授の福本昌弘先生，准教授の松崎公紀先生に感謝致
します．また，日々の研究室活動にて輪講などで様々な意見をいただいた鵜川研究室の皆様，
松崎研究室の皆様に感謝致します．
最後に，私の大学生活を支えてくれた両親にも感謝致します．また，大学生活にて 4 年間
お世話になりました情報学群の教職員の皆さんに感謝します．ありがとうございました．
– 46 –
参考文献
[1] 漆原 明博，岩崎 英哉，鵜川 始陽，サーバサイド向け JavaScript 処理系における Just
In Time コンパイラの実装，第 16 回プログラミング及びプログラミング言語ワーク
ショップ，2014．
[2] 中村 成洋，相川 光，ガベージコレクションのアルゴリズムと実装，秀和システム，
2010．
[3] NAKAMURA Minoru，
「Boehm GC ライブラリを使って C/C++ でもガベージ
コレクションしよう」，[online]http://www.nminoru.jp/~nminoru/programming/
boehm-gc2.html（参照 2015-7-26），2002．
[4] 漆原 明博，サーバサイド向け JavaScript 処理系における Just In Time コンパイラの
実装，電気通信大学大学院情報理工学研究科 情報・通信工学専攻修士論文，2014．
[5] 高田 祥，鵜川 始陽，中野 圭介，岩崎 英哉，JavaScript 仮想機械における Quickening
の効果，第 15 回プログラミング及びプログラミング言語ワークショップ，2013．
[6] Andrew W.Appel 著，神林 靖，滝本 宗宏 訳，最新コンパイラ構成技法，翔泳社，
2009．
[7] 木山 真人，オブジェクト指向スクリプト言語 Ruby への世代別ゴミ集めの実装と評価，
情報処理学会論文誌:プログラミング，Vol.43，No.SIG 1（PRO 13），2002．
[8] Richard Jones，Antony Hosking，Eliot Moss，The Garbage Collection Handbook，
Chapter 7，CRC press，2012．
– 47 –