深入理解Python虛擬機中列表(list)的實現(xiàn)原理及源碼剖析

更新時間：2023年03月08日 08:21:10 作者：一無是處的研究僧

在本篇文章當(dāng)中主要給大家介紹?cpython?虛擬機當(dāng)中針對列表的實現(xiàn)，在?Python?中，List?是一種非常常用的數(shù)據(jù)類型，可以存儲任何類型的數(shù)據(jù)，并且支持各種操作，如添加、刪除、查找、切片等，在本篇文章當(dāng)中將深入去分析這一點是如何實現(xiàn)的

列表的結(jié)構(gòu)

在 cpython 實現(xiàn)的 python 虛擬機當(dāng)中，下面就是 cpython 內(nèi)部列表實現(xiàn)的源代碼：

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;
 
    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;
 
#define PyObject_VAR_HEAD      PyVarObject ob_base;
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
 
typedef struct _object {
    _PyObject_HEAD_EXTRA // 這個宏定義為空
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

將上面的結(jié)構(gòu)體展開之后，PyListObject 的結(jié)構(gòu)大致如下所示：

現(xiàn)在來解釋一下上面的各個字段的含義：

Py_ssize_t，一個整型數(shù)據(jù)類型。
ob_refcnt，表示對象的引用記數(shù)的個數(shù)，這個對于垃圾回收很有用處，后面我們分析虛擬機中垃圾回收部分在深入分析。
ob_type，表示這個對象的數(shù)據(jù)類型是什么，在 python 當(dāng)中有時候需要對數(shù)據(jù)的數(shù)據(jù)類型進行判斷比如 isinstance, type 這兩個關(guān)鍵字就會使用到這個字段。
ob_size，這個字段表示這個列表當(dāng)中有多少個元素。
ob_item，這是一個指針，指向真正保存 python 對象數(shù)據(jù)的地址，大致的內(nèi)存他們之間大致的內(nèi)存布局如下所示：

allocated，這個表示在進行內(nèi)存分配的時候，一共分配了多少個 (PyObject *) ，真實分配的內(nèi)存空間為 allocated * sizeof(PyObject *)。

列表操作函數(shù)源代碼分析

創(chuàng)建列表

首先需要了解的是在 python 虛擬機內(nèi)部為列表創(chuàng)建了一個數(shù)組，所有的創(chuàng)建的被釋放的內(nèi)存空間，并不會直接進行釋放而是會將這些內(nèi)存空間的首地址保存到這個數(shù)組當(dāng)中，好讓下一次申請創(chuàng)建新的列表的時候不需要再申請內(nèi)存空間，而是直接將之前需要釋放的內(nèi)存直接進行復(fù)用即可。

/* Empty list reuse scheme to save calls to malloc and free */
#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;

free_list，保存被釋放的內(nèi)存空間的首地址。
numfree，目前 free_list 當(dāng)中有多少個地址是可以被使用的，事實上是 free_list 前 numfree 個首地址是可以被使用的。

創(chuàng)建鏈表的代碼如下所示（為了精簡刪除了一些代碼只保留核心部分）：

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;
 
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
    nbytes = size * sizeof(PyObject *);
  // 如果 numfree 不等于 0 那么說明現(xiàn)在 free_list 有之前使用被釋放的內(nèi)存空間直接使用這部分即可
    if (numfree) {
        numfree--;
        op = free_list[numfree]; // 將對應(yīng)的首地址返回
        _Py_NewReference((PyObject *)op); // 這條語句的含義是將 op 這個對象的 reference count 設(shè)置成 1
    } else {
      // 如果沒有空閑的內(nèi)存空間 那么就需要申請內(nèi)存空間 這個函數(shù)也會對對象的 reference count 進行初始化 設(shè)置成 1
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
  /* 下面是申請列表對象當(dāng)中的 ob_item 申請內(nèi)存空間，上面只是給列表本身申請內(nèi)存空間，但是列表當(dāng)中有許多元素
  	保存這些元素也是需要內(nèi)存空間的 下面便是給這些對象申請內(nèi)存空間
  */
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
      // 如果申請內(nèi)存空間失敗 則報錯
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
      // 對元素進行初始化操作 全部賦值成 0
        memset(op->ob_item, 0, nbytes);
    }
  // Py_SIZE 是一個宏
    Py_SIZE(op) = size; // 這條語句會被展開成 (PyVarObject*)(ob))->ob_size = size
  // 分配數(shù)組的元素個數(shù)是 size
    op->allocated = size;
  // 下面這條語句對于垃圾回收比較重要 主要作用就是將這個列表對象加入到垃圾回收的鏈表當(dāng)中
  // 后面如果這個對象的 reference count 變成 0 或者其他情況 就可以進行垃圾回收了
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

在 cpython 當(dāng)中，創(chuàng)建鏈表的字節(jié)碼為 BUILD_LIST，我們可以在文件 ceval.c 當(dāng)中找到對應(yīng)的字節(jié)碼對應(yīng)的執(zhí)行步驟：

TARGET(BUILD_LIST) {
    PyObject *list =  PyList_New(oparg);
    if (list == NULL)
        goto error;
    while (--oparg >= 0) {
        PyObject *item = POP();
        PyList_SET_ITEM(list, oparg, item);
    }
    PUSH(list);
    DISPATCH();
}

從上面 BUILD_LIST 字節(jié)碼對應(yīng)的解釋步驟可以知道，在解釋執(zhí)行字節(jié)碼 BUILD_LIST 的時候確實調(diào)用了函數(shù) PyList_New 創(chuàng)建一個新的列表。

列表 append 函數(shù)

static PyObject *
// 這個函數(shù)的傳入?yún)?shù)是列表本身 self 需要 append 的元素為 v
  // 也就是將對象 v 加入到列表 self 當(dāng)中
listappend(PyListObject *self, PyObject *v)
{
    if (app1(self, v) == 0)
        Py_RETURN_NONE;
    return NULL;
}
 
static int
app1(PyListObject *self, PyObject *v)
{
  // PyList_GET_SIZE(self) 展開之后為 ((PyVarObject*)(self))->ob_size
    Py_ssize_t n = PyList_GET_SIZE(self);
 
    assert (v != NULL);
  // 如果元素的個數(shù)已經(jīng)等于允許的最大的元素個數(shù) 就報錯
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }
	// 下面的函數(shù) list_resize 會保存 ob_item 指向的位置能夠容納最少 n+1 個元素（PyObject *）
  // 如果容量不夠就會進行擴容操作
    if (list_resize(self, n+1) == -1)
        return -1;
		
  // 將對象 v 的 reference count 加一 因為列表當(dāng)中使用了一次這個對象 所以對象的引用計數(shù)需要進行加一操作
    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v); // 宏展開之后 ((PyListObject *)(op))->ob_item[i] = v
    return 0;
}

