はじめに

　この記事はSafie Engineers' Blog! Advent Calendar 16日目の記事です

　セーフィーのサーバーサイドエンジニアの三村です。

　セーフィーのサーバーサイドでは箇所によって色々な言語（Python, Go, Java…）が用いられていますが、コードベースの大部分はPythonを用いています。本記事では、そんな普段セーフィーのエンジニアが用いているPython（*1）のガベージコレクションの仕組みについて調べたので、まとめてみます。

はじめに
概要の説明
参照数によるガベージコレクションの実装
まとめ

概要の説明

　多くのプログラミング言語には、ユーザーが明示的に行なわずとも自動で不要なデータをメモリから解放するガベージコレクションの仕組みがあります。こちらは各言語ごとに仕組みや詳細な実装は異なっていますが、Pythonの場合には2種類の自動のメモリ解放の仕組みがあります。

　一つ目は、Pythonの全てのオブジェクトに被参照数のカウントを持つようにして、それが0になったらメモリ解放をするという単純なものです。

　もう一つは、上記の手法では対応できない循環参照の検知のための仕組みです。全てのオブジェクトを「世代」に分けてトラックしておき、それらの中で使われていないものを探索し開放する手法のものです。

参照数によるガベージコレクションの実装

概要

　Pythonのオブジェクト（CのコードではPyObjectと呼ばれる）は全て、被参照数をデータとして持っています。こちらのカウンターが0になるとメモリ解放がされます。こちらの、PyObjectの被参照数を減らして数が0になれば削除をしている実装を見てみます。

static inline Py_ALWAYS_INLINE void Py_DECREF(PyObject *op)
{
    // Non-limited C API and limited C API for Python 3.9 and older access
    // directly PyObject.ob_refcnt.
    if (_Py_IsImmortal(op)) {
        return;
    }
    _Py_DECREF_STAT_INC();
    if (--op->ob_refcnt == 0) {
        _Py_Dealloc(op);
    }
}

cpython/Include/object.h at v3.12.7 · python/cpython · GitHub

　引数で受け取ったPyObjectの被参照数を表すob_refcountをデクリメントして、値が0になれば_PyDeallocというメモリ解放の関数を呼び出しています。

呼び出される_PyDeallocの関数は、以下の実装になっています。

// デバッグモードの時等の挙動が長いので、それらを省いて簡略化
void
_Py_Dealloc(PyObject *op)
{
    PyTypeObject *type = Py_TYPE(op);
    destructor dealloc = type->tp_dealloc;

    (*dealloc)(op);
}

cpython/Objects/object.c at v3.12.7 · python/cpython · GitHub

　削除対象のオブジェクトの型（Py_TYPE）がそれぞれ持つtp_deallocという関数を呼び出してメモリ解放を行なっています。このように、Pythonのオブジェクトの型ごとにメモリ解放の実装は異なっています。

intのオブジェクトでの例

　いくつもあるPythonの型の中で、一例としてint型のオブジェクトの参照数によるメモリ解放の例を見てみます。（*2）

long_dealloc(PyObject *self)
{
    /* This should never get called, but we also don't want to SEGV if
     * we accidentally decref small Ints out of existence. Instead,
     * since small Ints are immortal, re-set the reference count.
     */
    PyLongObject *pylong = (PyLongObject*)self;
    if (pylong && _PyLong_IsCompact(pylong)) {
        stwodigits ival = medium_value(pylong);
        if (IS_SMALL_INT(ival)) {
            PyLongObject *small_pylong = (PyLongObject *)get_small_int((sdigit)ival);
            if (pylong == small_pylong) {
                _Py_SetImmortal(self);
                return;
            }
        }
    }
    Py_TYPE(self)->tp_free(self);
}

cpython/Objects/longobject.c at v3.12.7 · python/cpython · GitHub

　条件分岐を経て、最後の部分でメモリ解放（tp_freeの中で実際にはされています）がされています。

　余談ですが、上で引用したコードの中ではこのintの値が特定の基準よりも小さいかどうかを判定（IS_SMALL_INT）*3 して、小さければ_Py_SetImmortalをしてガベージコレクションにかけられないようにしています。こちらはPython3.12以降には、使用頻度が高いことが見込まれる小さい値のintのオブジェクトを削除しないようにした、パフォーマンス向上目的の変更です。こちらの仕様の導入には色々議論があったようで、気になった方はこちらのPRを見てみてください。

