源码分析Python的List的列表容器

一、背景

列表list是Python开发中常用的数据结构之一，同样，其他语言中也有类似的数据结构，例如C++中的vector，Golang中的list, Java中的ArrayList等。list在Python底层是基于动态数组，给个通俗的名字—指针数组实现的，但实现的方式在每个语言中可能不完全相同。接下来，就来探究下list底层的数据结构，来学习一下Python的list相关操作集，动态扩容机制以及如何在内存的使用上进行优化的。本篇文章所使用的的Python版本为3.10。

二、list所设计的数据结构

list结构体对应的代码位于/cpython/listobject.h

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;  /* 动态数组中存放的是真实对象的指针，即指针数组*/
    Py_ssize_t allocated;
} PyListObject;

list对象，是可变对象，相比于不可变对象的数据结构来说，增加了ob_size字段。因此PyObject_VAR_HEAD如下:

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* 数组中的长度 */
} PyVarObject;

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
} PyObject;

说明:

ob_refcnt：对象的引用计数值。
ob_type：对象的类型。
ob_size：数组中已使用的元素的个数。
ob_item：指针指向存放指针的数组，即指针数组。
allocated：数组中的总容量。
list中包含的是每个指向ob_item对应位置的指针，所以使用**ob_item等价于*ob_item[]

三、 list相关的操作集

list相关的部分操作集位于/Include/listobject.h，还有一部分位于/Objects/listobject.c中

PyAPI_FUNC(PyObject *) PyList_New(Py_ssize_t size);
PyAPI_FUNC(Py_ssize_t) PyList_Size(PyObject *);

PyAPI_FUNC(PyObject *) PyList_GetItem(PyObject *, Py_ssize_t);
PyAPI_FUNC(int) PyList_SetItem(PyObject *, Py_ssize_t, PyObject *);
PyAPI_FUNC(int) PyList_Insert(PyObject *, Py_ssize_t, PyObject *);
PyAPI_FUNC(int) PyList_Append(PyObject *, PyObject *);

PyAPI_FUNC(PyObject *) PyList_GetSlice(PyObject *, Py_ssize_t, Py_ssize_t);
PyAPI_FUNC(int) PyList_SetSlice(PyObject *, Py_ssize_t, Py_ssize_t, PyObject *);

PyAPI_FUNC(int) PyList_Sort(PyObject *);
PyAPI_FUNC(int) PyList_Reverse(PyObject *);
PyAPI_FUNC(PyObject *) PyList_AsTuple(PyObject *);

static PySequenceMethods list_as_sequence = {
    (lenfunc)list_length,                       /* sq_length */
    (binaryfunc)list_concat,                    /* sq_concat */
    (ssizeargfunc)list_repeat,                  /* sq_repeat */
    (ssizeargfunc)list_item,                    /* sq_item */
    0,                                          /* sq_slice */
    (ssizeobjargproc)list_ass_item,             /* sq_ass_item */
    0,                                          /* sq_ass_slice */
    (objobjproc)list_contains,                  /* sq_contains */
    (binaryfunc)list_inplace_concat,            /* sq_inplace_concat */
    (ssizeargfunc)list_inplace_repeat,          /* sq_inplace_repeat */
};

1.首先，来看下PyList_GetItem函数和PyList_SetItem函数。

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    // 检查对象的类型
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    // 检查索引是否超过数组长度
    if (!valid_index(i, Py_SIZE(op))) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    // 返回动态数组中的指针
    return ((PyListObject *)op) -> ob_item[i]; 
}


