------------------------------------------------------------------
第 346 回 PTT のお知らせ
--- Programming Tools and Techniques ---
------------------------------------------------------------------
■日時: 2008年7月31日 (木) 18:30 から
■話者: 鵜川 始陽 (電気通信大学)
■題目: メモリ効率のよい実時間ごみ集め
■概要:
本発表では，Javaのサブセットの実行環境であるKVM上に実装した
実時間ごみ集めを紹介する．このごみ集めは，高い実時間性，良い
メモリ効率，及び実装しやすいことを特徴とする．近年では，生産
性を高めるために，組込みプログラムにJavaなどの近代的な言語を
使う例が増えつつある．ごみ集めも生産性の向上に大きく貢献して
いる．一方で，古典的なごみ集めでは，ごみ集めが開始されると完
了するまでアプリケーションの実行が停止してしまうため，実時間
アプリケーションに適さない．これに対応するために，ごみ集めを
分割して少しずつ進める実時間ごみ集めが提案されている．本発表
では，代表的な実時間ごみ集めアルゴリズムを紹介する．そのうえ
で，KVMのごみ集めを紹介する．このごみ集めはスナップショット
方式を基本とした．また，実時間コンパクションを開発し，フラグ
メンテーションを解消した．
■場所: 電気通信大学 西9号館 3F AVホール
新宿駅より京王線，調布駅(特急・準特急で2つ目，15分) 北口下車，
北西方向徒歩12分程度，電気通信大学西地区キャンパスの
南西端にある白い建物; 甲州街道(国道20号線)
下石原交差点の北20メートルに西門あり．
交通ガイド
http://www.uec.ac.jp/map/comm.html
キャンパス内マップ(図中の40番の建物)
http://www.uec.ac.jp/map/campus.html
第 346 回 PTT report
出席者：20名
角田，小室，寺田，阿部，佐藤，田村，岩崎，多田，小宮，佐藤，高須賀（電通
大），小林（元電通大），相川，丸山，笹田（東大），三廻部（IBM），佐々木，
卜部（TNT），日比野（朝日ネット），光林（ATL）
話者: 鵜川 始陽 (電気通信大学)
題名: メモリ効率のよい実時間ごみ集め
質疑応答：
Q. C じゃなくて C++？
A. 私の知っている例ではC++が多いようです．
Q. スレッド数が増えるとレジスタの数は無視できないほど増える
のでは？
A. 全スレッドのレジスタを一括してスキャンすると無視できなく
なります．今回のKVMには実装していませんが，「スレッド再開バ
リア」なるものを使ってルートスキャンを分割する方法を提案して
いますので，よろしければご覧ください．
鵜川始陽，花井亮，八杉昌宏，湯淺太一：
マルチスレッド環境における実時間ごみ集めのためのスレッド再開バリア，
コンピュータソフトウェア， Vol. 25 (2008) No.2 pp.2_135-2_150．
Q. 断片化が激しいとはどうやって選ぶのか？
A. 今後の課題です．今の実装は，単純に前回コンパクション対象
にした領域の次のアドレスから始めて，空きメモリに比例した大き
さの領域を対象としてコンパクションしています．
Q. cons セルが5割り増し？
A. 全てのオブジェクトがフォワーディングポインタ(転居先)の領
域として１ワードを必要とするので，２ワードのオブジェクトは５
割増しの大きさになってしまいます．
Q. 組み込みでそれは良い？
A. 全てのオブジェクトが１ワード大きくなっても，例えばコピー
GCではじめからヒープの５０％しか使えないよりはいいです．
Q. マルチスレッド環境ではロックが必要では？
A. はい．このままでは，マルチプロセッサやプリエンプションの
ある環境では，書き込みバリアでロックが必要です．
Q. read などで使う領域の複製はどうするのか？
A. システムコールなど，処理系の外部で書き込みが起こる場合は，
後から書き込まれた領域をコピーしてつじつまを合わせます．
Q. y は引越ししなくてよいのか？
A. 変数xとyがそれぞれ複製元と複製先を指している場合，xかyの
どちらかの転居先(元)と他方を比較すれば十分です．
Q. ポインタの大小関係の比較は？
A. Javaなので参照先アドレス自体の大小比較はありません．
Q. グラフは空き領域の最大値？
A. 連続した空き領域のうち最大のものの大きさです．
Q. グラフの横軸は？
A. 実行したバイトコード命令の数です．
Q. 評価は「GC回数の削減回数」とするべきでは？
A. フラグメンテーションが激しくなればGC回数が増えていき，つ
いにはいくらGCをしても所望の大きさの領域を確保できなくなって
しまいます．今回の評価では，プログラムが要求する領域がどの程
度の大きさまで耐えれるのかを調べるために，の連続空き領域の最
大値を測りました．
Q. グラフ中のGC開始はどこ？
A. 連続空き領域の最大値が急に増えているところです．
Q. フラグメンテーション回避により動くようになった例は？
A. 同じベンチマークでヒープサイズを小さくしていくと，コンパ
クションしない処理系では動かなくなります．さらに小さくすると，
コンパクションする場合でも動かなくなります．
Q. スコアとは？
A. ベンチマークプログラムが出力する「スコア」で，大きいほど
速いことを示しています．
Q. root への書き込みも write barrier している？
A. ルートのポインタは最後に一括して更新するのでバリア不要で
す．ただし，スタックを一括スキャンすると時間がかかるかもしれ
ないので，スタックはリターンバリアの手法を使って関数フレーム
単位で分割してスキャンしています．
Q. 更新し終わるまでは使えない状況があるが，そのラグは？
A. ありますが，この実験ではグラフに表れないほど短いです．
Q. mutator と collector の動く比率は？
A. 今の実装ではメモリ割り当て毎にGCが100us動くようにしています．
Q. その比率をどう決めるか，というのは難しいのでは．
A. 難しいです．
Q. アプリケーションを細切れにするとスループットが減るが，その評価は？
A. スコアの評価がそれで，最大で2割程度，平均で1割弱落ちています．
Q. 組み込みは，まず最初に確保してしまうのがいいのではないか．
JavaでGCは必ず必要になるものなのか．
A. Javaリアルタム仕様(RTSJ)ではそのようなプログラミングを前
提としているようです．
Q. 100us は妥当なのか？
A. そもそも，性能評価の環境が妥当ではない（デスクトップPCを
使っている）ので，短めに100usとしました．それほど根拠はあり
ません．
Q. 消費電力については？
A. 考えていません．
Q. 25% というのはどうやって決めたのか？
A. 実験してよさそうな値にしました．
Q. 組み込みだとハイブリッド（gc, malloc/free）がいいのでは？
A. RTSJでは，GCとスコープメモリ(あるスコープを抜けるまでメモ
リの解放はせずに，抜けるときに解放する)の組み合わせです.
Q. ARM などに Core2Duo の結果は適用できるのか？
A. 今後ARMで評価します．
Q. GC してコンパクション，ということか．
A. はい．
Q. 関連研究は？
A. IBMのコンパイラでリードバリアを挿入してコンパクションする
GCがいい性能を出しています．
David F. Bacon, Perry Cheng, V.T. Rajan:
A Real-time Garbage Collector with Low Overhead and
Consistent Utilization,
POPL'03, (2003) pp. 285-298.
Q. リアルタイム性を意識することは多いのか？
A. 絶対数としては十分多いとおもいます．
Q. SquawkVM は？
A. 調査します．
Q. GCを使って十分な予測可能性はあるのか？
A. 完全には無理ですが，実用的にはなると思います．
Q. Javaリアルタイム仕様はGCを使わないでリアルタイム性を保証するのか？
A. はい．
Q. ポインタの比較は負荷にならない？
A. アドレスの比較だけなので，それほど重くはないです．