本文同步刊載於 「為你自己學 Python - 串列的排隊人生」

串列的排隊人生

有些程式語言，例如 C 語言，對於陣列（Array）的設計，不僅只能放同一種型態的資料，還要事先知道要放多少個元素，這樣的好處是效能很好而且不會造成不必要的記憶體浪費，但對寫習慣動態增減元素的程式來說，用起來就有些不習慣。Python 的串列（List）沒有這樣的限制，可以放不同型態的資料，也可以隨時增加或減少元素，有什麼想裝的東西，不用管是數字、字串還是什麼型態，往裡面丟進去就對了，使用起來相當方便。

但是，CPython 是怎麼實作這樣的資料結構呢？又是怎麼動態的增加容量？這個章節就來看看串列是怎麼一回事。

串列的內部結構

在前面章節其實我們有稍微看過串列物件的結構，大概長這樣：

// 檔案：Include/cpython/listobject.h

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

我們前面介紹的整數、浮點數以及字串，結構開頭用的是 PyObject_HEAD，而在串列用的是 PyObject_VAR_HEAD，來看看它們有什麼不同：

// 檔案：Include/object.h

#define PyObject_HEAD          PyObject ob_base;
#define PyObject_VAR_HEAD      PyVarObject ob_base;

同樣都是定義一個 ob_base 成員，但 PyObject_HEAD 實際上是定義的型別是 PyObject，而 PyObject_VAR_HEAD 是 PyVarObject 類型的。PyObject 我們之前就看過了，而 PyVarObject 結構如下：

// 檔案：Include/object.h

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() 函數：

// 檔案：Objects/typeobject.c

PyObject *
PyType_GenericNew(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    return type->tp_alloc(type, 0);
}

這個函數其實沒做什麼事，就只是呼叫 tp_alloc 成員變數指向的函數，而在 PyList_Type 的 tp_alloc 是指向 PyType_GenericAlloc() 函數：

// 檔案：Objects/typeobject.c

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 參數而跟系統索取足夠的記憶體空間，但是這個空間是怎麼計算的？繼續往下看：

// 檔案：Objects/object.c

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() 巨集是用來計算需要分配多少記憶體空間，它會怎麼算？

// 檔案：Include/cpython/objimpl.h

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）」，這個巨集展開後是這樣：

// 檔案：Include/pymacro.h

#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() 函數裡：

// 檔案：Objects/listobject.c

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 的值就好。什麼叫「夠用」呢？

1. 當前分配的空間（allocated）大於或等於需要的新的空間（newsize）。
2. 新的空間（newsize）大於或等於當前分配空間的一半（allocated >> 1 其實就是除以 2 的意思）。

這兩個條件都要同時滿足才叫夠用，如果不夠用，就會再去要更多的記憶體，然後重新分配。舉幾個例子：

1. 增加元素，但在當前容量內

原本分配 8 格，目前已用 5 格，想要再增加 2 個元素，newsize 就是 5 + 2 = 7，因為 8 >= 7 而且 7 >= 4，所以不需要重新分配，直接更新 ob_size 到 7。

2. 增加元素，而且超過目前容量

原本分配 10 格而且已用滿 10 格，想要再加 1 個元素，newsize 等於 11，因為 10 >= 11 不成立，需要重新分配。

3. 減少元素，但不到一半

原本分配 16 格，目前已用了 16 格，都沒剩了，這時如果刪除 5 個元素，newsize 就是 16 - 5 = 11，因為 16 >= 11 且 11 >= 8，所以不用重新分配，直接更新 ob_size 為 11。

4. 大幅減少元素

原本分配 100 格而且已全部用滿 100 格，如果一口氣刪除 80 個元素，newsize 就是 100 - 80 = 20，雖然 100 >= 20 但 20 < 50，所以需要重新分配。

5. 清空列表

原本分配 10 格，只用了 5 格，當要清空列表時，newsize 等於 0，因為 10 >= 0 但 0 < 5，所以需要重新分配。

附帶一提，在 Python 裡有好幾種清空串列的手法，例如：

numbers = [9, 5, 2, 7]

# 方法 1
numbers.clear()

# 方法 2
numbers = []

呼叫串列身上的 .clear() 方法，這會直接觸發 list_resize() 函數而進行計算是否需要重新分配，這是 C 語言實作的函數，效能很好。如果是方法二，實際上是建立一個新的空串列，並將變數指向這個新串列。原串列如果沒有其他引用，會被垃圾回收，這個做法的效能會比較差一些。

過度分配的公式

過度分配的計算公式就寫在 list_resize() 函數裡，：

// 檔案：Objects/listobject.c

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    // ... 略 ...

    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;

    // ... 略 ...
}

new_allocated 的計算規則有分不同的條件...我們先來看看第一行。除了根據 newsize 來計算外，還會額外再多要一點 newsize >> 3，>> 3 其實就是除以 8，這樣就是 newsize 的 1/8。最後加 6 是因為對於比較小的列表可以確保有一定的增長空間，避免頻繁的重新分配，這也跟最後的 ~(size_t)3 有關，這個運算是為了對齊記憶體，讓分配的記憶體空間是 4 的倍數。

