最近在閱讀《垃圾回收的算法與實作》，裡面将講到了一些常用的垃圾回收(Garbage Collect)算法，如：标記-清除、引用計數、分代回收等等。
後面講到了 Python 的垃圾回收政策，在此記錄一下。
吞吐量
吞吐量為機關時間内的GC出來能力。計算公式為：GC處理的堆容量 / GC花費的時間。
通常，人們都喜歡吞吐量高的GC算法。
最大暫停時間
GC執行過程中令使用者線程暫停的最長時間。如果GC時間過長，會影響程式的正常執行。
較大的吞吐量和較短的最大暫停時間往往不可兼得。
堆使用效率
GC是自動記憶體管理功能，是以理想情況是在GC時不要占用過量的堆空間。
影響堆使用效率的兩個因素是：頭的大小和堆的用法。
可用的堆越大，GC運作越快；相反，越想有效地利用有限的堆，GC花費的時間就越長。
通路的局部性
具有引用關系的對象之間通常很可能存在連續通路的情況。這在多數程式中都很常見，稱為“通路的局部性”。
考慮到通路局部性，把具有引用關系的對象安排在堆中較近的位置，能夠提高資料的使用率。
Python 使用引用計數的 GC 的算法，引用計數算法的優勢是可以減短<code>最大暫停時間</code>，缺陷是在維護計數的增量和減量上面臨很大的挑戰（如果忘記執行減量操作就會造成對象沒有釋放）。
對于 Python 的資料，像 List、Set、Tuple、Dict、Str、Int，在其底層的資料結構中，都會有一個<code>PyObject</code>類型的成員，用來維護對象的引用計數
其中的<code>ob_refcnt</code>成員負責維持引用計數
如此，所有的内置型結構在都在開頭保留了<code>PyObject</code>結構體來維護引用計數。
Python 在進行記憶體配置設定時并不是簡單的調用<code>malloc/free</code>函數來向作業系統請求記憶體的。而是出于效率考慮盡可能減少系統調用，将記憶體配置設定器分成了3層。
第0層到第3層是 Python 實作管理的分布器層級，如果以字典對象為例，
第0層就是直接調用作業系統提供的配置設定函數，如<code>malloc</code>。Python 并不是所有的對象生成都調用第0層，而是根據要配置設定記憶體的大小來選擇不同的配置設定方案：
申請的記憶體大于256位元組，使用第0層
申請的記憶體小于256位元組，使用第一層和第二層
基于經驗，我們是編碼過程中使用的大量對象都是小于256位元組的，并且生命周期很短，例如：
這個過程中如果頻繁調用<code>malloc</code>和<code>free</code>，效率就會很低。Python 通過增加第1層和第2層，并在第一層中會事先從第0層申請一些空間保留管理起來，當配置設定對象記憶體小于256時，使用這部分空間。
Python 管理的記憶體結構有3個部分：<code>block</code>、<code>pool</code>、<code>arena</code>，它們之間的關系如下：
arena 用來管理存儲 pool
pool 用來管理存儲 block
block 記憶體申請者可用的最小機關
為了避免頻繁調用<code>malloc()</code>和<code>free()</code>，第1層的配置設定器會以最大的機關 arena 來保留記憶體。pool 是用于有效管理空的block的機關。
第2層的配置設定器負責管理 pool 内的 block。将 block 的開頭位址傳回給申請者，并釋放 block 等。
配置設定器會将 pool 會按照8位元組的倍數的大小來分割後産出若幹個 block，如：8位元組的 block、16位元組的 block、24位元組的 block、... 256位元組的 block。申請記憶體時，會傳回适合大小的 block。
第3層是對象特有的配置設定器，Python 中各種内置類型：如：list、dict 等，又會有各自特有的配置設定器，比如 dict 的配置設定器長這樣：
在配置設定字典對象時，會先檢查空閑清單<code>free_list</code>是否有可用對象，如果已被用盡，再去通過第2層<code>PyObject_GC_New</code>去申請對象。
整體下來 Python 生成字典對象時的互動如下：
Python 内實作引用計數法，其實就是對各對象的引用數量變更做相應的操作，如果對象的引用數量增加，就在計數器上加1，反過來如果引用數量減少，就在計數器上減去1。
實際的計數操作由宏<code>Py_INCREF</code>來實作
<code>ob_refcnt</code>的類型在32位環境下是 int 型，在64位環境下是 long 型。因為有符号位，是以隻有一半數值能用非負整數表示。但是因為指針基本上都是按4位元組對齊的，是以即使引用計數器被所有指針引用，也不會溢出。
設計成允許存在負數是為了友善調試，當引用計數器存在負數數，就有減量操作過度或者增量操作遺留的可能。
實際的計數操作由宏<code>Py_DECREF</code>來實作
先将計數器将量，如果不為0，調用宏<code>_Py_CHECK_REFCNT</code>檢查引用計數器是否變為了負數。如果計數器為0，那麼就調用宏<code>_Py_Dealloc</code>，通過<code>Py_TYPE</code>識别對象的類型并調用對應的負責釋放各個對象的函數指針，比如：負責釋放元組對象的函數指針是<code>tupledealloc</code>。
成員<code>tp_free</code>存着對各個對象的釋放處理函數指針，大部分在其内部都是調用<code>PyObect_GC_Del</code>函數
元組的減量操作調用圖如下：
上面已經闡明了引用計數的核心操作就是計數+1和計數-1。需要明确的是，誰來去負責進行操作，比如：A 對象通過調用函數<code>func1</code>獲得了 B 對象，那麼 B 對象的引用計數+1應該由誰去負責呢？
這裡就涉及到“引用的所有權”， 即誰持有引用的所有權，誰就得承擔在不需要此引用時将對象的引用計數器減量的責任。
傳遞引用所有權（傳回值）
即函數方把引用的所有權和傳回值一起交給調用方。由函數的調用方在引用結束時負責執行減量操作。對象生成時，會把引用所有權交給調用方，比如：字典對象的生成
出借引用的所有權（傳回值）
即函數方隻把傳回值交給調用方，至于引用的所有權則隻是出借而已，調用方不能對引用計數進行減量操作。負責從“集合”中取出元素的函數，都是出借所有權，比如：元組擷取指定索引的函數
占據引用的所有權（參數）
即調用方把參數傳遞給函數時，函數方有時會占據這個參數的引用所有權，此時由函數方負責該參數的引用管理事宜。往連結清單中追加元素的函數都會占據參數的引用所有權，比如：向元組指定位置增加元素的函數
出借引用所有權（參數）
即調用方把參數的引用所有權借給函數方。當函數的調用方要出借引用的所有權時，從把對象交給函數之後直到函數執行結束為止，這段時間調用方都必須保留指向對象的引用的所有權。
引用計數法有一個缺陷，無法解決循環引用問題，當兩個對象之間互相引用，引用計數無法清零，即無法進行 GC。是以，對于循環引用，Python 通過<code>部分标記-清除算法</code>來解決。
比如下圖，左側的三個對象之前存在循環引用，導緻正常的引用計數無法将他們回收
我們先将他們目前的引用計數複制到另一塊區用于後面操作
有一個前提：Python 對象在生成時會将其自身連接配接到一個<code>對象連結清單</code>中（通過雙向指向互相連接配接），圖中用雙向箭頭表示
基于此，我們周遊<code>對象連結清單</code>中的所有對象，對他們所有引用的對象進行拷貝計數減一
現在進行<code>标記</code>操作了，我們将所有經過上步處理後拷貝計數仍然大于0的對象标記為“可達對象”，即有其他活動對象引用他們，并将他們所引用的對象也标記為可達對象，連接配接到可達對象連結清單中；然後将拷貝計數為0的對象記為“不可達對象”，連接配接到不可達對象連結清單。
可以看到，不可達對象中即為循環引用的對象，接下來進行<code>清除</code>操作，我們将不可達對象連結清單中的對象釋放記憶體，将可達對象連結清單中的對象重新連接配接會<code>對象連結清單</code>中
到此，我們完成了對循環引用對象的垃圾回收。
引起循環引用的根因是有些對象可能保留的指向其他對象的引用，對于這類對象，我們稱之為“容器對象”。
像元組、清單和字典等，都屬于容器對象，隻需要對這些容器對象解決循環引用的問題。容器對象中都被配置設定了用于循環引用垃圾回收的頭結構體。
正如前面所說，容器對象生成時，會被連接配接到<code>對象連結清單</code>，以字典對象為例，看一下他生成時代碼
<code>_PyObject_GC_TRACK</code>負責連接配接到<code>對象連結清單</code>中的操作
Python 将上面提到的容器對象連結清單劃分為“0代”、“1代”、“2代”，通過下面的結構體管理
一開始所有的容器對象都連接配接着0代的對象。當0代容器對象經過1次循環引用垃圾回收，仍然存活下來的對象晉升為1代；再次從循環引用垃圾回收過程中存活下來的對象晉升為2代。
在循環引用垃圾回收過程中，我們會将有<code>終結器</code>的對象從不可達連結清單中移除
之是以如此，是因為想要釋放循環引用的有終結器的對象是非常麻煩的。我們無法确定先釋放那個對象時合理的，如果先将第1個對象釋放，再釋放第二個對象時執行的終結器引用了第一個對象怎麼辦？
對于這些含有終結器的循環引用垃圾對象， Python 提供了全局變量<code>garbage</code>，讓開發者内從應用程式的角度來去移除對象的循環引用。
Python 的 GC 分為兩部分：
通過<code>引用計數算法</code>來管理正常對象的垃圾回收，并通過優化的記憶體結構來盡可能減少 GC
通過<code>分代+清除-标記</code>來管理循環引用對象的垃圾回收