Garbage Collection for Python

Pythonのガベージコレクションについて書かれた論文の一部を訳す。
実際にどういう風なアプローチで実装されてるかが分かる部分だけ。

Garbage Collection for Python

How does this Approach Work?

このアプローチはどう働く？

Conceptually, this approach does the opposite of traditional garbage collection. Instead of trying to find all reachable objects it tries to find unreachable objects. This is much safer because if the algorithm fails we are no worse off than with no garbage collection (except for the time and space wasted).

概念的に、このアプローチは伝統的なガベージコレクションの反対のことを行う。全ての到達可能なオブジェクトを見付ける試みの代わりに到達不可能なオブジェクトを見付けるようと試みる。これはより安全である、なぜならばもしアルゴリズムが失敗しても(時間と空間の無駄を除いて)ガベージコレクション無しより悪くなることはない。

Since we are still using reference counting, the garbage collector only has to find reference cycles. The reference counting will handle freeing other types of garbage. First we observe that reference cycles can only be created by container objects. These are objects which can hold references to other objects. In Python lists, dictionaries, instances, classes, and tuples are all examples of container objects. Integers and strings are not containers. With this observation we realize that non-container objects can be ignored for the purposes of garbage collection. This is a useful optimization because things like integers and strings should be fast and small.

まだ参照カウントを使用しているので、ガベージコレクターは参照サイクルを見付けるだけである。参照カウントは他の型のゴミの開放を扱う。最初に参照サイクルはコンテナオブジェクトによってのみせいせいされることに気付く。これらは他のオブジェクトへの参照を持つオブジェクトである。Pythonではリスト、辞書、インスタンス、クラス、そしてタプルはコンテナオブジェクトの例の全てである。整数と文字列はコンテナではない。この所見から非コンテナオブジェクトはガベージコレクションの目的のために無視できることに気付く。これは有用な最適化である、なぜならば整数と文字列のようなものは速くて小さくあるべきである。

Our idea now is to keep track of all container objects. There are several ways that this can be done but one of the best is using doubly linked lists with the link fields inside the objects structure. This allows objects to be quickly inserted and removed from the set as well as not requiring extra memory allocations. When a container is created it is inserted into this set and when deleted it is removed.

アイデアは今、全てのコンテナオブジェクトのトラックを把握することである。いくつかの方法があるり可能かもしれないが、最高のうちの1つはオブジェクトの構造の中にリンクフィールドを備えた二重のリンクリストを使用することである。これはオブジェクトが余計なメモリ割り当てを必要としないだけでなく集合から速やかに挿入や削除することを許す。

Now that we have access to all the container objects, how to we find reference cycles? First we to add another field to container objects in addition to the two link pointers. We will call this field gc_refs. Here are the steps to find reference cycles:

今全てのコンテナオブジェクトへのアクセスを持つ、どのように参照サイクルをみつけるか？最初にコンテナオブジェクトへ2つのリンクポインタに加えて他のフィールドを追加。このフィールドをgc_refsと呼ぶ。参照サイクルを見付けるためのステップがここにある：

1. For each container object, set gc_refs equal to the object's reference count.
2. For each container object, find which container objects it references and decrement the referenced container's gc_refs field.
3. All container objects that now have a gc_refs field greater than one are referenced from outside the set of container objects. We cannot free these objects so we move them to a different set.
4. Any objects referenced from the objects moved also cannot be freed. We move them and all the objects reachable from them too.
5. Objects left in our original set are referenced only by objects within that set (ie. they are inaccessible from Python and are garbage). We can now go about freeing these objects.

1. 各コンテナオブジェクトについて、オブジェクトの参照カウントと同じになるようにgc_refsを設定。
2. 各コンテナオブジェクトについて、到達可能なコンテナオブジェクトを見付けて参照されたコンテナのgc_refsフィールドをデクリメント。
3. 今1より大きなgc_refsフィールドを持つ全てのコンテナオブジェクトは外部のコンテナオブジェクトの集合から参照されている。それらを異なる集合へ移動するのでこれらのオブジェクトを開放できない。
4. 移動されるオブジェクトから参照されるどんなオブジェクトもまた開放することができない。それらを移動してそれらから到達可能な全てのオブジェクトも。
5. オリジナルの集合に残るオブジェクトはその集合に属するオブジェクトによってだけ参照される。