Pythonのガベージコレクタは「マーク&スイープ」？

昨日公開した Pythonのガベージコレクションにこんな突っ込みをいただいた。

マークアンドスイープGCじゃないそうです
PythonのGarbageCollection http://www.narihiro.info/translate/garbage_collection_for_python_jp.html

確かに、Pythonで使用しているのは教科書で言うマーク&スイープとは異なるアルゴリズムである。上記のページにあるように、いわゆるマーク&スイープは、ルートオブジェクトと呼ばれる生きていることが確実なオブジェクトを見つけ出し、そこから参照されているオブジェクトをどんどん探り出して、最終的に誰からも参照されていないオブジェクトをあぶり出すというものだ。Pythonではルートからオブジェクトを探すというアプローチを取っておらず、私も会場の説明では「マークアンドスイープの一種」のような言い方をしたと思う。

だがまあ、ここは大目に見ていただきたい。「マーク&スイープ」と言わないとすると、なんと呼べばよいのか困ってしまう。単に「ガベージコレクタ」と言ってしまうとこれは不要メモリの解放手段全般を指す用語で、参照カウント方式も含まれてしまう。他に通りの良い呼び方が見つからないのだ。

おそらくPythonの解説者たちはみんな困っていて、とりあえず「Pythonのガベージコレクタというのは参照カウントとマーク&スイープ」というように説明されることが多いように思う。ちょっと検索してみると、

PythonのGCはマーク&スイープですか？

という質問に対して、Fredrik Lundh/Martin v. Lowis というPython界きってのうるさ型がそろって

普通のマーク&スイープとは違うけど、...

とか

そうです

とか答えている。また、 Dive Into Pythonという書籍では、はっきりと

Python 2.0 にはマーク&スイープという新しいガベージコレクタがあり、…

と書いてしまっている。まあ、いちおうマークするし、スイープもするのだから良いではないか。読者諸賢の寛仁を乞う次第である。

なんで「マーク&スイープ」じゃないの？

ところで、先ほどの「PythonのGarbageCollection」では、伝統的なマーク&スイープを採用しない理由として

拡張モジュールが動作している為，Pythonはルートセットを完全に取り決める事は決して出来ないからです

オブジェクトはCの関数スタック上にあり，ポータブルにルートを見つける方法はないでしょう

と二つの理由をあげている。ここをもうちょっと掘り下げてみよう。

Pythonはルートセットを完全に取り決める事は決して出来ない

前述のように、伝統的なマーク&スイープでは到達可能なオブジェクトを探すために、確実に生きているオブジェクトをルートオブジェクトとして把握できなければならない。Pythonで書かれたアプリケーションではインタープリタがルートとなるオブジェクトを把握しておけばよいのだが、C言語で書かれた拡張モジュールではちょっと話が変わってくる。たとえば

static PyObject *static_obj;

void init_mymodule(PyObject *m) {
    static_obj = PyList_New(0);
}

などというコードがあった場合、自動的にstatic_objをルートオブジェクトとして認識することができない。ルートオブジェクトとして登録するためには、例えば

static PyObject *static_obj;

void init_mymodule(PyObject *m) {
    static_obj = PyList_New(0);
    PyGC_RegisterRoot(static_obj);
}

のように、新しいPython APIを用意して、拡張モジュール側でルートオブジェクトを明示的に指定する必要があるのだ。

しかし、Python2でガベージコレクタを修正しようという話になったころには、すでにサードパーティによるPython拡張モジュールが大量に存在していた。Pythonコミュニティは基本的にバージョン間のコンパチビリティを非常に重視するので、このような既存拡張モジュールへの影響が大きい修正は受け入れられなかったのである。

まあ、決してできないというのは言い過ぎかもしれないが、技術的にはともかくPythonの開発ポリシーからすると不可能、ということである。

オブジェクトはCの関数スタック上にあり，ポータブルにルートを見つける方法はないでしょう

面倒なので「Cの関数スタック」という言葉の解説は省略するが、スタックという、CPU/OSなどの環境に非常に強く依存するデータ領域を取り扱わなければならないので嫌だね、という話だ。

有名なGCライブラリのBoehm GCなどでは、スタックなどのメモリ領域から自動的にルートオブジェクトを探索する、「保守的ガベージコレクタ」という方式をとっている。Boehm GCでは環境依存の部分を解決するために一部アセンブリ言語で記述されている箇所があったりもする。

Python専用のガベージコレクタを実装するのではなく、このBoehm GCを使えばよいのではないか、という声もあったのだが、こんなアーキテクチャ依存の処理があるとPythonの移植性が損なわれてしまうという懸念から、最終的には却下された。おかげで、現在でもPythonのコア部分は、Cコンパイラが使える環境であれば、細かいアーキテクチャに関わらず移植することができるのである。