舉個例子，如果 newsize 是 1，計算公式是：

1 + (1 >> 3) + 6 = 1 + 0 + 6 = 7

經過對齊之後，向下調整到 4 的倍數後為 4。如果 newsize 是 5：

5 + (5 >> 3) + 6 = 5 + 0 + 6 = 11

經過對齊之後，向下調整到 4 的倍數後為 8。

正因為這個公式，產生的數字都會是 4 的倍數，像是 0, 4, 8, 16, 24, 32, 40, 52, 64, 76,...。如果有看懂這個計算公式，也可想想如果少了這個加 6，對於比較小的串列每次增加元素都會重新分配記憶體，效能就沒那麼好了，所以多加一點可能會造成一點點的浪費，但對於效能來說是值得的。

那麼接下來的那段 if 判斷是在做什麼事？那段的目的是防止串列突然大幅增加的時候過度分配記憶體，舉例來說，如果目前分配的是 100 格，想要來討 1,000 格，也就是 newsize 是 1,000。如果沒有這個檢查，重新分配的結果是 1,000 + 1,000/8 + 6 = 1,125，再對齊到 4 的倍數，就是 1,128。如果有檢查，只會分配到 1,000 + 3 = 1,003，對齊之後是 1,004。

常見串列操作

接下來，我們來看看串列一些主要操作是如何做的。要看串列物件身上的方法，就得去看看 PyList_Type 的 tp_methods 成員變數，這裡我們來看看 append、insert 以及 remove 這三個方法是怎麼實作的。

增加元素

串列的 .append() 方法在 C 層面上對應的是 list_append 函數：

// 檔案：Objects/listobject.c

static PyObject *
list_append(PyListObject *self, PyObject *object)
{
    if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {
        return NULL;
    }
    Py_RETURN_NONE;
}

看起來重點就是 _PyList_AppendTakeRef() 了，再往裡面追：

// 檔案：Include/internal/pycore_list.h

static inline int
_PyList_AppendTakeRef(PyListObject *self, PyObject *newitem)
{
    assert(self != NULL && newitem != NULL);
    assert(PyList_Check(self));
    Py_ssize_t len = PyList_GET_SIZE(self);
    Py_ssize_t allocated = self->allocated;
    assert((size_t)len + 1 < PY_SSIZE_T_MAX);
    if (allocated > len) {
        PyList_SET_ITEM(self, len, newitem);
        Py_SET_SIZE(self, len + 1);
        return 0;
    }
    return _PyList_AppendTakeRefListResize(self, newitem);
}

allocated 就是目前已分配到的空間，len 則是會取得 ob_size，也就是目前元素個數。如果已分配的空間足夠，直接添加新元素到串列的最後面，並更新串列的長度，這個的速度是比較快的。但如果不夠，就要呼叫 _PyList_AppendTakeRefListResize() 函數來進行重新分配記憶體空間了，追進去就會看到它在呼叫我們剛剛介紹的 list_resize() 函數。

插入元素

串列的 .insert() 方法對應的是 list_insert 函數：

// 檔案：Objects/listobject.c

static PyObject *
list_insert(PyListObject *self, PyObject *const *args, Py_ssize_t nargs)
{
    // ... 略 ...
    return_value = list_insert_impl(self, index, object);

    // ... 略 ...
}

扣掉一些參數檢查程式碼，主要的邏輯在 list_insert_impl() 函數：

// 檔案：Objects/listobject.c

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    // ... 略 ...
    if (list_resize(self, n+1) < 0)
        return -1;

    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    items[where] = Py_NewRef(v);
    return 0;
}

可以看到也有呼叫 list_resize() 函數，這是因為插入元素會增加串列的長度，所以也要檢查是否需要重新分配記憶體空間。可以看到其實最後也就是跑一個 for 迴圈，把第 i 個元素往後移到 i + 1 的位置，再把新元素放到 where 的位置，還滿直覺的。

刪除元素

最後來看看刪除元素的 .remove() 方法，對應的是 list_remove 函數：

// 檔案：Objects/listobject.c

static PyObject *
list_remove(PyListObject *self, PyObject *value)
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        PyObject *obj = self->ob_item[i];
        Py_INCREF(obj);
        int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        Py_DECREF(obj);
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

這裡跑個 for 迴圈，逐個比對是否有要刪除的元素，如果沒有符合的元素，就會顯示錯誤訊息：

>>> numbers = [9, 5, 2, 7]
>>> numbers.remove(100)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: list.remove(x): x not in list

如果有比對到，就會執行 list_ass_slice() 函數，而這個函數，其實是在對這個串列做切片操作。那個 ass 不是屁股，是 assign 的意思。上面那段 list_ass_slice() 的操作如果你要換成等效的 Python 語法，相當於 self[i:i+1] = []，這個操作會刪除索引 i 的元素。

本文同步刊載於 「為你自己學 Python - 串列的排隊人生」