python 的 gc ( garbage collection) 演算法介紹

最近無聊看了一下 python 的 garbage collect 的實作。還蠻簡單易懂的。 python 回收沒用的物件，主要是靠參考計數 (reference count)。然而，他無法解決自己參考自己或是參考循環(a 參考 b， b 參考 a)的問題。這篇文章是講 python 如何解決這個問題。

自己參考自己的範例是

a = []
a.append(a)

參考循環的範例是

a = []
b = []
a.append(b)
b.append(a)

python 的 gc model (程式碼在 Modules/gcmodule.c) 用來解決這個問題。 python 的 gc 策略是找出一定是垃圾。因為非容器的物件不會有參考循環(或是自己參考自己的問題)，因此 python 只對容器 (container) 做 gc。下面是他的演算法步驟(根據 python 2.7.3 的程式碼，static Py_ssize_t
collect(int generation) 函數):

對每個容器，將他的 gc_refs 設成該物件自己的 reference count。 (update_refs 所做的事)
對每個容器，將他所參考的容器的 gc_refs 的值減一 ( subtract_refs 所做的事)
移除掉所有 gc_refs 大於的容器，那些物件表示有被其他物件參考。( move_unreachable 所做的事)
任何被移除的容器所參考到的容器，也需要被移除。 ( visit_reachable 所做的事)
從剩下的容器物件(他們可能是垃圾)中，找出有定義 __del__ 的物件，把他們放到 finalizers 的 list 中，那些不是垃圾 ( move_finalizers 所做的事)。
把被 finalizers 的 list 裡的容器所參考的容器移到 finalizers 的 list。 (move_finalizer_reachable 所做的事)
處理指向垃圾的 weakref ( handle_weakrefs )
刪除垃圾 (delete_garbage)
將有 __del__ 的垃圾放到 garbage list，讓程式設計師處理(handle_finalizers)

python 把所有可以 gc 的物件分成三代，只要被 gc 過一次而沒被回收則到下一代，程式碼大概長這樣

    /* Move reachable objects to next generation. */
    if (young != old) {
        if (generation == NUM_GENERATIONS - 2) {
            long_lived_pending += gc_list_size(young);
        }
        gc_list_merge(young, old);
    }
    else {
        long_lived_pending = 0;
        long_lived_total = gc_list_size(young);
    }

為了增進 gc 效能，每次 gc 時並不會檢查所有的容器。他只會檢查年輕的容器(除非條件滿足或是使用者指定)。越老的容器，越不容易被 gc。上面提到的條件是指 threshold 參數。當從上次 gc 以來，第 0 代的容器數目大於 threshold 0 時，執行第 0 代垃圾回收 ( 第 0 代垃圾回收是指物件若逃過一次以上的垃圾回收，該物件在這次 gc 中不會被檢查)，當第 0 代垃圾回收執行次數大於 threshold 1，則執行第 1 代垃圾回收 ( 第 1 代垃圾回收是指物件若逃過 2 次以上的垃圾回收，該物件在這次 gc 中不會被檢查)。當第 1 代垃圾回收執行次數大於 threshold 2 時，則執行第 2 代垃圾回收。

gc 自動被呼叫的時機則是在於當要分配空間給可以被 gc 物件時，會檢查是否滿足 garbage collection，滿足的話則進行 gc。詳見 Modules/gcmodule.c 裡的 _PyObject_GC_Malloc 函數。

事實上，python 的 gc 演算法和傳統的 gc 演算法不一樣。傳統的 gc 演算法是定義一個根物件 (root)，只要和根物件有聯結的話就不是垃圾。不過這套在 python 中行不通，因為 extension modules 的關係。而且 python 已經有使用 reference count。所以他使用這個方法，來彌補 reference count 的問題。

參考資料:

程式的窩

2013年7月6日星期六