修論タイトル:「遅延スイープ法におけるメモリアクセスの局所性改善」 (2012年度 修士論文)

氏名:金野 千顕

概要:

ガベージコレクション(GC : Garbage Collection)とは,プログラミング言語における自動メモリ管理機構であり,プログラムが二度と使用しないデータ(ごみ)を見つけて再度利用するための機能を持つ.

一般的なガベージコレクションとして,マークスイープ法(Mark Sweep GC)がある.このガベージコレクションはルートから生きているオブジェクトを確認するマークフェーズと,ヒープ領域内からごみを回収して再利用するスイープフェーズがある.その回収には,フリーリストと呼ばれるリストに保存する.アロケーションは,フリーリストの先頭のごみを新たなオブジェクトとしてミューテータに渡してヒープ領域に配置する.しかし,親子関係の(連続して参照される)オブジェクトがヒープ領域上の離れた位置に配置されてしまうことも多く,アクセスに時間がかかる.また,ヒープサイズが大きくなるほど,ミューテータ(アプリケーション)の停止時間が長くなってしまう.

一方,マークスイープ法の一種である遅延スイープ法(Lazy Sweep GC)はマークスイープ法と同様な動作を行なう.しかし,スイープフェーズが少しずつ必要に応じて進められる.ミューテータにより要求されたサイズのごみをメモリ要求時に探すため,ごみの回収は分割して行なわれる.1つのポインタ(スイープポインタ)を利用して,ヒープをアドレス順に徐々に参照する.これにより,マークスイープ法と比べてガベージコレクションの停止回数が多くなるが,1回の停止あたりの停止時間を短くすることができる.それにより時間的局所性が多少向上できた.しかし,遅延スイープ法はマークスイープ法の空間的局所性を改善できていないため,さらにメモリアクセスの局所性を向上させることが望まれる.

キャッシュはライン単位で管理されるため,新たに割り当てるオブジェクトは最近参照したヒープ領域の近辺に配置できると良い.しかし,他のオブジェクトが既に割り当てられていて探すのが困難な可能性がある.本研究では親子関係のあるオブジェクトを生成し始めるときに,ラインサイズのメモリ領域(以後,チャンクと呼ぶ)を割り当て,そこへ親子関係のあるオブジェクトを配置できるようにする手法を示す.その手法では,後に親子関係のあるオブジェクト群を生成する際は,専用のコンストラクタを明示的に用いるようにしている.このコンストラクタはオブジェクトを参照の局所性に考慮してチャンクに配置する.


[修論pdf][研究室内部向け情報]