Garbage Collection in Julia

Introduction

Juliaは、非移動型、部分的に同時、並列、世代別で、主に正確なマークスイープコレクタを持っています（CからJuliaを呼び出したいユーザーのために、保守的なスタックスキャンのインターフェースがオプションとして提供されています）。

Allocation

Juliaは2種類のアロケータを使用しており、アロケーションリクエストのサイズによってどちらが使用されるかが決まります。2kバイトまでのオブジェクトは、スレッドごとのフリリストプールアロケータで割り当てられ、2kバイトを超えるオブジェクトはlibc mallocを通じて割り当てられます。

Juliaのプールアロケータは、異なるサイズクラスのオブジェクトをパーティション分けします。これにより、プールアロケータによって管理されるメモリページ（64ビットプラットフォームでは4つのオペレーティングシステムページにまたがる）は、同じサイズクラスのオブジェクトのみを含むことになります。プールアロケータからの各メモリページは、スレッドごとのロックフリーリストに保存されたページメタデータとペアになっています。ページメタデータには、そのページにライブオブジェクトが存在するかどうか、空きスロットの数、そしてそのページに含まれるフリリスト内の最初と最後のオブジェクトへのオフセットなどの情報が含まれています。これらのメタデータは、コレクションフェーズを最適化するために使用されます。たとえば、ライブオブジェクトがまったく存在しないページは、スキャンする必要なくオペレーティングシステムに返される可能性があります。

オブジェクトがないページはオペレーティングシステムに返される可能性がありますが、その関連メタデータは永続的に割り当てられ、指定されたページよりも長く生存する可能性があります。前述のように、割り当てられたページのメタデータはスレッドごとのロックフリーリストに保存されます。しかし、空きページのメタデータは、ページがマッピングされているが一度もアクセスされていない場合（page_pool_clean）、ページが遅延スイープされており、バックグラウンドGCスレッドによってマドバイズされるのを待っている場合（page_pool_lazily_freed）、またはページがマドバイズされている場合（page_pool_freed）に応じて、3つの別々のロックフリーリストに保存される可能性があります。

ジュリアのプールアロケータは「階層的」な割り当て方針に従います。プールアロケータのためにメモリページを要求する際、ジュリアは次のようにします：

page_pool_lazily_freedからページを取得しようとします。ここには、最後のストップ・ザ・ワールドフェーズで空だったページが含まれていますが、同時に実行されているスイーパーGCスレッドによってまだマディバイズされていません。
page_pool_lazily_freed からページの取得に失敗した場合、以前のページ割り当て要求で mmap されたが一度もアクセスされなかったページを含む page_pool_clean からページを取得しようとします。
pool_page_clean および page_pool_lazily_freed からページの取得に失敗した場合、page_pool_freed からページを取得しようとします。ここには、同時に動作しているスイーパー GC スレッドによってすでにマッドアドバイスされたページが含まれており、その基盤となる仮想アドレスは再利用可能です。
上記のすべての試行が失敗した場合、バッチのページをmmapし、自身のために1ページを確保し、残りのページをpage_pool_cleanに挿入します。

階層プール割り当ての図

Marking and Generational Collection

ジュリアのマークフェーズは、オブジェクトグラフに対する並列反復深さ優先探索を通じて実装されています。ジュリアのコレクタは移動しないため、オブジェクトの年齢情報はオブジェクトが存在するメモリ領域だけでは決定できず、オブジェクトヘッダーまたはサイドテーブルに何らかの形でエンコードする必要があります。オブジェクトのヘッダーの最下位2ビットは、それぞれ、マークフェーズ中にオブジェクトがスキャンされたときに設定されるマークビットと、世代コレクションのための年齢ビットを格納するために使用されます。

世代コレクションは、スティッキービットを通じて実装されています：オブジェクトは、マークビットが設定されていない場合にのみマークスタックにプッシュされ、したがってトレースされます。オブジェクトが最古の世代に達すると、いわゆる「クイックスイープ」の間にマークビットはリセットされず、その結果、これらのオブジェクトは次のマークフェーズでトレースされません。しかし、「フルスイープ」は、すべてのオブジェクトのマークビットをリセットし、次のマークフェーズで全てのオブジェクトがトレースされることになります。オブジェクトは、生存している各スイープフェーズの間に次の世代に昇進します。ミューテータ側では、フィールドの書き込みは、オブジェクトが最後の世代にあり、書き込まれているフィールドのオブジェクトがそうでない場合に、オブジェクトのアドレスをスレッドごとの記憶セットにプッシュする書き込みバリアを通じてインターセプトされます。この記憶セット内のオブジェクトは、その後マークフェーズでトレースされます。

Sweeping

オブジェクトプールのスイーピングは、Juliaにおいて2つのカテゴリに分けられます。プールアロケータによって管理される特定のページに少なくとも1つの生存オブジェクトが含まれている場合、そのデッドオブジェクトを通じてフリリストをスレッドしなければなりません。一方、特定のページに生存オブジェクトがまったく含まれていない場合、その基盤となる物理メモリは、たとえばLinuxのmadviseシステムコールを使用してオペレーティングシステムに返却される可能性があります。

最初のスイーピングのカテゴリは、ワークスティーリングを通じて並列化されています。2番目のスイーピングのカテゴリでは、フラグ --gcthreads=X,1 を通じて同時ページスイーピングが有効になっている場合、バックグラウンドスイーパースレッドで madvise システムコールを実行し、ミューテータスレッドと並行して処理します。コレクタのストップ・ザ・ワールドフェーズ中に、ライブオブジェクトを含まないプールに割り当てられたページは、最初に pool_page_lazily_freed にプッシュされます。バックグラウンドスイーピングスレッドが起こされ、pool_page_lazily_freed からページを削除し、それに対して madvise を呼び出し、pool_page_freed に挿入する責任を負います。上記のように、pool_page_lazily_freed はミューテータスレッドとも共有されています。これは、割り当てが多いマルチスレッドワークロードでは、ミューテータスレッドが新しい mmaped ページにアクセスするか、madvise されたページにアクセスすることから来るページフォルトを回避するために、pool_page_lazily_freed のページから直接割り当てを行うことが多いことを意味します。一方、バックグラウンドスイーパースレッドは、ミューテータによってすでに要求されたページの一部があるため、少数のページに対して madvise を行う必要があります。

Heuristics

GC ヒューリスティクスは、ガーベジコレクションの間の割り当て間隔のサイズを変更することによって GC を調整します。

GC ヒューリスティクスは、コレクション後のヒープサイズがどれくらい大きいかを測定し、https://dl.acm.org/doi/10.1145/3563323 で説明されているアルゴリズムに従って次のコレクションを設定します。要約すると、ヒープのターゲットは生存ヒープとの平方根関係を持つべきであり、GC がオブジェクトを解放する速度やミューテータが割り当てる速度によってスケーリングされるべきだと主張しています。ヒューリスティクスは、使用中のページ数と malloc を使用するオブジェクトの数をカウントすることによってヒープサイズを測定します。以前は生存オブジェクトをカウントすることでヒープサイズを測定していましたが、それでは断片化を考慮しておらず、悪い決定につながる可能性がありました。また、それはスレッドローカル情報（割り当て）を使用してプロセス全体（GC のタイミング）についての決定を行うことを意味していましたが、ページを測定することで決定がグローバルになります。

GCは、ヒープサイズが最大許容サイズの80％に達したときにフルコレクションを行います。