列表的擴容機制

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;
 
    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
  // 如果列表已經(jīng)分配的元素個數(shù)大于需求個數(shù) newsize 的就直接返回不需要進行擴容
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }
 
    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
  // 這是核心的數(shù)組大小擴容機制 new_allocated 表示新增的數(shù)組大小
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
 
    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }
 
    if (newsize == 0)
        new_allocated = 0;
    items = self->ob_item;
    if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
      	// PyMem_RESIZE 這是一個宏定義 會申請 new_allocated 個數(shù)元素并且將原來數(shù)組的元素拷貝到新的數(shù)組當(dāng)中
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
  // 如果沒有申請到內(nèi)存 那么報錯
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
  // 更新列表當(dāng)中的元素數(shù)據(jù)
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

在上面的擴容機制下，數(shù)組的大小變化大致如下所示：

newsize≈size⋅(size+1)1/8

列表的插入函數(shù) insert

在列表當(dāng)中插入一個數(shù)據(jù)比較簡單，只需要將插入位置和其后面的元素往后移動一個位置即可，整個過程如下所示：

在 cpython 當(dāng)中列表的插入函數(shù)的實現(xiàn)如下所示：

參數(shù) op 表示往哪個鏈表當(dāng)中插入元素。
參數(shù) where 表示在鏈表的哪個位置插入元素。
參數(shù) newitem 表示新插入的元素。

