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 されたが一度もアクセスされなかったページを含む the page_pool_clean からページを取得しようとします。
pool_page_clean および page_pool_lazily_freed からページの取得に失敗した場合、page_pool_freed からページを取得しようとします。これは、すでに同時に実行されているスイーパー GC スレッドによってマッドアドバイスされたページを含み、その基盤となる仮想アドレスが再利用可能です。
すべての上記の試行が失敗した場合、バッチのページをmmapし、自身のために1ページを確保し、残りのページをpage_pool_cleanに挿入します。

階層プール割り当ての図

Marking and Generational Collection

Juliaのマークフェーズは、オブジェクトグラフに対する並列反復深さ優先探索を通じて実装されています。Juliaのコレクタは移動しないため、オブジェクトの年齢情報はオブジェクトが存在するメモリ領域だけでは決定できず、オブジェクトヘッダー内またはサイドテーブルに何らかの形でエンコードされる必要があります。オブジェクトのヘッダーの最低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％に達したときにフルコレクションを行います。