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 SSJSV

学士学位論文

サーバサイド向け

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はメモリ割り当てが遅いことがわかった．

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 appli-cation 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 pro-grams．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 imple-mented 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．

第1章 はじめに 1 1.1 研究の背景 . . . 1 1.2 研究の目的 . . . 3 1.3 本研究の内容 . . . 3 第2章 SSJSVM 4 2.1 SSJSVMとは . . . 4 2.2 SSJSVMの構成 . . . 5 2.2.1 関数フレーム . . . 7 2.2.2 関数テーブル . . . 8 2.2.3 JSValue . . . 8 2.2.4 グローバルオブジェクト . . . 9 2.2.5 オブジェクトの構造 . . . 9 第3章 SSJSVMのGC 13 3.1 GCの概要 . . . 13 3.2 GCアルゴリズム . . . 15 3.3 BoehmGC . . . 15 3.4 SSJSVMにおけるGCの検証 . . . 16 3.4.1 検証方法 . . . 16 3.4.2 検証結果 . . . 17 第4章 マークスイープGCの実装 20 4.1 マークスイープGC . . . 20 4.1.1 マークフェーズ . . . 20

目次 4.1.2 スイープフェーズ . . . 21 4.1.3 メモリ割り当て . . . 22 4.2 設計. . . 22 4.2.1 フリーリスト . . . 23 4.2.2 GCのタイミング . . . 24 4.2.3 マークフェーズ . . . 24 OBJECT型 . . . 25 STRING型，FLONUM型. . . 26 ARRAY型 . . . 26 その他の型. . . 27 4.2.4 スイープフェーズ . . . 27 4.3 実装. . . 28 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 第5章 評価 36 5.1 検証方法 . . . 36

5.2 検証結果 . . . 39 5.3 考察. . . 41 5.4 今後の課題 . . . 43 第6章 関連研究 44 第7章 おわりに 45 謝辞 46 参考文献 47

図目次

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

5.4 本研究の GCを持つSSJSVMの実行時間の内訳と既存のSSJSVMの実行 時間の比較 . . . 41 5.5 オブジェクトが割り当てられる度にフリーリストを辿る回数. . . 42

表目次

2.1 特殊レジスタ . . . 7 2.2 オブジェクトのデータ型 . . . 10 5.1 ヒープ領域の大きさに対するGCの回数 . . . 40

はじめに

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 研究の背景 る．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を作成した場合に比べて性能が劣ると考えられる．

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章）．

第

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]．

ソースコード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のように制御スタックに積んで，関数ごと

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) { 7: return g(s + 1) 8: } 9: f(n);

図2.1 制御スタックの様子 表2.1 特殊レジスタ レジスタ名 レジスタが示すもの fp 実行中の関数のレジスタ群の開始位置を示す． sp 実行中の関数のレジスタ群の終点位置を示す． lp 実行中の関数の関数フレームの参照を示す． cf 関数テーブル内の実行中の関数が保持している命令列の参照を示す． pc 実行中のプログラムカウンタを示す． a 関数の返り値を示す．

2.2.1

関数フレーム

SSJSVMでは関数を呼び出す度に関数フレームが作成される．関数フレームは関数の引 数を格納するオブジェクトや，ローカル変数，関数が宣言された関数フレームに対する参照， 及び関数内で定義されたローカル変数のオブジェクトなどで構成される．関数フレームの例 を図2.2に示す．図2.2のprev frameは関数が宣言された場所の関数フレームを指す参照 である．また，augumentsは関数の引数を示しており，残りは関数内のローカル変数を格 納している．

2.2 SSJSVMの構成 図2.2 関数フレームの様子

2.2.2

関数テーブル

JavaScriptプログラム中の全ての関数はプログラム中で宣言された順に関数テーブルに 格納される．関数テーブル内のそれぞれの関数は，その関数に対応するバイトコードの命令 列を保持している．

2.2.3

JSValue

