list源码解析:动态数组精讲

list 对象是一种 容量自适应 的 线性容器 ,底层由 动态数组 实现。 动态数组结构决定了 list 对象具有优秀的尾部操作性能,但头部操作性能却很差劲。 研发人员只有对底层数据结构有足够的认识,才能最大限度避免问题代码。

现成的动态数组实现很多,除了我们正在研究的 list 对象,C++ 中的 vector 也是众所周知。 虽然在实际项目中需要自行实现动态数组的场景已经很少很少了,但是源码还是有必要研究一番。 源码研究不仅能加深对数据结构的理解,还能进一步提升编程水平,裨益颇多。

本节,我们开始 list 对象源码,深入学习 动态数组 实现的艺术。

容量调整

当我们调用 append 、pop 、insert 等方法时,列表长度随之发生变化。 当列表长度超过底层数组容量时,便需要对底层数组进行 扩容 ; 当列表长度远低于底层数组容量时,便需要对底层数组进行 缩容 。

Objects/listobject.c 源码表明,append 等方法依赖 list_resize 函数调整列表长度,扩容缩容的秘密就藏在这里! list_resize 函数在调整列表长度前,先检查底层数组容量,并在必要时重新分配底层数组。 接下来,我们一起来解读 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.
    */
    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, ...
    * 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.
    */
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }

    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;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

在函数开头,有几个局部变量定义,对理解函数逻辑非常关键:

  • items 指针,用于保存新数组;

  • new_allocated ,用于保存新数组容量;

  • num_allocated_bytes ,用于保存新数组内存大小,以字节为单位;

  • allocated ,用于保存旧数组容量;

然后,代码第 12 行,检查新长度与底层数组容量的关系。 如果新长度不超过数组容量,且不小于数组容量的一半,则无需调整底层数组,直接更新 ob_size 字段。 换句话讲, list 对象扩缩容的条件分别如下:

  • 扩容条件 ,新长度大于底层数组长度;

  • 缩容条件 ,新长度小于底层数组长度的一半;

扩容或缩容条件触发时,list_resize 函数根据新长度计算数组容量并重新分配底层数组(第 27-44 行):

  1. 27 行,新容量在长度加上 \(\frac{1}{8}\) 的裕量,再加上 3 或 6 的裕量;

  2. 28-31 行,如果新容量超过允许范围,返回错误;

  3. 33-34 行,如果新长度为 0 ,将新容量也设置为 0 ,因此空列表底层数组亦为空;

  4. 36-40 行,调用 PyMem_Realloc 函数重新分配底层数组;

  5. 41-44 行,更新 3 个关键字段,依次设置为 新底层数组 、 新长度 以及 新容量 ;

注意到代码第 27 行,新容量的计算公式有点令人费解。 为什么还要加上 3 或者 6 的裕量呢? 试想一下,如果新长度小于 8 ,那么 \(\frac{1}{8}\) 的裕量便是 0 ! 这意味着,当 list 对象长度从 0 开始增长时,需要频繁扩容!

为了解决这个问题,必须在 \(\frac{1}{8}\) 裕量的基础上额外加上一定的固定裕量。 而 3 和 6 这两个特殊数值的选择,使得列表容量按照 04816253546587288……这样的序列进行扩张。 这样一来,当 list 对象长度较小时,容量翻倍扩展,扩容频率得到有效限制。

顺便提一下, PyMem_Realloc 函数是 Python 内部实现的内存管理函数之一,功能与 C 库函数 realloc 类似:

PyAPI_FUNC(void *) PyMem_Realloc(void *ptr, size_t new_size);

PyMem_Realloc 函数用于对动态内存进行扩容或者缩容,关键步骤如下:

1. 新申请一块尺寸为 new_size 的内存区域; 1. 将数据从旧内存区域 ptr 拷贝到新内存区域; 1. 释放旧内存区域 ptr ; 1. 返回新内存区域;

../../_images/91636ba4992bde5b54e5484cac374179.svg

内存管理 是最考验研发人员编程功底的领域之一,鼓励大家到 PyMem_Realloc 源码( ./Objects/obmalloc.c )中进一步研究内存管理的技巧。 学有余力的童鞋,可模仿着自己实现一个 realloc 函数,假以时日编程内功将突飞猛进!

尾部追加

append 方法在 Python 内部由 C 函数 list_append 实现,而 list_append 进一步调用 app1 函数完成元素追加:

static int
app1(PyListObject *self, PyObject *v)
{
    Py_ssize_t n = PyList_GET_SIZE(self);

    assert (v != NULL);
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) < 0)
        return -1;

    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    return 0;
}
  1. 4 行,调用 PyList_GET_SIZE 取出列表长度,即 ob_size 字段;

  2. 7-11 行,判断列表当前长度,如果已经达到最大限制,则报错;

  3. 13-15 行,调用 list_resize 更新列表长度,必要时 list_resize 对底层数组进行 扩容 ;

  4. 16 行,自增元素对象 引用计数 (元素对象新增一个来自列表对象的引用);

  5. 17 行,将元素对象指针保存到列表最后一个位置,列表新长度为 n+1 ,最后一个位置下标为 n

我们看到,有了 list_resize 这个辅助函数后, app1 函数的实现就非常直白了。 接下来,我们将看到 insertpop 等方法的实现中也用到这个函数,从中可体会到程序逻辑 划分 、 组合 的巧妙之处。 点击 “更多章节”,获取更多细节!

更多章节

洞悉 Python 虚拟机运行机制,探索高效程序设计之道!

到底如何才能提升我的 Python 开发水平,向更高一级的岗位迈进? 如果你有这些问题或者疑惑,请订阅我们的专栏,阅读更多章节:

https://cdn.fasionchan.com/python-source-course-qrcode.png

附录

订阅更新,获取更多学习资料,请关注我们的 微信公众号

微信搜索:小菜学编程

创作不易,如果觉得我们写得还行,就请我们喝杯咖啡吧😋

微信搜索:小菜学编程