K.Sasada's Home Page

ライトバリア考察。

世代別 GC において、古い世代のオブジェクト（old objと呼ぶ）から新しい世代のオブジェクト（new objと呼ぶ）への参照があったら、うまく動かない（新しい世代だけ GC（マイナーGC）すると、本当は old obj から参照されているのだから殺してはいけないオブジェクトまで殺してしまう）のを防ぐため、ライトバリア（WBと呼ぶ）によって検出し、なんとかする。

なんとかする、には2通りあって、(1) old obj を覚えておくか、(2) new obj を覚えておく、という2通りがある。教科書には (1) old obj を覚えておいて、次のマイナー GC のとき、ルートとする、というのが圧倒的に多い。が、(2) new obj を覚えておいて、さっさと old にしてしまえばいい、という考えがある。どうせ、old obj から参照されるようなオブジェクトは、長寿命だろう、という話。次のマイナー GC のとき、new obj をきちっとマークすれば、別に問題無い。

では、なぜ (2) が無いのかと言うと、(i) moving GC で何か都合が悪かった気がする（違ったかな？　理由を思い出せない）。それから、(ii) 覚えるオブジェクトが (1) よりも多くなりやすい（例えば古い配列へ参照させた new obj が複数あった場合、その全ての new obj を覚えなければならない）。そして、(iii) 間違って短寿命オブジェクトを長寿命オブジェクトとしてしまう、という問題がある。

(iii) について、もう少し。

stack = []
# いろいろ動かして stack は old になる
while obj = stack.pop
  task(stack, obj) # task は複数のオブジェクトを stack に再度 push する
end

こんなよくありそうな幅優先探索のコードを考えてみると、入れたり出したりするオブジェクトを、短寿命なものをすべて old にしてしまう。(1) の場合は、GC 時にたまたま stack が参照していたオブジェクトだけ、old にする。なので、間違って短寿命のオブジェクトを old にしてしまう危険が少ない（ないわけではない）。なので、これを理由に（今の実装である）old を覚える、ということを続けようと思う。

MRI のことを考えると、(i) は moving しないので関係ないし、(ii) は、実は remember set をオブジェクト 1 つずつに持つ、bitmap で扱っているので、いくらでも増やせるから関係ない。

なので、(iii) の懸念が無ければ、(2) のほうが、色々楽かと思ったのでした。先日の PRO 研究会でも、似たようなことを聞かれて、明確に理由を答えられなかった気がするので、少し検討し直した次第です。

---

long lived WB unprotected object は長寿命オブジェクトと同じ顔をするべきであるか？　についての考察。

MRI では、WB unprotected object （長いね）というものを導入して、不完全な WB にも関わらず、安全に世代別 GC を行なっている。

この WB unprotected object は、

(1) 年をとっても old にならない (2) （マーク時に）old から参照されたら、long lived WB unprotected object になる（WB でこれを発見されても、次の GC 時に old から指されていなければ関係ない。これは、実は前節の話に関わる） (3) long lived WB unprotected object はマイナー GC では消えない (4) long lived WB unprotected object はマイナー GC 時にずっとルートになる

という性質がある。(3) の性質は、古い世代の GC と、まんま同じなので、これは古い世代なんじゃないの、という指摘をよく受ける。実装しながら考えてきたので、あまりまとまっていなかったのだけれど、これを「若い世代だ」と言い張る理由を考える。

ちなみに、MRI では若い世代のオブジェクトは、オブジェクトにくっついている年齢が 0〜2 歳までのオブジェクトで、古い世代のオブジェクトは 3 歳のオブジェクトである。1度GCを経過すると、すべての（WB unprotected object 以外の）オブジェクトの年齢は 1 ずつあがっていく。ただし、3 になると、もうこれ以上増えない（2ビットで表現している）。WB unprotected object の年齢は、ずっと 0 のままである。

年齢は、RBasic::flags に格納されているので、VALUE から取り出すのは非常に容易である（速い）。なので、出来れば年齢だけで、いろんなチェックが出来ると良い。

ここまでが前提。

さて、やはり WB() はやくなんねーかな、というのが話の発端である。ふつーの処理系だと、

def wb(a, b) # a->b の参照が生まれたときにチェック
  remember(a) if a.old? and b.new?
end

こんなコードになる。ここで、今は WB unprotected オブジェクトは new に見えるので、このチェックのままである。ただし、b が long lived WB unprotected object の場合、どーせ a から参照されなくても、ずっとマークされっぱなしであるので（上記 (3), (4) の性質から）、a を remember しなくても良い。これを実装すると、