レジスタに格納する値は64bitのワードであり，真偽値や整数値はデータそのものを表し， オブジェクトや関数はデータを格納している場所を示す．データには，整数や真偽値，オブ ジェクトや関数など様々な型がある．そこで，データを示す64bitのワードの中で，それぞ れのデータの型とデータを示す場所を表している．データを指すアドレスは必ず8の倍数 となっているため，下位3bitは全て0である．そのため，データの型を下位3bitに埋め込 んで表し，それ以外でデータを指すアドレスを表している．下位3bitでデータの型を表す

ため，それぞれのデータの型には3bitで表現できるタグ値が対応付けられている．例えば， 整数(タグ値7)は上位61bitで符号付き61bit整数を表現して扱い，オブジェクトや関数な どはヒープ領域上の割り当てられた領域を指すポインタにタグ値が組み込まれて表現され る．このような，データを指す64bitのワードをSSJSVMではJSValueとして定義してい る．SSJSVMのプログラム中ではJSValue型の変数などにデータの参照が格納されている．

2.2.4

グローバルオブジェクト

JavaScriptプログラムの関数内のローカル変数など，関数に関するデータは関数フレー ムに保持されているのに対して，関数外のデータであるグローバル変数などは，グローバ ルオブジェクトと呼ばれる専用のオブジェクトのプロパティに保持される．SSJSVMには JavaScriptのプログラムのグローバル環境でのデータを保存しておくために，グローバル オブジェクトと呼ばれるオブジェクトが存在する．グローバルオブジェクトのプロパティに はJavaScriptプログラムのグローバル変数が宣言された順に格納されている． グローバルオブジェクトや特殊レジスタなど，JavaScriptのプログラムを実行するのに必 要な内部情報をまとめたものを実行コンテキストと呼び，SSJSVMではコンテキスト構造 体として用意されている．グローバルオブジェクトはこのコンテキスト構造体から参照され ている．

2.2.5

オブジェクトの構造

オブジェクトにも様々なデータ型がある．オブジェクトのデータ型は，全部で11種類存 在する．オブジェクトの全てのデータ型にはタグ値が対応付けされており，オブジェクトの データ型とタグ値の対応付けを表2.2に示す． 全てのオブジェクトはヘッダとデータを保持するプロパティを持っている．データ型に よって保持するプロパティが異なるため，オブジェクトの構造はそれぞれのデータ型によっ て異なっている．しかし，共通して全てのオブジェクトは必ずヘッダを保持している．オブ

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

型のプロパティとそれぞれのデータ型のプロパティを保持することができる構造になって いる． STRING型とFLONUM型のオブジェクトはそのままプロパティにアクセスすることで 必要なデータを得ることができる．それ以外の型のオブジェクトは，配列でデータを格納し ており，その配列にアクセスするためにはハッシュテーブルから必要なデータが格納されて いる場所を探してアクセスする．例としてグローバルオブジェクトにグローバル変数の値 が格納されている時のオブジェクトの様子を示す．このときの，グローバルオブジェクト， ハッシュテーブル，配列の関係を図2.6に示す．図では，mapから指されたハッシュテーブ ル上でグローバル変数aとグローバル変数aの値が格納されているprop配列の場所が対応 付けられている．また，グローバルオブジェクトはnumberOfProp，limitOfPropという 2つのプロパティを保持している．numberOfPropはprop配列の使われている長さを示し ており，limitOfPropはprop配列の長さの限界を示している[5]． 図2.3 STRING型とFLONUM型のオブジェクトの構造

2.2 SSJSVMの構成

図2.4 STRING型とFLONUM型以外のオブジェクトの構造

図2.5 オブジェクトのヘッダのフォーマット

SSJSVM

の

GC

第3章では，SSJSVMにGCを実装する前にGCがどのような機能を持ったプログラム なのかを説明する．また，既存のSSJSVMに実装されているBoehmGCがどのようなGC なのかを説明する．その上で，既存のSSJSVMのGCの性能を調査して，SSJSVMに専用 のGCを実装することで性能改善できるかを調べる．

3.1

GC

の概要

