2013年7月6日 星期六

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) 函數):
  1. 對每個容器,將他的 gc_refs 設成該物件自己的 reference count。 (update_refs 所做的事)
  2. 對每個容器,將他所參考的容器的 gc_refs 的值減一 ( subtract_refs 所做的事)
  3. 移除掉所有 gc_refs 大於的容器,那些物件表示有被其他物件參考。( move_unreachable 所做的事)
  4. 任何被移除的容器所參考到的容器,也需要被移除。 ( visit_reachable 所做的事)
  5. 從剩下的容器物件(他們可能是垃圾)中,找出有定義 __del__ 的物件,把他們放到 finalizers 的 list 中,那些不是垃圾 ( move_finalizers 所做的事)。
  6. 把被 finalizers 的 list 裡的容器所參考的容器移到 finalizers 的 list。 (move_finalizer_reachable 所做的事)
  7. 處理指向垃圾的 weakref ( handle_weakrefs )
  8. 刪除垃圾 (delete_garbage)
  9. 將有 __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 的問題。

    參考資料:

沒有留言:

張貼留言