int
PyList_SetItem(PyObject *op, Py_ssize_t i,
               PyObject *newitem)
{
    PyObject **p;
    if (!PyList_Check(op)) {
        Py_XDECREF(newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    // 检查索引是否超过数组长度
    if (!valid_index(i, Py_SIZE(op))) {
        Py_XDECREF(newitem);
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    // 指针赋值, 地址偏移i个元素，在64位机器上指针大小为8字节，因此总偏移量为i*8字节
    p = ((PyListObject *)op) -> ob_item + i;
    Py_XSETREF(*p, newitem);
    return 0;
}

说明：

(1).PyList_GetItem函数和PyList_SetItem函数前两步都是判断对象类型以及检查索引是否超过数组的长度。

(2).由于Python中处处皆对象，因此容器中存放的是对象的指针，a = list[0], a即指向ob_items[0]的指针。

(3).PyList_SetItem中的赋值操作是对指针进行赋值，因此首先需要计算第i个元素指针的位置，这里采用了地址偏移的集散方式，地址偏移i个元素，因为每个元素为指针，在64位机器上占8个字节，因此总偏移量为i*8字节，然后将newitem指针覆盖p指针。

2.在指定位置插入元素的PyList_Insert函数和追加元素的PyList_Append函数。

/* 带了动态扩容的数组的插入, 平均时间复杂度为0(N) */
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;
    }

    // 数组长度是否小于最大限度, 小于size_t = 0 ~ 2^64, (size_t)-1)>>1
    assert((size_t)n + 1 < PY_SSIZE_T_MAX);
    // 动态扩容
    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];
    // 增加引用计数
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

/* 追加元素, 时间复杂度为O(1) */
static int
app1(PyListObject *self, PyObject *v)
{
    Py_ssize_t n = PyList_GET_SIZE(self);

    assert (v != NULL);
    assert((size_t)n + 1 < PY_SSIZE_T_MAX);
    if (list_resize(self, n+1) < 0)
        return -1;

    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    return 0;
}

四、 list的动态扩(缩)容机制

list动态扩(缩)容对应的函数为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;

    /* 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.
    */
    
    /* 如果newsize小于allocated并且newsize大于总容量的一半，小于总容量，无需扩缩容 */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_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().
     * Add padding to make the allocated size multiple of 4.
     * 数组容量大小始终为4的倍数
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    // 使得数组容量大小始终为4的倍数
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    /* Do not overallocate if the new size is closer to overallocated size
     * than to the old size.
     */
    if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
        new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

    if (newsize == 0)
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    // 为申请新的大小的数组空间并拷贝数组
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    // 替换掉items和allocated
    self->ob_item = items;
    Py_SET_SIZE(self, newsize);
    self->allocated = new_allocated;
    return 0;
}

说明：

(1).动态扩(缩)容机制的核心在于计算new_allocated大小。

(2).在python3.6左右的版本中，new_allocated的大小为`new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

新容量大小在之前容量的基础上加1/8的容量,再加上3或6的容量。
加上3或6的容量为了避免频繁扩容。
当newsize < 9时，加上3的容量，当newsize > 9 时，加上6的容量，减小当处理扩容小数据集的时候，减少内存的浪费。

(3).在python3.9左右的版本中，也就是上述对应代码段中，相比于之前的版本，做了优化。

新容量大小在之前容量的基础上添加1/8的容量，再加上6的容量，然后& ~(size_t)3，这样得到的心容量大小恒为4的整数倍。

(4).PyMem_Realloc函数的功能主要分为三步：

首先分配一个大小为num_allocated_bytes字节的内存块
将旧内存块中的ptr(ob_items), 拷贝到新申请的内存空间。
释放旧内存块，并返回新的内存块。

五、 list对象申请和释放的内存管理

1.首先，来看下list对象的申请过程对应的函数PyList_New，源码位于/Objects/listobjects.py中

/* 在BUILD_LIST字节码中被调用 */
PyObject *
PyList_New(Py_ssize_t size)
{
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }

    // 获取执行程序所处的解释器中本地线程中的状态, state是个双向链表, 从状态集中获取list缓存数组。
    // state对象存在于local thread的上下文中
    struct _Py_list_state *state = get_list_state();
    // 定义指针
    PyListObject *op;
#ifdef Py_DEBUG
    // PyList_New() must not be called after _PyList_Fini()
    assert(state->numfree != -1);
#endif
    // 检查这个list缓存池中是否还有剩余空间, 如果存在, 从缓存池中取出list对象
    if (state->numfree) {
        state->numfree--;
        op = state->free_list[state->numfree];
        _Py_NewReference((PyObject *)op);
    }
    // 开辟新的空间, 创建PyListObject对象
    else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL) {
            return NULL;
        }
    }
    if (size <= 0) {
        op->ob_item = NULL;
    }
    else {
        // 为数组开辟空间
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    // 设定op->size和op->allocated
    Py_SET_SIZE(op, size);
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

六、总结：

未完待续~

C Python 源码分析数据结构

Python 源码分析数据结构 C

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

源码分析CPython中的垃圾回收机制上一篇

多进程通信之基于mmap的共享内存和文件锁下一篇

源码分析Python的List的列表容器

一 、背景

二 、list所设计的数据结构

三 、 list相关的操作集