GCとは，プログラムが使わなくなったメモリ領域(ごみ)を自動的に回収して再利用可 能にする仕組みである．GCの動作は，まずメモリ領域上のごみを発見して，見つけたごみ を回収する．そしてプログラムが再度利用できるようにし，再びプログラムからの要求に応 じてメモリを割り当てる．これらの機能を持ったプログラムがGCである． 通常GCはを持つシステムでは，プログラムの開始時にシステムが必要なメモリ領域を予 め確保しておき，実行中には確保した領域内にデータを配置する．このとき，メモリ領域上 に予め確保しておく領域をヒープ領域と呼ぶ．また，GCによって操作されるこれらのデー タをオブジェクトと呼ぶ．ヒープ領域に配置されたオブジェクトはGCで操作するため，配 置するオブジェクトにはオブジェクト自体の情報を持たせる必要がある．そのため，オブ ジェクトにはヘッダを付与して，オブジェクトの情報を保持する．ヘッダに付与される情報 は，主にオブジェクトのサイズやオブジェクトの種類である．また，オブジェクトはプログ ラムを実行する際に必要なデータを保持している．これらを保持している場所をフィールド と呼び，プログラムは必要に応じてオブジェクトのフィールドにアクセスしてデータを参照

3.1 GCの概要 したり書き換えたりする．プログラムは一般的に，オブジェクトを参照で連結したデータ構 造を作り，その参照がポインタで実現されている．そのため，GCはそれを利用してポイン タを辿り，オブジェクトからさらに別のオブジェクトを探索する．整数などのポインタでは ないものを非ポインタと呼ぶことにする．非ポインタに対してはGCは何も操作しない． ヒープ領域に割り当てられたオブジェクトのうち，プログラムから参照できて，GC以降 もプログラム中で使われる可能性のあるオブジェクトを生きているオブジェクト，プログラ ムからはどうやっても参照できないオブジェクトを死んでいるオブジェクトと呼ぶ．プログ ラムからどうやっても参照できないため，死んでいるオブジェクトはごみと呼ばれている． プログラムからの参照の有無でオブジェクトが生きているか死んでいるかを判断するた め，GCはプログラムからの参照の有無を判断する必要がある．プログラムが持つ参照の元 となる部分をルートと呼ぶ．例えば，グローバル変数が指す先はプログラムから参照可能な ため，グローバル変数はルートとなる． プログラムの実行中にGCが起こるとプログラムは処理を停止してGCを実行する．そ のため，図3.1のようにプログラムの実行ではプログラムの本来の処理の合間にメモリの割 り当てとごみの回収を行っていることになる[6]． 図3.1 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はそれを非ポインタであるかポイ

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

SSJSVM

における

GC

の検証

3.4.1

検証方法

SSJSVMは保守的GCを利用しているため，GCが遅いと考えられる．なので，本当に 遅いのか検証を行って確かめる．検証では，GCにかかっている時間とメモリ割り当てにか かる時間を調べたいので，以下の3種類のSSJSVM処理系を用いてプログラムの実行時間 を比較する．

• 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種類の処理系の実行時間を表したグラフである．このグラ

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を実装することで高速化の余地があることがわかった．

図3.3 メモリを多く消費して頻繁にGCが起こるプログラムの実行時間の比較

第

4

章

マークスイープ

GC

の実装

第3章では，BoehmGCが使われている既存のSSJSVMのGCの性能を調査した．その 結果BoehmGCは遅いことがわかった．BoehmGCは保守的GCであるため，ヒープ領域 上のオブジェクトを移動させるような処理はできない．そのため，高速な GCアルゴリズ ムを適用させることができず処理が遅い．そこで本研究では，SSJSVMに保守的では無い マークスイープGCを実装する．マークスイープGCを選んだ理由は，GCアルゴリズムの 中でも比較的実装が簡単であることである．

4.1

マークスイープ

GC

マークスイープGCとはマークフェーズとスイープフェーズの 2つのステップから成る GCアルゴリズムである．マークフェーズではヒープ領域上の全ての生きているオブジェク トに生きていることを示すマークをつける．スイープフェーズは，ヒープ領域上のマークの ついていないオブジェクトを全て回収する．回収したメモリ領域は，フリーリストと呼ばれ る空き領域のリストに繋げられる．プログラムからメモリが要求される度に，フリーリスト からメモリを割り当てる．以下で詳しく説明する．

4.1.1

マークフェーズ

