Garbage Collection Ch.7-a #

用語など #

英単語は短く適切な訳があった場合に翻訳している。

言い換え:

• generation = gen. = 世代
• garbage = ゴミ
• Generational Garbage [(Collection)|(Collector)] = GenGC
• collect = scavenge = “掃除”
• オブジェクト = セル (文字の視認性の観点から「セル」を使用)

7.1 The generational hypothesis #

GC の目的:

• 自動メモリ管理 (だけでなく…)
• locality の向上

Tracing, Copying はそれぞれ以下の点で locality を悪化させる:

→ ページフォルト、キャッシュミスの頻発

Tracing では、長寿オブジェクトに(無駄に)多くの時間を使う:

• 死んでいる可能性が低いのに、毎回 mark-bit を立てに訪問する (mark-sweep)
• flip ごとに繰り返しコピーする (copying)

→ static area, read-only area (in ch.6) に置き、なるべく触らないように

大半のオブジェクトはすぐに死ぬ(weak generational hypothesis):

• オブジェクトは"長寿" or “早死に"のどちらか [Deutsch and Bobrow, 1976]
• 98%のオブジェクトが次の"掃除"で解放可能 [Foderaro and Fateman, 1981]

→ 即解放可能なオブジェクトに注力

→ Generational Garbage Collection (以降 GenGC)

利点:

• 停止時間が短い
  • small part (youngest gen.) に集中
• GC に使われる時間が短い
  • full collection は低頻度
• 局所性に優れる
  • small part (youngest gen.) に集中

欠点:

• “age” の管理
• old gen. -> new gen. のポインタの管理 (後述)

GenGC の基本的戦略:

• generations に分割
  • それぞれが異なる頻度で"掃除"される
    • youngest : 頻繁に
    • older : 低頻度 (or 全くされない)
• 分割数はまちまち [Appel, 1989b; Caudill and Wirfs-Brock, 1986; Hudson, 1991b]
  • Standard ML of New Jersey (SML/NJ) : 2
  • Tektronix 4406 Smalltalk : 7
  • GC toolkit from UMass : any

成功を収め、広く使われている:

• commercial Lisps
• Modula-3
• Standard ML of New Jersey
• Glasgow Haskell
• …

どの戦略を取るかはアプリ依存:

• 大半のオブジェクトはすぐに死ぬ？
• ポインタ書き込みの頻度は？ (特に old->young ポインタ)
• ポインタ書き込みのコストは？

→ 以降はこれらを議論

7.1.1 Object lifetimes #

セルの"age"を管理するためには、“時間"の計り方を決める必要がある。

“時間” = heap に確保されるバイト数:

• メモリの需要を反映 (実装依存)
• GC の頻度に関係する
  • GC の頻度は heap の残りのサイズに依存

weak generational hypothesis を支持する根拠が多く存在:

• 1MB 以内に 80~90%のオブジェクトは死ぬ [Wilson, 1994]
• 1MB 以内に 50~90%のオブジェクトが死ぬ (Common Lisp) [Zorn, 1989]
• 10KB 以内に 75~95%のオブジェクトが死ぬ。1MB をこえるのは 5%以下 (Haskell) [Sansom and Peyton Jones, 1993]
• …

misc:

• The strong generational hypothesis : 長寿セルは長生きする
  • 一般には成立しない
  • 長寿セルはより長く生きる傾向がある かも しれない
• 大きいオブジェクトの寿命に関しての議論は少ない
  • 長生き/そうではない、両者の主張あり [Caudill and Wirfs-Brock, 1986; Ungar and Jackson, 1988; Barrett and Zorn, 1993b]
  • いずれにせよ、特別に扱う方が良い (ch6 を参照)

7.2 Generational garbage collection #

GenGC の概略:

• “age"によって heap を複数の generation に分割
  • 割り当ては youngest generation に
  • 十分生きると、次の世代に promote
