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

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

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

Sweeping

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

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

Heuristics

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

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

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