串列的排隊人生
有些程式語言,例如 C 語言,對於陣列(Array)的設計,不僅只能放同一種型態的資料,還要事先知道要放多少個元素,這樣的好處是效能很好而且不會造成不必要的記憶體浪費,但對寫習慣動態增減元素的程式來說,用起來就有些不習慣。Python 的串列(List)沒有這樣的限制,可以放不同型態的資料,也可以隨時增加或減少元素,有什麼想裝的東西,不用管是數字、字串還是什麼型態,往裡面丟進去就對了,使用起來相當方便。
但是,CPython 是怎麼實作這樣的資料結構呢?又是怎麼動態的增加容量?這個章節就來看看串列是怎麼一回事。
串列的內部結構
在前面章節其實我們有稍微看過串列物件的結構,大概長這樣:
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
我們前面介紹的整數、浮點數以及字串,結構開頭用的是 PyObject_HEAD
,而在串列用的是 PyObject_VAR_HEAD
,來看看它們有什麼不同:
#define PyObject_HEAD PyObject ob_base;
#define PyObject_VAR_HEAD PyVarObject ob_base;
同樣都是定義一個 ob_base
成員,但 PyObject_HEAD
實際上是定義的型別是 PyObject
,而 PyObject_VAR_HEAD
是 PyVarObject
類型的。PyObject
我們之前就看過了,而 PyVarObject
結構如下:
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
PyVarObject
除了 PyObject
的基本結構外,還有一個 ob_size
成員,用來記錄串列裡的元素數量。當我們執行 len(["a", "b", "c"])
會得到 3,其實就是讀取這個 ob_size
的值。再回到 PyListObject
結構,ob_item
是一個指向 PyObject*
陣列的指針,這個陣列儲存了這個串列中所有元素的指針。
而 allocated
記錄了當前為 ob_item
陣列分配的記憶體空間,它通常大於或等於 ob_size
(也就是目前元素數量),待會我們也會看到這個數字是怎麼長大的。
串列的建立及初始化
當我們在 Python 中創建一個新的 List 時,CPython 會去找 PyList_Type
上的 tp_new
成員變數,這個成員指向一個 PyType_GenericNew()
函數:
PyObject *
PyType_GenericNew(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
return type->tp_alloc(type, 0);
}
這個函數其實沒做什麼事,就只是呼叫 tp_alloc
成員變數指向的函數,而在 PyList_Type
的 tp_alloc
是指向 PyType_GenericAlloc()
函數:
PyObject *
PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)
{
PyObject *obj = _PyType_AllocNoTrack(type, nitems);
if (obj == NULL) {
return NULL;
}
if (_PyType_IS_GC(type)) {
_PyObject_GC_TRACK(obj);
}
return obj;
}
這裡 _PyType_AllocNoTrack()
函數會根據不同型別的 type
參數以及要多少顆物件的 nitems
參數而跟系統索取足夠的記憶體空間,但是這個空間是怎麼計算的?繼續往下看:
PyObject *
_PyType_AllocNoTrack(PyTypeObject *type, Py_ssize_t nitems)
{
PyObject *obj;
const size_t size = _PyObject_VAR_SIZE(type, nitems+1);
const size_t presize = _PyType_PreHeaderSize(type);
char *alloc = PyObject_Malloc(size + presize);
// ... 略 ...
if (type->tp_itemsize == 0) {
_PyObject_Init(obj, type);
}
else {
_PyObject_InitVar((PyVarObject *)obj, type, nitems);
}
return obj;
}
首先,_PyObject_VAR_SIZE()
巨集是用來計算需要分配多少記憶體空間,它會怎麼算?
static inline size_t _PyObject_VAR_SIZE(PyTypeObject *type, Py_ssize_t nitems) {
size_t size = _Py_STATIC_CAST(size_t, type->tp_basicsize);
size += _Py_STATIC_CAST(size_t, nitems) * _Py_STATIC_CAST(size_t, type->tp_itemsize);
return _Py_SIZE_ROUND_UP(size, SIZEOF_VOID_P);
}
從 函數的名稱就看的出來這個函數並不是單純只給串列用的,只要是可以變大變小的物件都可以這個函數計算需要多少記憶體空間。計算公式也很簡單,tp_basicsize
是這個型態的基礎大小,tp_itemsize
是裡面每個元素的大小,nitems
就是看你想要幾顆元素,簡單的加法跟乘法就能算出來:
size = tp_basicsize + (tp_itemsize x nitems)
最後再執行 _Py_SIZE_ROUND_UP()
巨集進行「對齊(alignment)」,這個巨集展開後是這樣:
#define _Py_SIZE_ROUND_UP(n, a) (((size_t)(n) + \
(size_t)((a) - 1)) & ~(size_t)((a) - 1))
這個公式看起來好像有點複雜,其實就是要讓 n
變成 a
的倍數,以這個例子來說,SIZEOF_VOID_P
在 CPython 裡的定義是 8,也就是希望算出來會對齊到 8 的倍數,例如算出來的 size
如果是 61,它會被調整為 64,如果是 65,它會被調整為 72。
但為什麼要做這件事?對齊的目的是為了確保記憶體的存取效率,也是為了確保元素都能夠被正確的存取。
接下來 _PyType_PreHeaderSize()
函數會計算是否需要額外的記憶體空間,例如該顆物件是否需要被資源回收(Garbage Collection, GC),如果需要回收的話,就會因為需要存放一些 GC 相關的資訊而多分配一些記憶體空間。這個空間是固定的,不會因為元素的個數而改變。是說有借有還、再借不難,照理說記憶體空間如果不再使用 應該就要歸還給系統,但在 Python 有些物件是不會還的,例如之前介紹過從 -5 到 256 的小整數以及 True、False 跟 None 這些不死身物件都不用還。
最後,再根據計算結果,呼叫 PyObject_Malloc()
函數跟系統索取記憶體空間。
要到記憶體空間之後,就會根據 tp_itemsize
來決定是呼叫 _PyObject_Init()
還是 _PyObject_InitVar()
函數,這兩個函數做的事情差不多,甚至 _PyObject_InitVar()
也是呼叫 _PyObject_Init()
函數,只是多了一個 ob_size
的初始化。
而以 PyList_Type
的設定來說,它的 tp_itemsize
是 0,所以會呼叫 _PyObject_Init()
函數。但為什麼 tp_itemsize
是 0?剛剛不是才說是 tp_basicsize
加上 (tp_itemsize x nitems)
嗎?如果串列的 tp_itemsize
是 0 的話,它不用裝東西了嗎?事實上這些元素是另外擺放在別的地方,串列裡的這些記憶體格子只記錄這些元素擺放的位置,並不是真的的把這些元素放在串列的記憶體格子裡,這也合理,不然怎麼同時在一個串列裡放不同型態的物件呢?
到這裡,就完成了串列的初始化,接下來就可以開始往串列裡放東西了。
記憶體管理
串列的重要特性之一是它可以動態增加,但如果每次增加元素都重新索取記憶體,效能並不好。Python 在需要更多記憶體的時候,會「多要一點」,免得如果之後還要增加元素,又得再重新索取記憶體,可以減少重新索取記憶體的次數。有點像你跟爸媽要零用錢的時候一次多要一 些,就不用一直跟他們要錢,這種多要一點的策略叫做「過度分配」(over-allocation)。
整個計算的邏輯都定義在 list_resize()
函數裡:
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated, num_allocated_bytes;
Py_ssize_t allocated = self->allocated;
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SET_SIZE(self, newsize);
return 0;
}
// ... 略 ...
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
// ... 略 ...
self->ob_item = items;
Py_SET_SIZE(self, newsize);
self->allocated = new_allocated;
return 0;
}
需要更多記憶體?
首先檢查是否真的需要重新分配,如果目前空間還夠用,就只會直接更新 ob_size
的值就好。什麼叫「夠用」呢?
- 當前分配的空間(allocated)大於或等於需要的新的空間(newsize)。
- 新的空間(newsize)大於或等於當前分配空間的一半(
allocated >> 1
其實就是除以 2 的意思)。
這兩個條件都要同時滿足才叫夠用,如果不夠用,就會再去要更多的記憶體,然後重新分配。舉幾個例子: