SGenを詳解してみるシリーズ

原文1原文2原文3

更新 2011/02/27 fililさんからのご指摘でtypoを修正。TODO部分に対して、考えていただいた訳を反映。

更新 2011/02/14 miura1729さんからのご指摘で誤訳を修正

翻訳: 中村 成洋

SGen

SGenは、我々が2年間熱心に取り組み、ここ数ヶ月の間で安定性と十分な競争力を持ってきた、Monoの新しいGCです。

これからの一連のブログの記事として、このGCの一般的な働きと、特別な働き、どのようにしてこのGCがベストな性能をえられるかを紹介し、そして最後に未来のプランを説明します。

なぜ新しいGCなのか?

多くのGC付きのランタイムのように、Monoは開発当時からBoehm-Demers-Weiser collectorを使っていた。以降、これをBoehmと略します。 Boehmの基本的な利点は移植性と安定性があり、楽に組み込むことができる点です。 このGCはCとC++用に設計され、言語を扱うもののためではありません。 なので、言語処理系やランタイム用のGCに比べると不十分な点もあります。

我々の目標は、Boehmの限界を克服し、扱うアプリケーションのアロケーション速度やGC停止時間やメモリ利用に関する性能をよりよくすることです。 この記事、またこれからの記事では、適切な箇所と思う所でBoehmよりも改善された点を述べていきます。

Garbage Collection

SGenの詳解の前に、GCがどのように働くのかの議論を見ておきましょう。 SGenに関連するトピックについて幅広い範囲を簡単に述べます。 GCについて、もう少し広範囲の概要を知りたければ「Uniprocessor Garbage Collection Techniques by Wilson」を読んだり、もう少し詳しく知りたければJonesとLinsの本*1を読むと良いでしょう。

GCは要するに、割り当てられているメモリ中の空きオブジェクトを見つける明確な方法がないにも関わらず、メモリを消耗してしてしまうプログラムを動作し続ける、言語やプラットフォームのランタイムの一部のことです。 GCはプログラムからいまだに参照されている(かもしれない)オブジェクトを見つけることによって、使用されていないオブジェクトを取り除きます。 いわゆる「ルート」によって直接的、間接的に参照されているものを到達可能なオブジェクトと考えます。 具体的にルートとして登録されるのはグローバル変数、スタック上のローカル変数、レジスタ、その他の明示的な参照です。 いいかえれば、これらの全ての到達可能と考えられるオブジェクトは、ルートから参照されるオブジェクト、そのオブジェクトが参照するオブジェクト、その参照するオブジェクト…ということになります。 物知り顔の人は、正確にはプログラムはすべてのオブジェクトには届けないと注意するでしょう。 プログラムが参照した最小オブジェクト数を求めることは不可能です。 そして、幸いにも我々はそのことをこの男のお陰で知っています。

SGenはBoehmと同じく「停止型(Stop The World)」のGCです。 この意味はプログラム(GCの世界では軽蔑的な呼び方として「ミューテータ」と呼ばれる*2)を停止するということです。

3つの古典的なGCアルゴリズムがあります。マーク・スイープ、コピー、コンパクションです。 このうち最初の二つはSGenの議論に関連します。 コンパクションを実装していませんし、将来的にもその計画はないため、コンパクションはSGenと関連ありません。

マーク・スイープ

マーク・スイープは最古のもっとも幅広く実装されていると思われるGCアルゴリズムです。 Boehmもマーク・スイープを実装しています。

アイデアとしては、すべてのオブジェクトに「マーク」ビットを持たせておき、「マーク」フェーズにてルートセット参照される点を起点に、再帰的にすべての到達可能なオブジェクトのマークビットを立てていきます。 もちろん実際には厳密な再帰の実装ではなく、キューやスタックを利用して実現します。

「スイープ」フェーズでは、マークされていないメモリを占有しているオブジェクトを解放し、マークされたビットはリセットします。

もちろん、細部が変更されているこのアルゴリズムの亜種は存在します。

コピー

伝統的なマーク・スイープは主要な2つの欠点があります。 まず、すべてのオブジェクトを辿る必要があります。この中には到達不可能なオブジェクトも含まれます。 次に、malloc/freeとアロケータのようにメモリフラグメンテーションを引き起こす可能性があります。

コピーGCは新しい記憶領域にすべての到達可能なオブジェクトをコピーし、この2つの問題に取り組みます。 コピー後は、次々と線形にアロケーションしていきます。 コピー前の領域は大規模に捨てることができます。 古典的なコピーGCはヒープが2つに分割される「半空間(semi-space)」アルゴリズムと呼ばれるものです。 線形のアロケーションは半分のヒープがいっぱいになった時に終了し、もう一つの半分のヒープに到達可能なオブジェクトをコピーします。 アロケーションはここに行われるようになり、空になったもう半分のヒープは「To空間」と呼ばれ、次のGCの際にコピー先として使われます。

コピーGCによってオブジェクトは移動するためアドレスが変わります。そのため、これらのオブジェクトへの参照すべてを更新しなければなりません。 しかし、Monoの場合はすべて更新可能ではありません。 なぜなら、すべてのケースでメモリ上の値(大抵はスタック内の値)が参照か、偶然にオブジェクトのアドレスと同じ数値か、明確に識別できないからです。 この問題の対処については、この一連の記事の後の方で議論します。

世代別GC

オブジェクトの大多数は早く死ぬか、非常に長い時間生きることが観測されています。 ヒープを2つに分ける、もしくはもっと多くの「世代」に分け、これらを違う頻度でGCすることで、いわゆる「世代的仮説」の利点を取ることができます。

オブジェクトは、第1世代(苗床(nursery)とも呼ばれます)で、その一生がはじまります。 彼らがなんとか十分に長く留まることができたならば、彼らは第2の世代、もしくはその他の世代に「昇進(promote)」します。 すべてのオブジェクトは苗床で生まれるため、苗床内のオブジェクトは急速に増えていきます。 そのため、GCをしばしば動かす必要があります。 世代的仮説が保たれるならば、それらのオブジェクトのほんの一部だけが次世代にたどり着くため、次世代のGCは頻度が低くてすみます。 また、苗床のオブジェクトのほんの一部だけが生き残り続ける間は、ヒープの割合は古い世代が高いと思われるため、より高い生存率に適したGCアルゴリズムをそれらに使うことができます。 いくつかのGCでは、これらのオブジェクトを「殿堂入り(tenure)」とまでして、これらの不死身のもの見なし、これらによってGCの負担がかからないようにします。

世代別GCの難点は、ミューテータが旧世代に新世代への参照を保存したかもしれないために、旧世代をまったく見ず新世代のみをGCすることができないということです。 旧世代から参照された若いオブジェクトが他のどこから参照されないとしても、それは生きていると見なされなければなりません。 そのような参照のために旧世代領域のすべてを調べたのでは、旧世代と新世代にわざわざ別れされた意味がありません。 世代別GCではこの問題に対処するために、旧世代から新世代へのすべての新しい参照をミューテータに記録させます。この記録は「ライトバリア(write barrier)」と呼ばれます。詳しくは後の記事で説明します。 書き込みの代わりに読み込みを記録する「リードバリア(read barrier)」によっても代用可能ですが、これはハードウェアサポートなしでは実用的ではありません。 すべてのフィールドへの参照の書き込みや、配列の要素の書き込み時などにライトバリアは起動するため、ライトバリア自体はとても効率的でなければなりません。

SGen

SGen(それは歴史的に「単純な世代別(Simple Generational)」を表します)は、2世代をもつ世代別GCです。 苗床はコピーGCによってGCされ、生きているオブジェクトを可能であればすぐに旧世代(もしくは「メジャーヒープ」)に昇格させます。

旧世代にはユーザが選択可能な2つのGCがあります。マーク・スイープGCとコピーGCです。 マーク・スイープGCはさらに4種類の、並行マークあり・なし、固定・動的ヒープサイズが利用可能です。