マークフェーズでは，まず最初にアプリケーションから直接参照されているヒープ領域上 のオブジェクトのヘッダにマークをつける．このマークをつけたオブジェクトは生きている オブジェクトであり，ここから辿れる全てのオブジェクトにも再帰的にマークをつけていく．

図4.1 マークフェーズ時のヒープ領域 こうすることで，メモリ領域上の全ての生きているオブジェクトにマークをつけることが可 能となる．再帰的に全てのオブジェクトを辿る際に，マーク済みのオブジェクトに辿り着い た場合には，そこから先のオブジェクトは辿らないようにすることで繰り返し辿らないよう にする． マークフェーズ時におけるメモリ領域の状態を図4.1に示す．この図は，プログラムから 参照されるヒープ領域上に割り当てられたオブジェクトのヘッダにマークをつけている様子 を表している．プログラムから直接参照されるオブジェクトだけではなく，オブジェクトか ら参照されているオブジェクトにもマークしており，プログラムから辿れる全てのオブジェ クトにマークをつけている．

4.1.2

スイープフェーズ

スイープフェーズでは，まず最初にヒープ領域の一番端のオブジェクトから順に全てのオ ブジェクトのヘッダをスキャンしていく．そして，ヘッダにマークの付いていないオブジェ クトを発見すると，回収して再利用可能な空き領域にする．オブジェクトのヘッダにマーク が付いている場合は，マークを外して次のGCに備える．回収されてできたヒープ領域上の 空き領域は，フリーリストに繋いで確保しておくことで，プログラムからのメモリ要求に備

4.2 設計 図4.2 スイープフェーズ時のヒープ領域 える． スイープフェーズ時におけるメモリ領域の状態を図4.2に示す．この図は，図4.1のマー クフェーズ時にマークを付けなかったヒープ領域上のオブジェクトを全て回収し，再度利用 可能にするためにフリーリストに繋いだ図である．

4.1.3

メモリ割り当て

プログラムからのメモリの要求に応じるために，ヒープ領域上の空き領域を繋げて確保し ているリストをフリーリストと呼ぶ．プログラムからメモリの要求があれば，フリーリスト の先頭から順に必要なサイズ以上の空き領域を探して，空き領域が見つかればその空き領域 をプログラムに渡す．この時，必要なサイズ以上の空き領域が見つからなかった場合はGC を発生させて，新たな空き領域をフリーリストに確保する．それでも見つからない場合はプ ログラムは停止する．

4.2

設計

本研究にて実装するマークスイープGCの概要を説明する．マークスイープGCに必要 なフリーリストの構造や，GCが発生するタイミング，マークフェーズとスイープフェーズ

におけるプログラムの動作について示す．

4.2.1

フリーリスト

ヒープ領域上の空き領域には，空き領域のサイズとフリーリストの次の空き領域の先頭ア ドレスを記憶させておくヘッダを付与する．ヘッダはオブジェクトのヘッダと同じ構造にし ておく，ヘッダを付与するのは，スイープフェーズの処理で空き領域を見分けられるように するためである．このときのフリーリストを図4.3に示す．図は，ヒープ領域上の空き領域 にヘッダを付与し，ヘッダは空き領域のサイズと次の空き領域を指すアドレスを持つことを 表している． プログラムからメモリの要求があった場合はフリーリストの先頭の空き領域から順にリ ストを辿り，要求されたサイズ以上のサイズの空き領域を探す．空き領域が見つかれば，そ こから必要な大きさの領域を切り取ってオブジェクトを割り当てる．切り取られて余った領 域は再びフリーリストに繋ぐことでヒープ領域の節約をする．ただし，先程も述べたよう にフリーリストにはヘッダを付与するので，空き領域をフリーリストに繋ぐためには，最低 16Byteの領域が必要である．そのため，切り取られて余った領域が 16Byteに満たない場 合は，その領域にはオブジェクトを割り当てない．ゆえに，プログラムからの要求で空き領 域を割り当てる条件は，要求されたサイズより空き領域が16Byte以上大きい場合か，要求 されたサイズと全く同じサイズの空き領域であることである． 図4.3 ヒープ領域上のフリーリストの様子

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言語のローカル変数 • 関数呼び出しの返り値を格納するレジスタ • 汎用レジスタ • 文字列テーブル ルートから指されたオブジェクトが見つかったら，そこから再帰的にオブジェクトを辿ら