• youngest を頻繁に"掃除”
  • そこは最もゴミが見つかりやすい
    • weak hypothesis によると、大半はすぐに死ぬ
  • old(er) gen. の"掃除"頻度は低い

性質:

• 停止時間が短い (比較的)
  • youngest gen. は小さい
• old(er) object のコピーは不要
  • promote され、old(er) gen. に追い出されている
  • younger gen. への pointer は追う必要あり

7.2.1 A simple example #

用語:

• minor collection : youngest gen. のみの “掃除”

7.1

7.1a

7.2

7.3

Diagram7.1~7.3:

• 7.1 : 初期状態、New gen. は満パン
• 7.1a : root set の 1 つ目の差し先をRに変更
• 7.2 : 新たなセルの確保要求。このタイミングで minor collection が走る。
  図は minor collection 後
• 7.3 : right(R)の差し先を 7.2 でのセルに。さらにセルを確保しポインタを調整
  old→new なポインタが新しくできる。

GenGC の 5 つの特徴:

1. younger gen. のみの"掃除"が可能
   • 全体の"掃除"より短い停止時間
2. minor collection を(十分に)生き延びたセルは older gen. に promote
   • 今回は１回
3. 短命セルの効率的な解放
4. 世代間ポインタの発生
   • old(er) → new(er) なポインタは minor collection の時は root として扱う必要あり
   • new(er) gen.内の移動が発生した場合は、このポインタの書き換えが必要
5. 永続ゴミは minor collection では解放できない
   • 永続ゴミ(tenured garbage) : old gen. にあるゴミ

本文記述に矛盾がある可能性

We suppose that all cells apart from cell S are in the younger generation, and that this generation is now full.

Diagram 7.1 では New generation は full。

Suppose that the mutator overwrites the first slot in the root set with a pointer to a new cell R.

root set の最初のスロットがRを指すようになった。これは既にあるセル？新しく確保したセル？後者ならこのタイミングで GC が走るだろうが、ここでは走らないので前者と考えられる。

Suppose further that a second new new cell is requested, but that this request triggers a minor collection of the younger generation.

2 つ目の新しいセルを確保したと読める。そうならば、1 つ目の時点で minor collection が行われるのでは？

※上記説明では、Rは既存セルと解釈して説明した。

7.2.2 Pause time #

ここでは、CopyingGC と GenGC の停止時間について比較を行う。

7.2.3 The root set for minor collections #

Minor collections 時の root は?

当該世代のセルを指す 世代間ポインタ も root の一部:

• 世代間ポインタ (inter-generational pointer)
  • 自身と差し先が世代を跨ぐようなポインタ
    → Diagram 7.5

GenGC においては、世代間ポインタの追跡が重要。

write-barrier のコストの緩和:

• ローカル変数へのポインタ書き込みは記録しない
  • スタックに入る → 記録しなくても GC の対象
  • ほとんどのポインタ書き込みはローカル変数に対して
    → trap コストを大幅に削減

更なる改善:

• old gen. を GC する時は、new gen.も同時に
  • 本来、old gen.を GC する時は、old gen.を指すポインタを知っている必要がある
    • old gen.内の配置が変わる → そこへのポインタを修正する必要あり
  • 同時にやれば、old gen. ← new gen. の追跡が不要に
  • (少なくとも関数型言語においては)
    old gen. ← new gen.の方が、old gen. → new gen.より多い
    → 削減効果あり
• 以上より、old gen. → new gen. のポインタを記録する
  • これにより、new gen.のみの GC が可能になる
  • old gen. を"掃除” する時は new gen. の"掃除"も必要
    • (old gen. ← new gen.を記録していないので)
    • しかし、そこまでの負担ではない
      • new gen. はほとんどゴミ（なので、trace の必要なし
      • old gen. ← new gen.のポインタが大体のケースである
        （ので、いずれにせよ young を見る必要あり

用語:

• minor collection : youngest gen. のみの “掃除” (より高頻度)
• major collection : 複数の gen. の “掃除” (youngest を含む、より低頻度)

7.2.4 Performance #

インタプリタ型言語とコンパイル型言語では話が違う:

• write-barrier に関するオーバーヘッド
  • インタプリタ型言語: 小
  • (最適化を行う)コンパイル型言語: 大
    • hand tuning compiler, non-optimizing compiler (resp.)
      • Ungar’s generation-scavenging GC for Smalltalk-80 : ~2% [Ungar, 1984]
      • same for SOAR : ~3% [Ungar, 1986]
    • optimizing compiler
      • SELF ( Smalltalk-like language ) : 4~27% [Chambers et al., 1989; Chambers et al., 1991]
      • New Jersey ML compiler : 5~10% [Apple, 1989b]
    • Smalltalk と ML
      • 大量の一時オブジェクトを生成 (確保スピード ↑)
        • これは GC の効率を下げるが、GenGC の効率は上がる
          ← 短命オブジェクトの数は増えるので
  • 手続き型言語
    → 確保スピードは低く、セルはより長生き (なので、上の議論は適用できない)
  • No Silver Bullet.

次章からアルゴリズムの詳細に踏み込む:

• 理想
  • low CPU overhead
  • good locality (for virtual memory and cache)
  • short pause time
  • ===
  • 同時に、空間オーバーヘッドも最小限にしたい
• これらはトレードオフの関係
  → 以降では種々のアルゴリズムを通してこのトレードオフを見ていく。

以降では copy-based な GenGC を仮定するが、多くの議論は mark-sweep-based な GenGC にも適用可能。

7.3 Promotion policies #

genGC の２つの目的:

1. 長寿オブジェクトに対するコストの削減
   と、それによる短命オブジェクトへの集中
2. 停止時間の削減
   • 対話的プログラムを邪魔しない程度には

これらは以下のよって達成される:

• “age"によってセルを分類
• older gen. の"掃除"の頻度を younger gen.に比べて低くする

停止時間について

停止時間:

• 主に"掃除"を生き延びた(=コピーが必要な)セルの数に依存
  → これは youngest gen. のサイズに依存
• youngest gen. のサイズを小さくすると、停止時間も短くなる
  • 長寿セルの発生頻度が一定だとすると、1 回の GC での生き残りも少なくなる
    → コピーが必要なセルの数も少なくなるため、停止時間が短くなる

発生するジレンマ:

• 早く promote させないと、new gen.でのコピーが削減できない (→ 停止時間が短くならない)
• 早すぎる promotion は tenured garbage につながる
  • youngest gen. で解放されるべきゴミが old gen. に入り、そこにずっといる (tenured)
    • その子供も解放できない (→ 子供も promote される)
  • old gen.がすぐ満パンになり、major collection を誘発する (→ 長い停止時間)
  • locality の悪化 (頻繁にアクセスされる若いセルが old gen.に)

取るべき選択肢:

1. youngest gen.のサイズを小さくし、停止時間を短くする
2. tenured garbage 覚悟で promotion の割合を増やす

7.3.1 Multiple generations #

heap を 2 層にする恩恵があるなら、3 層以上にするのは自然。

• 層を３つ以上に
  • 中間層はフィルター層
    • youngest gen. からの promotion が早熟だったセルの"掃除”
      → oldest gen. よりも素早く効率的に tenured garbage を"掃除"できる
  • “掃除"の頻度: youngest より低い
    • youngest より埋まるのが遅いため

メリット:

• youngest gen. からの promotion をすぐに行える
  • → youngest gen. のサイズを小さく保てる (tenured garbage の心配がなくなるため)
  • → より少ない停止時間

デメリット:

• (実装などの)複雑さ
• 中間層の解放に時間がかかる
  • full collection よりは少ないが