それに加えて、SGenは大きなオブジェクト(8000バイトより大きい)のための隔離された空間を持ち、これを「大きなオブジェクト空間(Large Object Space)」か「LOS」と呼びます。 これは論理的に旧世代の一部となります。 大きなオブジェクト群は苗床内には生まれず、LOSに直接入れられます。そして、これらは移動しません。

SGenが対処しなければならない1つの主な困難は「ピン付け(pinned)」オブジェクトです。 そして、それは彼らが動かされることができないことを意味します。 ピン付けになる理由は大体がスタックフレームから参照されて起こります。 スタックフレームは「正確」に調べることができない、つまり、中の値が参照なのか、それ以外なのかを見分けることができないものだからです。 現在、管理されたスタックフレームに正確性をもって調べれるように取り組んでいますが、それでも型情報が利用できずに、「保守的」にのみ調べることができる、管理されていないスタックフレームを常に扱わなければなりません。 続きは後の記事で。

これからの連載リスト

GCの2、3の基本的な概念を抑えたので、私はこのあとの連載でSGenについてより多くの詳細を書いていこうと思います。 以下は私が今後数週間で書こうと思っている記事のリストです。コメントや提案はもちろん歓迎です。

オブジェクトアロケートとマイナーGC

苗床の構造、どのようにオブジェクトがアロケートされるか、どのように苗床はGCされるか。

メジャーGC

SGenのメジャーGCであるマーク・スイープ、コピーの概要。 これらがどのようなヒープ構造をしていて、どのようにGCするかを述べようと思います。

いろんなこと

いくつかの短いトピック

GCのデバッグ

GCのバグを見つけるのは難しいです。ばかげてると言えるほどに。 ここではそのアシストをしてくれるツールを詳解しようと思います。

SGenのベストな性能を引き出すために

負荷におけるいいチューン方法。 どのようにアプリケーションを書けばSGenのパフォーマンス特性を引き出せるか。

未来

SGenの未来について、何か考えがありますか?

SGen 苗床

この記事はこのブログの一連の記事(Monoの新しいGCについてのもの)の一部です。 今回の記事では第1世代である「苗床(nursery)」について詳解します。

苗床

この名前が示すように苗床はオブジェクトが「アロケートされる」場所、もうすこし詩的にいえば、「生まれる」場所となります。 SGenでは隣接する細かい領域をSGen開始時にメモリからアロケートします。細かい領域のサイズは変更しません。 デフォルトサイズは4Mバイトですが、Mono起動時に環境変数の MONO_GC_PARAMS を指定することで変更可能です。 詳しくは man ページを見てください。

アロケーション

古典的な半空間GCのアロケーションはポインタをずらすことで線形に割り当てられます。 つまり、現在の半空間領域の先頭を指すポインタを必要な分だけ単純にインクリメントして、未使用のメモリ領域を新しいオブジェクトとして割り当てます。

1つのポインタをMonoのようなマルチスレッドの環境で使用すると、コストが発生する。 なぜなら、少なくともインクリメントの際にコンペア・アンド・スワップ(CAS)しなければならず、それは、競合のために失敗するかもしれないため、ループしてしまう可能性をはらんでいる。 この問題に対する標準的な解決方法は、排他的に使用でき、他のスレッド競争なく「ずらしたアロケーション」を可能な、苗床内の小さな領域を、すべてのスレッドに与えることです。 同期が必要なタイミングは、スレッドがその領域を使い果たしてしまって、新しい領域を必要とするときのみであり、それ以上の頻度でおこないません。 この苗床の小さい領域は「TLABs(Thread local allocation buffers)」と呼ばれます。

TLABsはスレッドにゆっくりと割り当てられます。 関連性のあるポインタ、特に「ずらすポインタ」とTLABsの終端のポインタはスレッドローカルな値として保持されます。 現在のTLABsは4Kバイトのサイズに固定されます(正確にはこれは最大サイズで、苗床のフラグメンテーションによっては小さくなるかもしれません)。 将来的には状況に適するようなサイズを動的に決めるようにするかもしれません。 少数のスレッドだけオブジェクトのアロケーションが行われており、頻繁ではないものの、TLABsを越えて新しいTLABsを割り当ることがあるとします。 一方で、その他のスレッドはTLABsを割り当てはするものの、その苗床領域を使い切らないとします。そうすると、時期尚早にGCを開始しなければなりません。 その状況では、TLABsがより小さくなければいけません。 理想的には、スレッドは、アロケーション比率に比例したTLABsサイズを得るのがよいでしょう。

マネージドコード*3からアンマネージドコードを呼び出し実行する際の移り変わりには、相対的にコストが伴います。 これを避けるための高速なアロケート関数はマネージドコードです。 これらはTLABからのアロケートを扱うだけです。 もし、スレッドがTLABを持っていない、もしくはユーザの要求サイズを満たせるほどの空きがない場合は、完全にアンマネージドなアロケート関数を呼び出します。

GC

苗床のGCの動作原理はメジャーGCとほとんど変わりありません。 ここで私が述べるものは多くはその点に有効なものです。

塗り絵

GCのプロセスは「塗り絵ゲーム」とみなすことができます。 すべてのオブジェクトは白としてGCをはじめます。 はじめにすべてのルートから直接参照されるオブジェクトを灰色に塗ります。 灰色は、到達可能なオブジェクトであることと、そのオブジェクトの内容についてはまだ処理されていないことを示します。 それぞれの灰色のオブジェクトから、さらなる参照をスキャンします。 スキャンで見つけられたオブジェクトがまだ白いならば、それを灰色に塗ります。 灰色のオブジェクトのスキャンが終わったとき、そのオブジェクトを黒色に塗ります。 黒色は到達可能なオブジェクトであることと、完全に処理されたことを意味します。 灰色のオブジェクトがなくなるまでこれは繰り返され、すべてが終了すると、黒いオブジェクトと白いオブジェクトに別れます。黒いオブジェクトは到達可能であることを意味し、白いオブジェクトは到達不可能なことを意味するため、これを処分することが出来ます。

このプロセスの中心的なデータ構造のうちの1つは「灰色セット(gray set)」(つまり、すべての灰色オブジェクト)です。SGenではこれをスタックで実装します。

ルート

以降の話題は前回の概要の記事の繰り返しになります。GCはルートを起点に始まります。 ルートの主な要素は、すべてのマネージドスレッドのスタック内にある参照と、staticなクラスのフィールドです。 これらに加えて、数値である可能性のあるルートは、ランタイムのレジスタと、内部で使用する目的のものがあります。 SGenは世代別GCですから、苗床GCのルートには旧世代ヒープからのすべての参照も含まれます。 これはライトバリアによって維持されます。この件については、後の記事で説明します。

フォワーディング

SGenの苗床GCはコピーGCのようなものです。 到達可能なオブジェクトは苗床から旧世代にコピーされます。 これは色を塗る際に一緒にコピーされることを暗示しています。 その場合は、そのオブジェクトへの参照をすべて更新しなければなりません。 そのためには、すべてのオブジェクトのコピー先を探知し続けなければなりません。 その簡単な方法は、フォワーディングポインタを使うことです。 Monoでは、すべてのオブジェクトの最初のワードはオブジェクトのvtableへのポインタになっており、これは最小4バイトでアラインメントされます。 アラインメントによって最小2ビット離れているというのはSGenのGCを行う間に重大な意味を持ちます。 なぜなら、我々はこのビットを、そのオブジェクトがフォワーディングポインタであることを指し示すために使うからです。 フォワーディングポインタであるということは、つまり、すでにそのオブジェクトはコピーされたということです。 このビットが設定されると、最初のワードはvtableを指さなくなりますが、その代わりに旧世代の新しいオブジェクト位置を指すようになります。 2つめのビットが何に使われているかについては後述します。

ループ

以下に苗床GCの主要なループの簡単な(ピン付けの扱わない)擬似コードを示します。

01:  while (!gray_stack_is_empty()) {
02:      object = gray_stack_pop();
03:      foreach (refp in object) {
04:          old = *refp;
05:          if (!ptr_in_nursery(old))
06:              continue;
07:          if (object_is_forwarded(old)) {
08:              new = forwarding_destination(old);
09:          } else {
10:              new = major_alloc(object_size(old));
11:              copy_object(new, old);
12:              forwarding_set(old, new);
13:              gray_stack_push(new);
14:         }
15:         *refp = new;
16:     }
17:  }

2行目では、灰色スタックからオブジェクトを取り出し、そのオブジェクトの中のすべての参照を要素に3行目のループを回します。 refp は参照をもつオブジェクトのフィールドのアドレスです。4行目で本当の参照を取り出します。 苗床をGCする中での唯一の興味深い点は、その参照がすでに旧世代を指していた場合は、これを無視することです(5、6行目)。 もし、オブジェクトがコピー済み(forwarded)(7行目)であれば、フォワーディングポインタからコピー先のアドレスを取り出します(8行目)。 そのほかは、必ず旧世代にコピーします。 そのため、新しい領域を割り当て(10行目)、コピーし(11行目)、コピー元のオブジェクトにフォワーディングポインタを設定します(12行目)。 新しくコピーされたオブジェクトは必ず処理されなければなりませんので、これを灰色スタックに積みます(13行目)。 最後に、これはどちらのケースでもなのですが、オブジェクト内の参照をコピー先の新しいアドレスに更新します(15行目)。

ピン付け(Pinning)

概要を述べた記事で、スタックフレームは正確なスキャンができないことを話題に上げました。 これは、参照が偶然そのように見えていて実は違うのか、正しいものなのか、そのどちらであるかを我々は知ることができないからです。 マネージドスタックフレームは正確にスキャンできるようにする作業は現在進行中ですが、アンマネージドフレームについてはどうやったってできないでしょう。 なぜなら、Cコンパイラが我々に必要な情報を提供してくれないからです(いくつかのランタイムではGCに管理されるべき参照をアンマネージドコードに直接いれない方法でこの問題を回避しています)。

必要な情報が欠如しているため、我々は保守的にその値を参照と見なさなければなりません。 つまり、その値から参照されているオブジェクトは到達可能であると見なすと言うことです。 一方、これによって参照だと想定されているものの値を変更できなくなります。なぜなら、その値は数値であるかもしれないからです。 これはつまり、オブジェクトが移動できないことを意味しています。 言い換えれば、このオブジェクトは「ピン付け(pinned)」です。

ピン付けオブジェクトはいささか面倒な事態を引き起こします。 苗床にピン付けオブジェクトをもつことは、苗床をすべてクリーンにすることができないことを意味し、これはフラグメンテーションを引き起こします。 また、先ほど説明した擬似コード(主要なループ)に、ピン付けオブジェクトのチェックが必要になります。

最後の仕上げ

すべてがコピーが終了した後、次回からのアロケーションのために苗床をクリーンアップしません。 SGenは、このタイミングにおいて苗床のメモリ領域を0にしません。 その代わり、0埋めはTLABsがスレッドに設定されるときに実行します。 この利点は、0埋め処理の負荷が潜在的に複数のスレッドに分散されることだけではありません。 これはキャッシュの振る舞いをよりよくします。そのスレッドがすぐにTLABを触れる可能性が高いためです。

という話もありますが、ここで大事なのは、苗床内のピン付けオブジェクトを避けて、アロケーションに必要な領域分をしっかりと確保しなければならないということです。 それを行うために、すべてのピン付けオブジェクトのリストを持っており、これは非常に効率的です。 この「ピンキュー(pin queue)」については以降の記事で述べようと思います。 次回のミューテータ実行時にTLABsを設定する際にはピン付けオブジェクトを避けなければならないため、フラグメント(fragments)してしまいます。

また、フラグメントを作ってしまう要因となるものはもう少しある、ということを話しておきましょう。 オブジェクトが到達不可になったときに、ファイナライザをもつオブジェクトのファイナライズが走ったか、弱参照がゼロにされたかを、確認しなければなりません。 どちらも非常に似た問題なので、これについてもあとの記事で述べることにしましょう。

SGen メジャーGC

SGenを詳解してみるシリーズ最後の記事では、Monoの新しいGC、特に新世代(我々はこれを苗床(nursery)と呼んでいますが)のGCについて話しました。 今回の記事では、旧世代の2つの異なるGCの実装について話していきましょう。

前は2つの中でもコピーGCをよく使っていました。 しかし、最近、実践的な場面でよく利用されるのはマーク・スイープです。 これは多くのケースにおいて性能面がよりよく、空間効率もよくなるためです。

Monoのmanページには環境変数 MONO_GC_PARAMS の仕様の説明と、値をどのように変更すればよいかが書かれています。

コピー

メジャーなコピーGCはとてもシンプルなものです。 一つの大きな連続したメモリ領域を使用する代わりに、固定サイズのブロック(128Kバイト)を使用し、そのブロックを要求に応じてアロケーションしたり、解放します。 これらブロックのアロケーションは、内部ではポインタをずらすことで実現します。

メジャーGCでは可能なすべてのオブジェクトを新しくアロケーションしたブロックにコピーします。 ピン付けされたオブジェクトはもちろんコピーできませんので、その場に留まります。 完全に何もなくなったブロックは解放されます。 ピン付けオブジェクトを含むブロックは、現在の空きの領域を0埋めします。 実はブロック内の0埋めした領域は再利用しません。 ただし、オブジェクトのピンが取れるまではブロックはその状態を維持します。 この辺りは何らかの改良が可能でしょう。

なぜ二つのGCを?

コピーGCが実装されたのはSGenの初期の話です。 多くの部分を苗床GCと共有しているため、実装自体も簡単に済ませています。 これは製品として公開しているGCではありますが、多くの利用したいシーンではうまく性能がでないでしょう。 旧世代にあるオブジェクトは大きく、長生きである可能性が高いため、これらをコピーすることはメモリの観点から見ると効率が悪いでしょう。 コピーすることで2倍近くのメモリを必要としますし、キャッシュの働きを考えてもあまり良くありません。

マーク・スイープ

SGenのマーク・スイープは標準のメジャーGCであり、活発に開発・改良が重ねられています。

マーク・スイープは、コピーGCとは対照的に、特定のオブジェクトが解放され、新しく作られるときは同じ領域に詰められる(これは、コピーGCのピン付けオブジェクトを残すことによってブロックに出来てしまう穴とは異なります。なぜなら、この場合はピン付けオブジェクトによって残ってしまう領域は最小に抑えられるだろうと考えられるためです。そのため、全体の空き領域はかなり多くなります、が、長生きするオブジェクトによって所々の小さい穴は増えてしまでしょう)。 これはフラグメンテーション問題を引き起こします。多くのオブジェクト間の小さい穴が埋められないままになり、結果的に多くの領域が使えなくなってしまいます。

ブロック

SGenのマーク・スイープの基本的な考えは、固定サイズのブロックを持つことです。 それぞれのブロックは、等しいオブジェクトスロットをもち、そのスロットサイズはそれぞれのブロックで異なります。 このオブジェクトのアロケーション方法の利点は穴のサイズがブロック内において常に等しいサイズになることです。 そのため、新しいオブジェクトがどこかの穴のサイズと同じである場合は、すぐにそこにアロケーションできます。

もちろん、すべてのオブジェクトのサイズがブロックのサポートするサイズに適応するわけではありません。 そのため、サポートされたサイズと異なるケースでは、なるべく近いサイズをサポートしているブロックにアロケーションします(将来的には使用用途に適応するようなサイズを動的に選択できるようにするかもしれません)。 また、スロットサイズが固定であることのもう一つの利点は、オブジェクトの始まりと終わりの場所を明確に保持しなくても良い点です。 メモリ局所性の恩恵を得るために、ヒープとは別の領域にオブジェクトと1対1で対応したマークビットが必要になります(苗床GCがやっているような、オブジェクトの先頭のワードのビットを使わなければよりよいのですが)。 これを早く処理するため、1ビット8バイト対応のビットマップを用意し、そのビットはオブジェクトの先頭となる可能性がある地点と対応しています。

限られた数の異なるサイズのスロットを持っているため、フリーリストも同じように種類分けすることができます。 そのため、アロケーションは検索の必要が無く、非常に効率的です。

GCの間、オブジェクトのマークビットへアクセスする必要があります。 ブロックのサイズは16Kバイトであり、これらは16Kバイトの境界線上でアロケーションされるため、ブロック内のオブジェクトの相対的な位置は論理的な AND で簡単に求めることができます。 しかし残念なことに、大きなオブジェクトはブロックの外にあります。そのため、これに偽りのブロックアドレスを与えます。 大きなオブジェクトかどうかを決定するために、vtableから参照されるクラスメタデータを調べる必要があります(GCの「固定ヒープ」を変化させたものは、この問題を解消します。詳細は後述します)。

すべてのブロックは「ブロック情報(block info)」というデータ構造を持ち、これはブロックのメタデータを含んでいます。 また、オブジェクトスロットのサイズやその他データの一部とは別に、マークビットが含まれています。

固定ヒープ

標準的なマーク・スイープGCではブロックが必要な際に、割り当て可能なバラバラののアドレス領域から要求に応じてブロックをアロケーションします。 一方、固定ヒープの変化系では、起動時に固定サイズのヒープをアロケート(mmapを使う)しておいて、その空間にブロックを割り当てていきます(大きいオブジェクト空間を除く)。 この利点はあるポインタがブロック内にあることを判断する際に、わざわざマークビットを見に行かなくても、その空間内にあるかどうかだけを見ればよい点です。

標準的なマーク・スイープではそれぞれのブロックの先頭のワードはブロック情報へのリンクになっています。 固定ヒープの場合はこのような読み込みをしなくてすみます。なぜなら、固定ヒープ内のブロックは連続しており、ブロック情報を得るためにはインデックスのみわかればよいからです。インデックスはブロックのアドレスから定義されます。

固定ヒープによるマーク・スイープの明らかなデメリットは、固定サイズを超えてヒープを拡張できない点です。 ただ、いくつかの使用用途では、固定ヒープは重大なパフォーマンス改善を生み出します。 それらいくつかベンチマーク結果については、後の記事で紹介しようと思います。

参照を持たないオブジェクト

参照をもたないオブジェクトはスキャンされる必要がありません。 それはつまり、灰色スタックにオブジェクトを入れなくても良いということです。 これらを効率的にマーク・スイープで扱うために、参照を持たないオブジェクトを別のブロックに分離します。 ブロック情報には、そのブロックがどのタイプであるかのフラグを持っています。

固定ヒープGCにおける分離の意味は、オブジェクトが参照を持っていない場合にオブジェクトの1ワードを読み込まなくてよいということです。

退避

決められたオブジェクトサイズに従ってブロックを分離しているにもかかわらず、まだメモリを無駄にしてしまうことはあります。 もし、特定のサイズのオブジェクトを多く持った後に、そのサイズが少なくなるような使用用途では、そのオブジェクトサイズのためのブロックは非常に少ない領域しか使用しなくなってしまいます。

SGenはBoehmとは違ってオブジェクトを方々にコピーする自由があります。 GCのスイープの間、すべてのスロットサイズの使用領域に関する統計を保持します。 もしスロットサイズの使用領域が閾値(ユーザが定義可能)を下回ることがあれば、そのスロットサイズを次のメジャーGCの際の退避対象としてマークします。