なければならない．しかし，オブジェクトのデータ型によって，オブジェクトから辿る先が 異なってくる．そこで，以下では第 2章の表2.2で示したデータ型のそれぞれの辿り方を 示す． OBJECT型 OBJECT型のオブジェクトは，ヘッダ以外に4つのプロパティを保持している．それは， 配列にどこまでデータが格納されているかを表す値，配列の限界の長さの値，ハッシュテー ブル，データを格納する配列の4種類である．このうちオブジェクトから辿る必要のあるプ ロパティはデータを格納する配列である．そして，配列に格納されているデータから指され ているオブジェクトを辿る．図4.4はOBJECT型オブジェクトの構造を示しており，prop プロパティで指された配列を探索する．この図では，headerがヘッダ，numberOfPropが 配列にどこまでデータが格納されているかを表す値，limitOfPropが配列の限界の長さ， mapがハッシュテーブルを示している． 図4.4 OBJECT型オブジェクトの構造

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プロパティで指された配列も探索する必要が ある．

図4.6 ARRAY型オブジェクトの構造

その他の型

上記に上げたOBJECT型，STRING型，FLONUM型，ARRAY型の4つオブジェク ト以外のデータ型のオブジェクトについては，オブジェクトの辿り方はOBJECT型と同じ である．なぜなら4つのオブジェクト以外のデータ型は全てOBJECT型と同じデータ構造 を持っているため，そのOBJECT型のデータ構造から他のオブジェクトを辿れるためであ る．そのため，この4つの型以外の型は全てOBJECT型と同じ辿り方で再帰的にオブジェ クトを辿ることができる．

4.2.4

スイープフェーズ

本研究では，ヒープ領域上にあるオブジェクトとフリーリストに繋がれた空き領域は共に それぞれの領域のサイズを記憶しているヘッダを持っている．そのため，ヒープ領域の先頭 から，ヘッダに記憶されている領域サイズずつ移動することで全てのオブジェクトまたは空 き領域へアクセスすることができる． スイープフェーズで行う動作を以下に示す．まず，ヒープ領域の一番端のオブジェクトか

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関数を用

図4.7 スイープフェーズの動作の例 いて割り当てたメモリ領域はGCの対象になるが，今回は時間の都合でオブジェクトのみを GCの対象にする．例えば，オブジェクトは必要なデータをオブジェクトの持つ配列に格納 して保存しており，その配列にアクセスするためにハッシュテーブルを用いて必要なデータ が格納されている場所を探してアクセスする．そのため，オブジェクトにはハッシュテーブ ルが必要なので，オブジェクトが作られる度にハッシュテーブルもmalloc関数を用いて作 成される．しかし，今回はオブジェクトはGCの対象とするが，ハッシュテーブルについて はGCの対象外としている．

4.3.2

メモリの割り当て

本研究では，最初のオブジェクトが作成される前に，一度だけ任意のサイズのヒープ領域 を確保し，その確保したヒープ領域上にオブジェクトを配置していくことでメモリをオブ ジェクトに割り当てる．今回実装したGCでは，プログラマが自由にヒープ領域のサイズを 決めることができるようになっている．最初にヒープ領域を確保する際は，確保した領域が フリーリストに繋げられて空き領域となる．

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種類の配列のプロパティを辿る．

STRING型，FLONUM型，ARRAY型以外のデータ型のオブジェクトはOBJECT型と 同じ配列プロパティである body配列を辿る．オブジェクトの持つ numberOfPropプロパ ティにはbody配列の長さの値が格納されており，propCount変数に格納する．格納された 値にしたがって配列プロパティを辿る．また，ARRAY型のオブジェクトが持つlengthプ ロパティはprop配列の配列の長さが格納されており，その値にしたがって配列プロパティ を辿る．

4.3 実装

ソースコード4.1 markObject関数の擬似コード

