概要
ISOLisp準拠の学習研究用処理系Easy-ISLispにパラレルGCとコンカレントGCを実装しました。マーク＆スイープ方式にPthreadを利用してパラレル、コンカレントの機能を追加したものです。このうちコンカレントについて難しい部分がありましたので後日のために記録に残すこととしました。
メモリ構成など
Easy-ISLispは学習用を意図しており、簡便な構成にするためにセルはC言語の構造体配列で実装しています。20メガセルが総セル数です。インタプリタにおいては環境は連想リストになっています。コンパイラはLispコードをCコードに変換する方式をとっています。
処理フェーズ
コンカレントGCは次の４つフェーズから成ります。
初期マーク
フラグ concurrent_flagをONにしてメインスレッドにGCのスレッドが起動していることを知らせます。シンボルにつながるハッシュテーブルをマークします。この間、メインスレッドでセルを消費する場合にはremard配列にそのアドレスを記憶しておきます。
再マーク
フラグ concurrent_stop_flagをONにしてメインスレッドにsopt the woeldに入ったことを知らせます。この間、メインスレッド側ではセルの消費は停止します。環境を表している連想リストなど保存が必要なセルを保存します。さらに初期マーク中に消費されたセルをremarkは配列から辿ってマークをします。
逐次スイープ
stop the worldの状態で全セルの２０％を回収します。この段階でconcullent_stop_flagをOFFにしてコンカレント動作に戻ります。
コンカレントスイープ
concurrent_sweep_flagをONにしてメインスレッドにコンカレントな回収に入ったことを知らせます。残りの80%のセルを回収します。全部を回収し終わったところで空セル数をカウントし、concurrent_sweep_flag及びconcurrent_flagをOFFにしてGCスレッドが終了したことを知らせます。
工夫を要した点
GC起動時の残りセル数
GCを起動した後に初期マークを行います。この時にコンカレントにメインスレッドは動作しています。そのためのセルを保持しておかないといけません。経験的に90万セルを残した状態でGCを起動しています。
逐次スイープ
セル回収とセル消費を同時に行おうとするとmutexを使ってメインスレッドとの同期をとる必要が生じます。これは速度の低下を招きます。また、消費数が回収数を上回るとセルを供給できなくなります。そこで予め逐次処理で20％のセルを回収してからコンカレント処理に移行します。２０％は計算実験をしながら割り出した数値です。
測定
ISLispのベンチマークテストコードをコンパイル、これを動作させたときのGC起動における数値を記録しました。下記のようになっていました。
Test 16: FFT -> ok, time = 0.03125s.
Test 17: Puzzle -> ok, time = 0.046875s.
GC (stop) (second) 0.138500 (0.021626)
GC (stop) (second) 0.132917 (0.021224)
Test 18: Triang -> ok, time = 1.32812s.
Test 19: Fprint -> ok, time = 00000s.
計測はicore5のマシンでWndows WSL Ubuntuで行いました。2回GCが起動しており1回あたりおよそ１３０ミリ秒、そのうちstop the worldは21ミリ秒程度です。
比較
ソースコードのうちのgbc.cがガベージコレクションにかかわるものです。冒頭にできるだけコメントを書いています。#define GC 2で逐次処理 #define GC 1でパラレル、 #defin GC 0でコンカレントで動作するようになっています。スレッドに処理を分割するためのオーバーヘッドがあり、実行速度は若干、遅くなります。しかし、stop the worldの時間は6分の１程度に抑えることができています。
実装はGithubにおいてあります。お試しください。
https://github.com/sasagawa888/eisl