def wb(a, b)
  remember(a) if a.old? and b.new? and !b.long_lived_unprotected
end

みたいになろうか。ちなみに、今は、そんなの滅多に無いんじゃ無いの、とたかをくくっており、!b.long_lived_unprotected の部分にあたるチェックはしていない（しても、勿論良い）。

さて、long lived WB unprotected object を old に、つまり age == 3 とする実装を考えてみる。a が長寿命、b が短寿命だとわかっても、a は long lived WB unprotected object である可能性があるので、もう一つチェックが必要である。

def wb(a, b)
  remember(a) if a.old? and !a.long_lived_unprotected_object b.new?
end

こんな感じであろうか。ただし、どーせ (4) の性質から long lived WB unprotected object から毎回マークするんだから、リメンバーセットに加えてやってもいいだろう。たいした手間じゃない（多分）。

つまり、現状の

def wb(a, b)
  remember(a) if a.old? and b.new?
end

で（チェックが足りないと、どちらも余分なことはしてしまうが）、あまり変わらん、ということが言える。

あれれ、若い方が良い、と言いたかったのに、どっちでも良い、になってしまった。

定性的なことを言うと、long lived WB unprotected オブジェクトは、あまり多くないはずなので、まー、どっちでも良い、といえば良いのだが、old にしてやったほうが、remember する old オブジェクトが減るので良い、といえるかもしれない。

CoW friendly 的には、flags は触らない方がいいので、良くないかもしれない...。

---

ああ、ダメな理由を思いついた。long lived WB unprotected オブジェクトは、マイナー GC の間はずっと生き残る long lived WB unprotected であるが、一度メジャー GC を行なうと、ただの WB unprotected object に戻らねばならない。具体的には long lived table が zero clear される。

この時、また old から参照されれば、無事（？）long lived WB unprotected object に戻るのだが、new や他の WB unprotected object から参照されて生き残っていると、そいつはただの WB unprotected object で無ければならない。

年齢を reset するには flags を変える、つまり heap_page を全部チェックして、書き換えていかなければならず、それは大変なコストになる（CoW frinedly 的にも良くない）。なので、現状の WB unprotected なら年齢 == 0 に固定、というのは理にかなっているということが言える。ということで、この件は、このままにしておこう。

---

長寿命と old という言葉が曖昧なので、もうちょっと整理できるか。

まず、2種類 WB protected と WB unprotected がいる。これをそれぞれ WBp, WBunp と略そう。

それから、WB protected には new と old が居る。old は年齢が 3 で、new は 2 以下である。

WBunp は、old から参照されたとき、long lived WBunp になる。これを llWBunp と略そう。

old も長寿命だと言える。実際、old と llWBunp は、long lived bit というのが真である。

なので、世の中を短寿命・長寿命、WBp と WBunp の2軸で分けられる。

• 短寿命 WBp - ふつーの短寿命オブジェクト。minor GC の対象になる。
• 長寿命 WBp - ふつーの長寿命オブジェクト。minor GC では（リメンバーされない限り）触らない。次の major GC までずっと生き残る。次の major GC では年齢 == 3 からスタート。生き残ればすぐに old。
• 短寿命 WBunp - 何回 mark されても年齢が増えない（0）。
• 長寿命 WBunp - 何回 mark されても年齢が増えない（0）。minor GC のたびに、root として毎回マークされる。次の major GC までずっと生き残る。major GC で短寿命 WBunp にリセットされる。

長寿命（long-lived）って書くから良くないのかな。minor mark 時では不死、って意味なので、temporal 不死、みたいな名前がいいのか。なんだそれは。

---

long-lived だと、長く生きた、だけど、ここで意図したいのは、長く生きる（少なくとも、次の major GC まで）、なんだよな。消せない、的な。force_marking とかの名前がいいのかなぁ。noncollectable という言葉がいいか。

• collectable new WBp
• noncollectable old WBp
• collectable WBunp
• noncollectable WBunp

どうだろう。分かりやすいかな。

uncollectable なのか noncollectable なのか uncollectible なのか noncollectible なのか、どっちがいいんだろう。

---

keep alive bits にして、keep alive WBunp にするか。なので、

• new WBp
• old WBp (keep alive)
• WBunp
• WBunp (keep alive)

的な。対義語が出ないのがアレだけど。

1単語にするなら、kept alive WBunp になるんだろうか。

---

kept alive objects という表現が正しいかわからなかったので、この案は無しかなぁ。uncollectable / uncollectible がいいのかなぁ。