コンパイラ演習 第 12 回 (2012/01/05) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎.

Presentation on theme: "コンパイラ演習 第 12 回 (2012/01/05) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎."— Presentation transcript:

1 コンパイラ演習 第 12 回 (2012/01/05) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎

2 今日の内容 Garbage Collection （ GC, ごみ集め） – 参照されなくなったメモリ領域を解放するこ と 配列境界検査

3 Garbage Collection 概論 遠藤敏夫先生の資料を参考にしています http://matsu-www.is.titech.ac.jp/~endo/gc/gc.pdf 遠藤敏夫先生 – 東京工業大学大学院 特任准教授 http://matsu-www.is.titech.ac.jp/~endo/

4 今回紹介する GC の種類 参照カウント (reference counting) Tracing GC – マーク & スィープ – Copying GC

5 参照カウント (Reference Counting) オブジェクトへの参照 ( ポインタ ) の数を オブジェクト自身に記録しておく 参照を作る / なくすたびにカウントを増減 カウントが 0 になったらオブジェクトを 解放

6 参照カウントの例 Roots ※ ここで roots とは、レジスタやメモリスタックなど GC の起点となる集合 ( 参照され得ることが分かっている集合 ) を表す

7 参照カウントの例 Roots 1

8 参照カウントの例 Roots 1 1

9 参照カウントの例 Roots 1 1 1

10 参照カウントの例 Roots 1 1 1

11 参照カウントの例 Roots 1 1 1 1

12 参照カウントの例 Roots 1 1 1 2

13 参照カウントの例 Roots 1 2 1 2

14 参照カウントの例 Roots 1 2 1 1 2

15 参照カウントの例 Roots 1 2 1 2 2

16 参照カウントの例 Roots 1 2 1 2 1

17 参照カウントの例 Roots 1 2 1 2 0

18 参照カウントの例 Roots 1 2 1 0 2 カウントが 0 になったら 解放

19 参照カウントでは上手くいかない 例 Roots 1 2 1 2

20 参照カウントでは上手くいかない 例 Roots 1 2 1 1 2

21 参照カウントでは上手くいかない 例 Roots 1 2 1 1 1 2

22 参照カウントでは上手くいかない 例 Roots 1 2 1 2 1 2

23 参照カウントでは上手くいかない 例 Roots 1 2 1 1 1 2 循環参照はどうする ?

24 マーク & スィープ マークとスィープの 2 段階からなる – マーク : 参照可能なオブジェクトにフラグを立 てる – スィープ : フラグの立ってないオブジェクトを 解放 Roots ✓ ✓ ✓ ✓ フラグが付かなかったものを解 放

25 3 色マーク & スィープの例 まず全て「白」にする Roots

26 3 色マーク & スィープの例 到達可能なオブジェクトを「灰」にする Roots

27 3 色マーク & スィープの例 未探索の参照のない「灰」を「黒」にす る Roots 今回は該当なし

28 3 色マーク & スィープの例 到達可能なオブジェクトを「灰」にする Roots

29 3 色マーク & スィープの例 未探索の参照のない「灰」を「黒」にす る Roots

30 3 色マーク & スィープの例 「灰」が無くなったのでマーク終了 Roots

31 3 色マーク & スィープの例 全ての「白」を解放する ( スイープ ) Roots フラグが付かなかったものを解 放 これらのオブジェクトを解放す る

32 Copying GC ヒープを二分割し、片方だけを使う 片方が埋まったら、参照可能なオブジェ クトをもう片方に移す – 移されなかったオブジェクトはそのまま解放 移すついでにヒープのデフラグができる

33 Copying GC の例 (GC 開始前 ) From-spaceTo-space Roots a b c d e

34 Copying GC の例 到達可能なオブジェクトを to-space へコピー From-spaceTo-space Roots a b c d e a コピー済みだが まだ from-space を指す オブジェクトは「灰」 コピー済みだが まだ from-space を指す オブジェクトは「灰」 コピー元のオブジェクトに コピー先のオブジェクトへ の参照を保存する a

35 Copying GC の例 「灰」のオブジェクトから参照されるオブジェクトをコ ピー From-spaceTo-space Roots a b c d e a b コピー済みで もう from-space を参照しない オブジェクトは「黒」 コピー済みで もう from-space を参照しない オブジェクトは「黒」 b a

36 Copying GC の例 「灰」のオブジェクトから参照されるオブジェクトをコ ピー From-spaceTo-space Roots a b c d e a b c d c d b

37 Copying GC の例 「灰」のオブジェクトから参照されるオブジェクトをコ ピー From-spaceTo-space Roots a b c d e a b c d c から d への参照を 復元するために コピー元の d に保存され た 参照を利用する c から d への参照を 復元するために コピー元の d に保存され た 参照を利用する c

38 Copying GC の例 「灰」のオブジェクトから参照されるオブジェクトをコ ピー From-spaceTo-space Roots a b c dd e a b c d

