ガベージコレクションのアルゴリズムと実装 3,4章

Shinichi Tokunaga @deepneko

第三章: 参照カウント(Reference Counting)

Shinichi Tokunaga @deepneko

オブジェクトの被参照数を表すカウンタを使って、人気不人気を表現しましょう！

Shinichi Tokunaga @deepneko

アロケーションの流れは基本的にマークスイープと同じ。

Shinichi Tokunaga @deepneko

指定したサイズ以上のチャンクをフリーリストから探して、見つからなかったらallocation_fail

Shinichi Tokunaga @deepneko

見つかったらそのチャンクを返すんだけど、そのときにref_cnt(参照カウント)をインクリメントする。

Shinichi Tokunaga @deepneko

あ、この章だと、オブジェクトは「カウンタ : フィールド」という形で話を進めます。(カウンタ=ref_cnt)

Shinichi Tokunaga @deepneko

嘘つきました。ref_cntをインクリメントするんじゃなくて、1にします。

Shinichi Tokunaga @deepneko

update_ptrってのが出てきたんだが…ミューテータがオブジェクトのポインタを更新するタイミングはいつだ？

Shinichi Tokunaga @deepneko

ポインタの更新は、カウンタのインクリメント処理→デクリメント処理

Shinichi Tokunaga @deepneko

インクリメントは簡単。オブジェクト渡してカウンタをインクリメントするだけ。

Shinichi Tokunaga @deepneko

デクリメントは少しだけ複雑。

Shinichi Tokunaga @deepneko

ポインタ(オブジェクトの)を渡して、カウンタをデクリメントする→カウンタが0だったら、子オブジェクトも踏査して同様にデクリメント処理。

Shinichi Tokunaga @deepneko

そんで一番最初に渡したポインタはフリーリストに連結されるわけ。

Shinichi Tokunaga @deepneko

これ、ソースか図見ないと絶対わかんなそうだｗ

Shinichi Tokunaga @deepneko

お、ポインタの更新タイミングについて(update_ptrがいつ呼ばれるのか)について書いてあった。

Shinichi Tokunaga @deepneko

「ポインタの更新は、例えば配列の要素を更新するときに行われます」

Shinichi Tokunaga @deepneko

ふーむ。ということは、色んな処理のあとにupdate_ptrが挿入されてるってことか。参照カウントの実装ってあんまり綺麗なものにならなそうだね。

Shinichi Tokunaga @deepneko

参照カウントはメモリ管理をミューテータと並行して行うので、アロケーション時にチャンクがなかったら、新たにオブジェクトを割り当てることができません。

Shinichi Tokunaga @deepneko

マークスイープとの大きな違い。(マークスイープはゴミはいったん放置しておいてチャンクが無くなったら回収)

Shinichi Tokunaga @deepneko

参照カウントのメリット①: ゴミがすぐ回収できる。

Shinichi Tokunaga @deepneko

他のGCだとチャンクがなくなってGCが走って初めて、ゴミかゴミじゃないかがわかる。つまりGCが走るまではゴミがメモリに残る。

Shinichi Tokunaga @deepneko

参照カウントのメリット②: ゴミが生成されるたびにゴミだけ回収するので、ミューテータの最大停止時間が短い。

Shinichi Tokunaga @deepneko

参照カウントノメリット③: ルートからポインタをたどる必要がない。

Shinichi Tokunaga @deepneko

分散環境において、計算ノード内では参照カウント、ノード間にはマークスイープ、という手法が一般的。

Shinichi Tokunaga @deepneko

ノード間…グローバルGCなんてあるのか。これは質問したいところ。