世代別の循環参照検知のガベージコレクションの実装

　上記のようなシンプルな参照数によるガベージコレクションがあれば、それで足りるのではないかと思うかもしれませんが、実際はそれでは済みません。Pythonのオブジェクト同士の循環参照のケースが、上のやり方だとカバーできないためです。このケースを避けるため、Pythonにはもう一つ世代別のガベージコレクションの仕組みが存在します。

世代とは

　（プログラミングの実行時の一般論として）ほとんどのオブジェクトは作成直後に使用されなくなる傾向があり、作成直後のオブジェクトのリストのほうが作成から時間の経ったオブジェクトよりも、ガベージコレクションの対象となる確率が高くなります。

　そのため、循環参照の検知のような重めの処理では、「世代」の若い（作られて間もない）オブジェクトのチェックを頻繁に行い、「世代の古い」（作られて時間の経っている）オブジェクトのチェックはより稀に行うようにして、効率化を図っています。

　この考え方は、Python独自のものではなくそのほかのプログラミング言語（Java等）でも一般的に用いられています。

オブジェクトのリストの作成

　Pythonのこちらの方式のガベージコレクションでは、世代ごとに循環参照となり得るすべてのオブジェクト（=他のPyObjectへの参照を持っているPyObject）のリストを持ちます。その後、そのリストの内部を走査し、特定の世代内部のみで循環参照をしているものを見つけて、メモリ解放をします。

　ここではまず、特定の世代のPyObjectを双方向リストとして保持する実装を見てみます。こちらの双方向リストには、オブジェクトの作成時に追加されます。以下でtupleのオブジェクトの生成時の例を挙げます。

PyObject *
PyTuple_New(Py_ssize_t size)
{
    PyTupleObject *op;
    if (size == 0) {
        return tuple_get_empty();
    }
    op = tuple_alloc(size);
    if (op == NULL) {
        return NULL;
    }
    for (Py_ssize_t i = 0; i < size; i++) {
        op->ob_item[i] = NULL;
    }
    _PyObject_GC_TRACK(op); // 筆者注: ここで作成したオブジェクトを、トラックできるようにしている
    return (PyObject *) op;
}

cpython/Objects/tupleobject.c at v3.12.7 · python/cpython · GitHub

　引用したコードの最後の方で_PyObject_GC_TRACK関数を呼び出して、世代別ガベージコレクションで追跡できるよう、作成したtupleのオブジェクトを双方向リスト（各要素が、自身の前と次へのリンクを持っているリスト）に追加しています。

　こちらの_PyObject_GC_TRACKの処理の実装を見てみます。

static inline void _PyObject_GC_TRACK(
// The preprocessor removes _PyObject_ASSERT_FROM() calls if NDEBUG is defined
#ifndef NDEBUG
    const char *filename, int lineno,
#endif
    PyObject *op)
{
    _PyObject_ASSERT_FROM(op, !_PyObject_GC_IS_TRACKED(op),
                          "object already tracked by the garbage collector",
                          filename, lineno, __func__);

    PyGC_Head *gc = _Py_AS_GC(op);
    _PyObject_ASSERT_FROM(op,
                          (gc->_gc_prev & _PyGC_PREV_MASK_COLLECTING) == 0,
                          "object is in generation which is garbage collected",
                          filename, lineno, __func__);

    PyInterpreterState *interp = _PyInterpreterState_GET();
    PyGC_Head *generation0 = interp->gc.generation0;
    PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
    _PyGCHead_SET_NEXT(last, gc); // 筆者注: この辺からリストへの追加を行なっている
    _PyGCHead_SET_PREV(gc, last);
    _PyGCHead_SET_NEXT(gc, generation0);
    generation0->_gc_prev = (uintptr_t)gc;
}

cpython/Include/internal/pycore_object.h at v3.12.7 · python/cpython · GitHub