39 From-spaceTo-space Copying GC の例 (GC 終了 ) Roots a b d e c a b c d

40 GC の利点・欠点 malloc/free vs. 参照カウント vs. tracing GC マーク & スィープ vs. copying – メモリ確保は大抵 copying GC が勝つ – メモリ効率は大抵マーク & スィープが勝つ 1 回の GC にかかる時間はスィープを lazy に行う マーク & スィープが勝つ malloc/free 参照カウン ト Tracing GC プログラムの 書きやすさ × ○ ( △ ?) ○ 停止時間 ○○× 実行時間全体 ○× △ (○?) メモリ効率 ○ △ ×

41 Tracing GC の改良 インクリメンタル GC: ちょっとづつ GC – GC の処理を細切れにして プログラムの実行と交互に行う手法 世代別 GC (Generational GC) – ヒープを幾つかの「世代」に分ける手法 大抵のオブジェクトはすぐ不要になるので 「若い世代」の GC だけで済ませる – 寿命の長いオブジェクトの探索回数を減らせる ただし、どちらの手法も write barrier が必要に なる Write barrier = ここでは、オブジェクトへの書き込み時に特別な処理を行うこと

42 GC のその他の話題 保守的な GC (conservative GC) 並行 GC (concurrent GC) と 並列 GC (parallel GC) 分散環境の GC – 分散参照カウント – 分散 tracing GC

43 “Conservative” garbage collection と は 参照と整数の区別がつかない環境でも行え る garbage collection のこと – 例えば C 言語ではメモリの中身を見ても 整数とポインタを区別できない 解決方法 : とりあえず全部ポインタだと思う

44 配列境界検査 GC のための拡張と同様に 配列データに長さを表すタグを付加する 配列アクセスを行う命令列の前に 配列長と添字を比較する命令を出力する 1234 567890 2 1234 567890

45 共通課題 MinCaml に以下の改造を加えよ – 配列長を表すタグを配列に付加する – 配列アクセスの前に境界検査を行い 配列の範囲外にアクセスしようとしていたら プログラムを終了させるなどの処理を行う

46 コンパイラ係用選択課題 Garbage collection を自作コンパイラまたは MinCaml に実装せよ – 使用する GC アルゴリズムは自由 – ゴミをたくさん作りながら動く サンプルプログラムを記述し それが複数回の GC を経て 動き続けることを確認すること

47 演習でどの GC を実装するか ? たぶん copying GC が一番楽 興味があれば mark-sweep GC に 挑戦してみるのもよい コンパイラ側の改造が多いのを いとわなければ reference count も おもしろい さらに余裕があれば incremental GC や generational GC も

48 GC 導入のための コンパイラの変更 (1) ヒープを作成する（ stub の）コードの改造 – Copying GC を採用する場合はヒープを 2 つ用意する 等 ヒープ内にメモリを確保するコードの改造 – ヒープポインタとヒープリミットを比較し ヒープがあふれそうなら GC ルーチンに飛ぶ ヒープ内のデータを扱うコードの改造 – 配列やタプルなどに型やサイズを表すタグを付加 – 採用する GC によっては mark bit 領域や reference count 領域などを追加し それらを操作するコードも追加

49 GC 導入のための コンパイラの変更 (2) GC が rootset を得るための機構の追加 – スタックに積まれた各ワードの型を GC ルーチンが知るための機構の導入 フレームに保存された PC の値から そのフレームの各ワードの型を得られるような表を 作る スタックに値をプッシュする際に その値の型の情報もどこかに書き込んでおく など – 大域変数のアドレスと型を GC ルーチンが知るための機構の導入

50 課題の提出先と締め切り 提出先 : compiler-report-2011@yl.is.s.u-tokyo.ac.jp 締め切り : 2 週間後 (1/19) の午後 1 時 – コンパイラ係用課題の締め切り : 2012 年 2 月 27 日 Subject: Report 12 – 例： Report 12 11099 本文にも氏名と学籍番号を明記のこと 半角スペース 1 個ずつ  質問は compiler-query-2011@yl.is.s.u-tokyo.ac.jp まで

51 コンパイラ係の 成績評価について (1) 選択課題を 1 つ以上提出してください – また選択課題と同等以上の難度の言語機構の実 装 をもって選択課題の提出とみなすことも可能で す 事前に相談してください

52 コンパイラ係の 成績評価について (2) 各コンパイラ係に前田と TA が面談をします – 基本的にはレイトレ競技会の当日または付近の日 – compiler-query-2011@yl.is.s.u-tokyo.ac.jp にメールして予約をとって下さい – 場所は地下端末室、時間は 20 分程度 – やること： 自作コンパイラの特徴や独創的な点などの説明 自作コンパイラによる、プログラム （レイトレ含む） の コンパイル・実行のデモ – 自作コンパイラでコンパイルしたレイトレが 自作 CPU またはシミュレータ上で動く様子を見せて下さい