• younger gen. を見る際の root が増える
  • older gen. からのポインタは root として扱う必要あり

何層が良いのか？:

• youngest 層とその後の層の解放率の落差は大きい (→ ので、層を分ける意味がある)
• この傾向は、後ろの層では見られない
• 多くは 2,3 層の実装になっている

7.3.2 Promotion threshold #

threshold (以下 th と表記) の取り方 : minor collection を生き延びた回数

th=1 の場合:

• 毎回の minor collection で全て promote させる
• 50~100%の promotion rate の向上 [Zorn, 1993]
  • 2,3 回で死ぬオブジェクトに対して、“掃除"の機会を与えない

promotion の挙動についてグラフで確認

Diagram 7.6:

• th=2
• 確保されてから 2 回目の"掃除"を生き延びる確率
  • (a) : scavenge n を生き延びる確率
  • (b) : scavenge n + 1 を生き延びる確率
  • (c) : scavenge n + 2 を生き延びる確率
• 大半のオブジェクトは若くして死ぬ
  • 割り当てが"掃除"の直前だと、その"掃除"を生き延びる可能性が高い
• n~n+1 に注目
  • never copied: 既に死んでいる
  • copied once: ２回目の"掃除”(n + 2)時点で死んでる
  • copied twice: ２回目の"掃除”(n + 2)時点で生きている
• th=2 はかなり良い
  • 2 回生き残る確率は低い (1 回生き残る確率と比べて)
  • 生き残りを減らしつつ(-100%)、コピーコストを抑えている(+~50%)
• th=3 以上の効果は薄い [Ungar, 1984; Shaw, 1988; Ungar and Jackson, 1988]

7.3.3 The Standard ML of New Jersey (SML/NJ) collector #

• SML/NJ collector は promotion に関して異なったアプローチを取る [Appel, 1989b]
  • 実装が簡単だが、効果的で allocation の速い GC を作りたい
  • 2 つの gen. を使う
    • (young セルのコピーを最小限にするため)
    • new gen. はできる限り大きくしておく

動作:

1. major collection の後、old gen. によって使われていない heap を等しいサイズで 2 分割
   • free : allocation はここから
   • reserve : “掃除"時の生き残りのコピー先
2. new が locked に到達したら minor collection が起動
   • 生き残りはsvrとして固められる
3. minor collection 後のサイズが heap の半分になったら major collection が起動
   1. old gen. の"掃除”
   2. minor の生き残りの"掃除"
4. 生き残りを heap の bottom にコピー

Note:

• major collection
  → old(er) セル (=old + svr + …)が heap の半分近くになったら
  • コピー先の容量は保証される
• プログラムの heap 専有率を下げると GC のオーバーヘッドが小さくなる
  • 1:3 以下 : 11%
  • 1:7 以下 : 6%

7.3.4 Adaptive tenuring #

発生するトレードオフ:

• youngest gen. 小 → “掃除"間隔・停止時間の減少、promotion 増加
• youngest gen. 大 → “掃除"感覚・停止時間の増加、promotion 減少
  • 死ぬための期間が多く与えられる
• copying:
  • オーバーヘッド : “掃除"の頻度を落とす(=各世代のサイズを大きくする)ことで減少
  • 停止時間 : 各世代のサイズを大きくすると増加
• 以上より、promotion 戦略が固定だと平均的な性能しか出せない
  • しかも、GenGC の tuning は複雑で時間がかかる

promotion 戦略が固定だと平均的な性能しか出せない

• promotion 戦略が固定だと…
  • 閾値が大きい場合 (i.e. larger youngest gen.) : 停止時間が長くなる
  • 閾値が小さい場合 (i.e. smaller youngest gen.) : 不必要な promotion が生じる

demographic feedback-mediated tenuring ( by Ungar and Jackson )。

promotion 戦略を動的に変更する手法。

2 つのルール:

1. 必要な時だけ tenure させる
   • “掃除"を生き延びたセルの数は次回の"掃除"の停止時間の予測に使える
   • “掃除"を生き延びたセルの数が(基準より)少なかったら、promote させる意味は薄い
     • ∵ 次回の生き残りも少ないと予測できる → 短い停止時間
     • (停止時間は、生き残りの数に比例(コピーする必要があるから))
2. 必要な分だけ tenure させる
   • “掃除"を生き延びたセルの数が(基準より)多い → 次回の"掃除"の停止時間は許容を上回ると予想される
     • → 上回った分を次回の"掃除"のヒューリスティックとして使う
     • 次回の"掃除"で tenure

1 つ目のルールの具体例:

• 生き残ったセルの数は基準以下
  • 次回の"掃除"は許容時間以内に終わる可能性大
• → 次回の"掃除"では promotion は行わない

2 つ目のルールの具体例:

• 生き残ったセルの数は基準を 10kb 上回る
• 次回の"掃除"は許容時間以内に終わらない可能性大
  • → 次回の"掃除"では上回った分だけ promote
  • この効果は次次回から現れる

1excess = size(survivors) - max_pause_time
2if excess ≦ 0
3  threshold = ∞
4else
5  generate_table()
6  threshold = look_up(excess)

動的に境界を動かす方法

• 上記の Ungar と Jackson による方法
  • promotion の基準を動的に変更した
  • old gen. にある tenured ゴミに対処する方法がない (major collection を除いて)
  • (あくまで tenured にしないための方法)
• Barrett と Zorn による方法 [Barrett and Zorn, 1993a]
  • new gen. と old gen. の境界を動かせる (threatening boundary)
  • 以下を記録しておく必要あり
    • それぞれのセルの"age”
    • 全ての forward ポインタ(つまり、自分より若いものを指すポインタ)
      ∵ 境界が動くので、inter-generational pointer になり得るため
  • 両方向のチューニングが選択可能
    • 停止時間を短くするか、tenured ゴミを少なくするか

• 以下では、時間は bytes 単位で測る
• TB : threatening boundary

停止時間を短くする境界の動かし方

1if last_trace > max_trace
2  TB = Feedback_Mediation()
3else
4  TB = t - (last_t - TB) * max_trace / last_trace

• このアルゴリズムは minor collection 直前に走る
• if 節: 前回の"掃除"が許容時間を超えたので、youngest gen. を小さくする
• else 節: 前回の"掃除"が余裕だったので、youngest gen. を大きくし、より多く"掃除"する
  • イメージ図は以下
    • \( Mem_n\) : その時点でのメモリの使用量
    • \( Trace_n\) : “掃除"n で trace したサイズ
    • \( L_n \) : full collection n で 生き残ったサイズ
    • \( S_n \) : minor collection n で 生き残ったサイズ
    • \( Trace_{max}\) : 最大許容時間 (bytes)
  • \( TB_{n} \) の決定に注目
    • 4行目のmax_trace / last_traceが1以上であることに注意

自作図 間違っているかも

tenured ゴミを削減する境界の動かし方

Minor collection 直後を考える。

heap の構成:

• 生きているセル:
  • old gen. で生きているセル
    • 元から old gen. に居たセル
    • promote されたセル
  • new gen. で生きているセル
• 死んでいるセル:
  • old gen. で死んでいるセル
• free 領域

• tenured garbage のサイズ : heap_size - live
  • heap_size : heap の現在のサイズ (使用量)
  • live : heap 全体で生きているセルのサイズ
    • ただし、この live は minor collection だけではわからない
    • → 推定する
• live_est : live の推定
  • live_est = (last_trace + last_survivors) / 2
  • ???????
    • old gen. にいて生きているやつが無視されていない??
    • or 他の変数の解釈が違う??

1live_set = (last_survivors + last_trace) / 2
2tmp = t * (max_memory - live_set) / last_mem
3TB = min(tmp, last_t)