int
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{
  // 檢查是否是列表類型
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
  // 如果是列表類型則進行插入操作
    return ins1((PyListObject *)op, where, newitem);
}
 
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
  // 如果列表的元素個數(shù)超過限制 則進行報錯
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }
  // 確保列表能夠容納 n + 1 個元素
    if (list_resize(self, n+1) == -1)
        return -1;
  // 這里是 python 的一個小 trick 就是下標(biāo)能夠有負數(shù)的原理
    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];
  // 因為鏈表應(yīng)用的對象，因此對象的 reference count 需要進行加一操作
    Py_INCREF(v);
  // 在列表當(dāng)中保存對象 v 
    items[where] = v;
    return 0;
}

列表的刪除函數(shù) remove

對于數(shù)組 ob_item 來說，刪除一個元素就需要將這個元素后面的元素往前移動，因此整個過程如下所示：

static PyObject *
listremove(PyListObject *self, PyObject *v)
{
    Py_ssize_t i;
  	// 編譯數(shù)組 ob_item 查找和對象 v 相等的元素并且將其刪除
    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
        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;
    }
  	// 如果沒有找到這個元素就進行報錯處理 在下面有一個例子重新編譯 python 解釋器 將這個錯誤內(nèi)容修改的例子
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

執(zhí)行的 python 程序內(nèi)容為：

data = []
data.remove(1)

下面是整個修改內(nèi)容和報錯結(jié)果：

從上面的結(jié)果我們可以看到的是，我們修改的錯誤信息正確打印了出來。

列表的統(tǒng)計函數(shù) count

這個函數(shù)的主要作用就是統(tǒng)計列表 self 當(dāng)中有多少個元素和 v 相等。

static PyObject *
listcount(PyListObject *self, PyObject *v)
{
    Py_ssize_t count = 0;
    Py_ssize_t i;
 
    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
      // 如果相等則將 count 進行加一操作
        if (cmp > 0)
            count++;
      // 如果出現(xiàn)錯誤就返回 NULL
        else if (cmp < 0)
            return NULL;
    }
  // 將一個 Py_ssize_t 的變量變成 python 當(dāng)中的對象
    return PyLong_FromSsize_t(count);
}

列表的拷貝函數(shù) copy

這是列表的淺拷貝函數(shù)，它只拷貝了真實 python 對象的指針，并沒有拷貝真實的 python 對象，從下面的代碼可以知道列表的拷貝是淺拷貝，當(dāng) b 對列表當(dāng)中的元素進行修改時，列表 a 當(dāng)中的元素也改變了。如果需要進行深拷貝可以使用 copy 模塊當(dāng)中的 deepcopy 函數(shù)。

>>> a = [1, 2, [3, 4]]
>>> b = a.copy()
>>> b[2][1] = 5
>>> b
[1, 2, [3, 5]]

copy 函數(shù)對應(yīng)的源代碼（listcopy）如下所示：

static PyObject *
listcopy(PyListObject *self)
{
    return list_slice(self, 0, Py_SIZE(self));
}
 
static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
  // Py_SIZE(a) 返回列表 a 當(dāng)中元素的個數(shù)（注意不是數(shù)組的長度 allocated）
    PyListObject *np;
    PyObject **src, **dest;
    Py_ssize_t i, len;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    len = ihigh - ilow;
    np = (PyListObject *) PyList_New(len);
    if (np == NULL)
        return NULL;
 
    src = a->ob_item + ilow;
    dest = np->ob_item;
  // 可以看到這里循環(huán)拷貝的是指向真實 python 對象的指針 并不是真實的對象
    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
      // 同樣的因為并沒有創(chuàng)建新的對象，但是這個對象被新的列表使用到啦 因此他的 reference count 需要進行加一操作 Py_INCREF(v) 的作用：將對象 v 的 reference count 加一
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
}