　こちらのコード内のgcというものが、引数で受け取ったPyObjectをガベージコレクションで追跡できるような型にキャストしたものです。こちらを、現在のラインタイムにおける最も若い世代のPyObjectの双方向リスト（generation0）の最後尾に追加しています。

オブジェクトのリストの走査

　上で特定の世代のPyObjectのリストに要素を追加する実装例を見たので、次にそのリスト内を走査する実装を見て見ます。こちらは以下のgc_collect_main関数で実行されています。

/* This is the main function.  Read this to understand how the
 * collection process works. */
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
                Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
                int nofail)
{
    int i;
    Py_ssize_t m = 0; /* # objects collected */
    Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
    PyGC_Head *young; /* the generation we are examining */
    PyGC_Head *old; /* next older generation */
    PyGC_Head unreachable; /* non-problematic unreachable trash */
    PyGC_Head finalizers;  /* objects with, & reachable from, __del__ */
    PyGC_Head *gc;
    _PyTime_t t1 = 0;   /* initialize to prevent a compiler warning */
    GCState *gcstate = &tstate->interp->gc;

// 略

    // 筆者注: 1. 若い世代のマージ
    /* merge younger generations with one we are currently collecting */
    for (i = 0; i < generation; i++) {
        gc_list_merge(GEN_HEAD(gcstate, i), GEN_HEAD(gcstate, generation));
    }

    /* handy references */
    young = GEN_HEAD(gcstate, generation);
    if (generation < NUM_GENERATIONS-1)
        old = GEN_HEAD(gcstate, generation+1);
    else
        old = young;
    validate_list(old, collecting_clear_unreachable_clear);

    // 筆者注: 2. 到達不能のオブジェクトの探索
    deduce_unreachable(young, &unreachable);

    untrack_tuples(young);
    // 筆者注: 3. 到達可能のオブジェクトを古い世代に移動
    /* Move reachable objects to next generation. */
    if (young != old) {
        if (generation == NUM_GENERATIONS - 2) {
            gcstate->long_lived_pending += gc_list_size(young);
        }
        gc_list_merge(young, old);
    }
    else {
        /* We only un-track dicts in full collections, to avoid quadratic
           dict build-up. See issue #14775. */
        untrack_dicts(young);
        gcstate->long_lived_pending = 0;
        gcstate->long_lived_total = gc_list_size(young);
    }

// 略
    // 筆者注: 4. 到達不能のオブジェクトの削除
    /* Call tp_finalize on objects which have one. */
    finalize_garbage(tstate, &unreachable);

    /* Handle any objects that may have resurrected after the call
     * to 'finalize_garbage' and continue the collection with the
     * objects that are still unreachable */
    PyGC_Head final_unreachable;
    handle_resurrected_objects(&unreachable, &final_unreachable, old);

    /* Call tp_clear on objects in the final_unreachable set.  This will cause
    * the reference cycles to be broken.  It may also cause some objects
    * in finalizers to be freed.
    */
    m += gc_list_size(&final_unreachable);
    delete_garbage(tstate, gcstate, &final_unreachable, old);

// 略
}

cpython/Modules/gcmodule.c at v3.12.7 · python/cpython · GitHub

　上記で引用したコード（*4）では、引数generationで受け取った世代のリストのコレクションを実行します。以下のような手順でオブジェクトのリストを走査しています。

1.若い世代のマージ

　本関数でコレクションをする対象の世代のリストに、それよりも若い世代のコレクション対象リストをマージします（gc_list_merge関数）。

　例として、第3世代のコレクションをしている場合は、第3世代のリストに第1世代と第2世代のリストをマージして、このリストをガベージコレクションのチェックの対象とします。こうすることで、若い世代のリストほど、ガベージコレクションの走査の対象となる頻度が高くなります。

2.到達不能のオブジェクトの探索

　1. 若い世代のマージで作成したリストの中から、到達不能なオブジェクトを探し出します（deduce_unreachable関数）。この関数の中では、循環参照を検知（後述）して、参照はあるものの実際は到達不能なオブジェクト（=参照数カウントのガベージコレクションでは検知できないが、実際は削除するべきオブジェクト）を探します。

3.到達可能のオブジェクトを古い世代に移動