7.4 Generation organisation and age recording #

各世代内のセルの配置方法について見てていく

7.4.1 One semi-space per generation #

最終層のみを semi-space にし、他の層では 1 回で promotion させる

利点:

• コピー先の世代が ToSpace のように振る舞う
• youngest gen. が毎回 0 から使用可能 (毎回空になるため)
  • allocation が楽になる

ただし…

• 中間層が必要
  • promotion の基準が緩い → 若いセルが promotion されてしまう
  • それらを filter out する必要あり
• 世代間ポインタ増
  • → write-barrier コストの増

7.4.2 Creation space #

世代内を creation space と aging space に分割。

• creation space : セルの確保はここから
• aging space : 世代内の生き残りはここに (promotion されるか死ぬまで)

“掃除"間の動き:

• creation space と (aging spaceの)Fromspace の生き残りが Tospace にコピーされる
• Diagram 7.12 を参照

利点:

• creation space は 0 から使用可能 (毎回空になるため)
• creation space が物理メモリにも乗れば、locality 的にも嬉しい
  • swap out されないように注意を払う必要あり

7.4.3 Age recording #

ここではセルの"age"の管理方法について見ていく。

• “age” に基づいた GC を行うには"age"の管理が必要
  • セルごとに"age"の情報を持たせると
    • メモリを多く食う
    • “age"の更新に時間を使う
  • 各世代内を buckets に分割する方法 [Shaw, 1988]

• young gen. の世代内を 2 つの buckets に分割
  • New space
  • Old space
• n 回の"掃除"ごとに次の bucket or gen. にコピー
• セルの"age"を空間・時間オーバーヘッド無しに保証する

heap 内のレイアウト

• old gen. は heap の底から上に向かって成長
• new gen. は中が semi-space
  • semi-space 内を bucket に分割
    • 上側が creation space
    • 下側が aging space
• promotion のタイミング
  • データを(図の)上方向にコピーする時に
  • aging space は old gen.に取り込まれる
• generation と bucket の区別に注意
  • “掃除"の対象となった gen. 内の bucket は全て"掃除"対象

特徴:

• premature promotion が少ない
• メモリ的には Ungar の方法(1 つ前の方法)に劣る
  • younger gen. 内の繰り返しコピーが発生する

Wilson と Moher による方法:

• Ungar による方法と Shaw による方法の組み合わせ
• 3 gen. (ただし、図から中間層は省略されている)

• Creation space 内に bucket の境界(high water mark)を作る
  • bucket 1 の生き残り : aging space へ
  • bucket 2 の生き残り : next gen. へ
• Creation space 内は確保された順に並んでいる
  • high water mark 以下は十分に時間が経ったと考えて良い
• promotion の決定はポインタ比較で済む

High water mark について

• high water mark は動的に変更可能
  • コピー量が多すぎる時 : high water mark を低くする
  • セルに長生きの傾向がみられた時 : high water mark を低くする

利点:

• セル単位の “age” の管理が不要
• premature promotion が無い
  • あっても中間層でフィルターされる
• 理想的な promotion 基準
  • 基準は実質的に 1.5
  • 1~2 が理想
  • diagram 7.16 で確認

promotion 基準 (=1.5) の効果を確認

• 最も若いセル群を promote せずに
• コピーの総量を削減

7.16

7.6

7.4.4 Large object areas #

• 大きいセルは特別に扱うのが良い
  • コピーコストが大きいから
• header と body に分割
  • header は GenGC で管理
  • body は large object area に
• 効果は劇的
  • 330KB の large object area で停止時間が 1/4 に [Ungar and Jackson, 1988; Ungar and jackson, 1992]

Question #

• 世代の境界がB1、B2、B3、B4それぞれの時
  • 記録しておくべき世代間ポインタは？
  • minor collection を行ったらどうなる？

Answers #

B1

B2

B3

B4

B5