1: static void markObject(JSValue objp) {

2: //オブジェクトを指すポインタか判別 3: if((!equalTag(objp, 0b000)) | (objp == 0)) 4: return; //オブジェクトを指すポインタでなければ何もしない 5: if(!markCheck(objp)) // オブジェクにマークがあるかどうか判別 6: return; //オブジェクトにマークがあれば何もしない 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型の持つ配列プロパティを辿る

15: markObject(objp−>prop[i]); // markObject関数を呼び出す

16: }

17: for(i = 0; i < objp−>length; i++) { // OBJECT型の持つ配列プロパティを辿る 18: markObject(objp−>body[i]); // markObject関数を呼び出す

19: } 20: break;

21: default: //残りの型はOBJECT型の配列を辿る

22: propCount = objp−>numberOfProp; // 配列の長さを取得

23: for(i = 0; i <= propCount; i++){ //OBJECT型の持つ配列プロパティを辿る

24: markObject(objp−>prop[i]); // markObject関数を呼び出す

25: } 26: break;

27: } 28: }

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が起こった場合は，呼び出し先の

4.3 実装 図4.8 C言語のローカル変数を保存するスタック 関数内のローカル変数だけではなく，呼び出し元の関数内のローカル変数もマークしなけれ ばならない．そのため，スタックを用いてローカル変数を保存していく．保存する必要のあ るローカル変数は，グローバル変数同様にJSValue型の変数である．例えば，関数fの中 で関数gが呼び出された場合は，図4.8のように下から関数fのローカル変数，関数fが格 納されている場所を示す値，関数g のローカル変数というふうにスタックに積まれていく． 関数gから抜け出す際は，関数fが格納されている場所を示す値にしたがって，スタックを 操作することで関数fに戻る． 関数呼び出しの返り値を格納するレジスタ 関数呼び出しの返り値が格納されているレジスタは，表2.1のaレジスタである．特殊レ ジスタは第2章で述べたコンテキスト構造体から参照することができるため，コンテキスト から特殊レジスタが持つオブジェクトにも辿ることができる． 汎用レジスタ 制御スタックに積まれている汎用レジスタはオブジェクトを指している．そのため，制御 スタックにある汎用レジスタが指すオブジェクトを辿る必要がある．

文字列テーブル JavaScriptプログラム内の関数に対応するバイトコードの命令列が関数テーブルに格納 されている．関数テーブルにバイトコードの命令列を読み込ませる際に，文字列テーブルに 文字列のデータを読み込むため，文字列テーブルにあるSTRING型のオブジェクトもマー クをする必要がある．これは，コンテキストから参照されている命令テーブルから辿ること ができる．

第

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ループで生成したオブジェクト

をグローバル変数に格納し，内側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に示す．

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++) 9: new Cell(0, null); 10: }

図5.2 オブジェクトの割り当てとmalloc関数でのメモリ割り当ての回数

5.2

検証結果

ごみのオブジェクトを多数生成するプログラムを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の実験に用いたプログラムを実行したときの，本

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

図5.4 本研究のGCを持つSSJSVMの実行時間の内訳と既存のSSJSVMの実行時間の比較

5.3

考察

検証結果より，本研究のGCを持つ SSJSVMが既存の SSJSVMより遅いということが わかった．GCの性能改善を狙って既存のSSJSVMに保守的ではないマークスイープGC を実装したが，既存の SSJSVMより実行時間が遅くなった．図5.4から，メモリ割り当て とGCにかかった時間とメモリ割り当てにかかった時間の差は小さいのに対して，メモリ割 り当てにかかった時間は大きいことがわかる．そのため，メモリ割り当てに多くの時間がか かってしまい遅くなったということがわかる． 本研究のGCのメモリ割り当ては，プログラムから要求されたメモリ領域以上の領域を， フリーリストを先頭から探して割り当てる割り当て方式である．そのため，プログラムから メモリの要求があれば，毎回フリーリストの先頭から必要な空き領域が見つかるまで探索し ていくため，メモリ割り当てに時間がかかる．そこで，メモリ割り当てが起こる度に必要な 空き領域が見つかるまでフリーリストを辿った回数を調べた．図5.5は，オブジェクトにメ モリを割り当てるために，必要な空き領域が見つかるまでフリーリストを辿った回数を示し

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 オブジェクトが割り当てられる度にフリーリストを辿る回数