　2. 到達不能のオブジェクトの探索でのチェックで引っ掛からなかった、コレクションの対象とすべきでないオブジェクトを、一つ古い世代に移します。こちらは先述した通り、作成されてから時間が経ったオブジェクトほど削除対象となる確率が下がるためです。

4.到達不能のオブジェクトの削除

　2. 到達不能のオブジェクトの探索で削除が必要と判明したオブジェクトを、実際に削除します。

到達不能のオブジェクトの探索

　上で、PyObjectのリストから到達不能なものを探索して削除する実装を軽くみてみました。次に、具体的にどのようなロジックで到達不能なオブジェクトを探しているのかを見てみます。上で到達不能なオブジェクトを探索するのに用いていた、deduce_unreachableの実装を引用します。

// 筆者注: コードに元々あったコメントを削除し、筆者のコメントを追加
static inline void
deduce_unreachable(PyGC_Head *base, PyGC_Head *unreachable) {
    validate_list(base, collecting_clear_unreachable_clear);

    update_refs(base);  // 1. GC用のカウンターをセット
    subtract_refs(base); // 2. 他のオブジェクトからの参照を探して、その分カウンターを減らす

    gc_list_init(unreachable);
    move_unreachable(base, unreachable);  // 3. カウンターの値を元に、削除対象のオブジェクトを探す
    validate_list(base, collecting_clear_unreachable_clear);
    validate_list(unreachable, collecting_set_unreachable_set);
}

cpython/Modules/gcmodule.c at v3.12.7 · python/cpython · GitHub

　まず、1. GC用のカウンターをセットの部分で、検査対象の世代の全オブジェクトのリスト（実装上はcontainersと呼ばれる）を走査し、参照数によるガベージコレクションに用いられているobj_refcntとは別に本処理用にgc_refsというカウンターを設定します。新しく設定した後者のカウンターには、デフォルト値として前者と同じ値を入れます。

　以下に、簡単な図解を用意します。ここでは、オブジェクトAからEまでがあり、それら全てにgc_refsの値を参照数であるobj_refcntの値を設定しています。この例だと、A, B, Cはこの世代の外から参照されており削除対象とはなりませんが、DとEはお互いの循環参照のみによって参照されていて、もう利用されておらずガベージコレクションで削除されるべきオブジェクトになります。

　次に、上で引用したコードの2. 他のオブジェクトからの参照を探して、その分カウンターを減らすの部分で、GC対象のオブジェクトのリストでイテレーションを回します。その中で、それぞれのオブジェクトが持つ他のオブジェクトへの参照を探し出して、参照先のオブジェクトのgc_refsのカウンターを1ずつ減らします。

　例えばオブジェクトがdict型であれば、自身の辞書のkeyとvalueの両方のオブジェクトのgc_refsをデクリメントします。（*5）

　以下の例だと、AはBへの参照を持つためBのgc_refsを減らし、同様にBはCへの参照を持つためCのgc_refsを減らします。DとEはお互いを参照しているので、お互いのgc_refsを減らします。

各オブジェクトの参照を辿って、参照先のオブジェクトのgc_refsを1ずつ減らしていく

　その後、上記引用のコードの3. カウンターの値を元に、削除対象のオブジェクトを探すの箇所で、gc_refsの値を元に循環参照でのみ参照されているオブジェクト（=参照数が0ではないがもう利用されていないオブジェクト）を探します。

　まず、gc_refsが0であるオブジェクトと1以上であるオブジェクトに分離します。オブジェクトに参照がある場合はそのままcontainersに置かれ、なければunreachableというリストに移されます。

　gc_refsが0である場合、この世代の外側から参照されていない可能性があります。こちらが、ガベージコレクションの対象となるオブジェクトの候補のリストとなります（後述する通り、この時点ではコレクションの対象となると確定したわけではないです）。

　逆にgc_refsが1以上であれば、それは現在使用されているオブジェクトであると判定できます。この場合、この世代以外の箇所からも参照されていると判断できるため、この時点でガベージコレクションの対象からは外れます。

　下記の例だと、gc_refsが1以上であり確実に利用されていると言えるのはAのみです。ただし、gc_refsが0であるunreachableのリストの中には、確かにコレクション対象となるべきDとEも存在しますが、Aから利用されていて消されるべきではないBとCも存在します