退避対象のスロットサイズのブロック群を退避するとき、マーク・スイープではコピーGCのようにブロック内のオブジェクトを扱います。 それらをマークする代わりに、新しくアロケーションされたブロックへコピーするのです。 オブジェクトをブロックへ連続して詰めていき、ブロックを空にします。 その後、スイープによって、まばらに割り当てられていたブロック(現在は空になっているもの)を解放します。

ピン付けオブジェクトを含むブロックはどちらにせよ解放されないので、このすべてのプロセスから免除されています。

使用状況はスイープと次のメジャーGCの間で変わることに注意すべきです。 使用用途によってはその間にそのスロットサイズに非常に多くのオブジェクトがアロケーションされてしまい、その場合はすべてがコピーされてしまうため、どの空間も救うことができません。 SGenはマークフェーズ実行をしなければオブジェクトが生きているかどうかを見分けることができないため、その問題が起こるリスクをとらざるおえません。

ちなみに。 SunのGarbage-FirstGCはその問題をマークフェーズをミューテータと並行に走らせることで解決しています。 そのため、GCの停止処理のはじまりでどのブロックが多くのゴミを含むかについて見分けることができます。

並列マーク

マークフェーズは適切な動作で並列実行することができます。 基本的にいくつかのスレッドは独立してそれぞれ1組のルートオブジェクトから処理をはじめます。 それぞれのスレッドは灰色スタックを持ちますが、他のスレッドと重複してオブジェクトを処理しないようにしなければなりません。 2つのスレッドは同じオブジェクトのマークを競争することができます。 もし、オブジェクトが両方のスレッドの灰色スタックに入っても、それは二回スキャンされることを避けます。

オブジェクトがまだ苗床にある場合は取扱にいくつか気をつけなければなりません。 これらは旧世代ヒープにコピーされる必要がありますし、その後でフォワーディングポインタが設定されなければなりません。 フォワーディングポインタはメジャーヒープにコピー先のスペースがアロケーションされた後に設定されます(でなければ、どこをさすのだろう?)。 そして、2つのスレッドは独立してそれをおこなうかもしれません。 その場合は、1つスレッドのみが勝ち、ほかは無駄にアロケーションをおこなうことになります。

実はワーカスレッドの間でルートオブジェクトのセットを分割するというのはあまりよくありません。 いくらかのスレッドは処理するのに十分なオブジェクトグラフを持っていないかもしれないからです。 現在、SGenではワーカスレッドの灰色キューの一部を共有の灰色スタックのバッファに預けます。 これは他のワーカスレッドが取ることができます。

並列マークはいくらかの使用用途で劇的なパフォーマンス向上を見せましたが、しかし、ほとんどのケースではまだ満足いく結果は得られていません。 個人的にはワーカスレッドの仕事量の分配について改善する必要があると疑っています。

並行スイープ

スイープフェーズではシステム上のすべてのブロックを走査し、マークビットをリセットし、解放対象のオブジェクトスロットを0埋めし、フリーリストを再構築します。

実はそれらのデータ構造は苗床GCまで必要ではないので、スイープはミューテータのバックグラウンドで走らせることができます。このマーク・スイープは任意に実行することができます。 この場合、次の苗床GCはスイープスレッドの処理が終了するまで待ちます。

翻訳者コメント

翻訳は、中村 成洋<authornari _at_ gmail.com> が行ないました。

もしも、誤植や誤訳などがありましたらお気軽に @nari3までお知らせください。

Copyright (C) 2011 中村成洋


*1訳注:拙著『ガベージコレクションのアルゴリズムと実装』もオススメ http://amzn.to/9ZkKMY
*2訳注:たぶん著者は突然変異とかそんな勘違いしてるような。オブジェクトの参照関係を変更するもの(mutator)という意味です。
*3訳注: http://e-words.jp/w/E3839EE3838DE383BCE382B8E38389E382B3E383BCE38389.html のことかな