下圖就是使用 a.copy() 淺拷貝的時候，內(nèi)存的布局的示意圖，可以看到列表指向的對象數(shù)組發(fā)生了變化，但是數(shù)組中元素指向的 python 對象并沒有發(fā)生變化。

下面是對列表對象進行深拷貝的時候內(nèi)存的大致示意圖，可以看到數(shù)組指向的 python 對象也是不一樣的。

列表的清空函數(shù) clear

當(dāng)我們在使用 list.clear() 的時候會調(diào)用下面這個函數(shù)。清空列表需要注意的就是將表示列表當(dāng)中元素個數(shù)的 ob_size 字段設(shè)置成 0 ，同時將列表當(dāng)中所有的對象的 reference count 設(shè)置進行 -1 操作，這個操作是通過宏 Py_XDECREF 實現(xiàn)的，這個宏還會做另外一件事就是如果這個對象的引用計數(shù)變成 0 了，那么就會直接釋放他的內(nèi)存。

static PyObject *
listclear(PyListObject *self)
{
    list_clear(self);
    Py_RETURN_NONE;
}
 
static int
list_clear(PyListObject *a)
{
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
        /* Because XDECREF can recursively invoke operations on
           this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i >= 0) {
            Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
       Note that there is no guarantee that the list is actually empty
       at this point, because XDECREF may have populated it again! */
    return 0;
}

列表反轉(zhuǎn)函數(shù) reverse

在 python 當(dāng)中如果我們想要反轉(zhuǎn)類表當(dāng)中的內(nèi)容的話，就會使用這個函數(shù) reverse 。

>>> a = [i for i in range(10)]
>>> a.reverse()
>>> a
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

其對應(yīng)的源程序如下所示：

static PyObject *
listreverse(PyListObject *self)
{
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    Py_RETURN_NONE;
}
 
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);
 
    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

上面的源程序還是比較容易理解的，給 reverse_slice 傳遞的參數(shù)就是保存數(shù)據(jù)的數(shù)組的首尾地址，然后不斷的將首尾數(shù)據(jù)進行交換（其實是交換指針指向的地址）。

總結(jié)

本文介紹了 Python 中列表對象的實現(xiàn)細節(jié)，介紹了一些常用函數(shù)的實現(xiàn)，包括列表的擴容機制，插入、刪除、統(tǒng)計、拷貝、清空和反轉(zhuǎn)等操作的實現(xiàn)方式。

列表的擴容機制采用了一種線性時間攤銷的方式，使得列表的插入操作具有較好的時間復(fù)雜度。
列表的插入、刪除和統(tǒng)計操作都是通過操作ob_item 數(shù)組實現(xiàn)的，其中插入和刪除操作需要移動數(shù)組中的元素。
列表的拷貝操作是淺拷貝，需要注意的是進行深拷貝需要使用 copy 模塊當(dāng)中的 deepcopy 函數(shù)。
列表清空會將 ob_size 字段設(shè)置成 0，同時需要將列表當(dāng)中的所有對象的 reference count 進行 -1 操作，從而避免內(nèi)存泄漏。
列表的反轉(zhuǎn)操作可以通過交換 ob_item 數(shù)組中前后元素的位置實現(xiàn)。

總之，了解 Python 列表對象的實現(xiàn)細節(jié)有助于我們更好地理解 Python 的內(nèi)部機制，從而編寫更高效、更可靠的 Python 代碼。

以上就是深入理解Python虛擬機中列表(list)的實現(xiàn)原理及源碼剖析的詳細內(nèi)容，更多關(guān)于Python虛擬機列表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: