从 Python 源码来分析列表的 resize 机制

Python 列表底层是通过存储对象指针的变长数组来实现的,使用数组带来的好处就是可以通过索引随机访问列表中的元素。

然而,由于 list 属于可变数据类型,我们可以动态地在 list 中增减元素,当底层数组不足以容纳新元素时,就要调整其大小了。这正是“变长”的含义所在。

那么,list 使用的变长数组是如何调整其大小呢?我们通过阅读 Python 源码来做下简单分析。


【列表初始内存分配机制】

先来了解一下,创建一个 list 时,list 底层数组是什么样子的。

list___init__() 是创建 list 对象的接口函数。它调用了 list___init___impl(self, iterable)。list___init___impl 接受一个 iterable 作为初始化源。这和我们通常初始化一个 list 对象的方式是一致的。

list___init___impl 做了哪些初始化工作呢?

list___init___impl() 首先将入参 self 指向的对象清空,原因是:Python 为提升创建 list 对象的效率,维护了一个 free_list 对象池。它可以回收不再使用的 list 对象,并重新分配给新 list 对象使用。

/* 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;

这个 list 内存池的大小为 80.

如果 self 指向的是一个缓存池中的对象,则需要先将它清理干净。

然后,list___init___impl() 调用 list_preallocate_exact() 为 self 的变长数组分配一块内存,这个数组中元素的个数和 iterable 中元素的个数相同。

这样,list 对象使用的变长数组就创建好了。


【列表 resize 的实现算法】

那么,变长数组是使用什么算法来调整其大小呢?

这个逻辑是在 list_resize() 函数中实现的。先看代码。

static intlist_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated, num_allocated_bytes;
    Py_ssize_t allocated = self->allocated;

    /*Step 1*/
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_SIZE(self, newsize);
        return 0;
    }

    /*Step 2*/
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    /* Do not overallocate if the new size is closer to overalocated 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;        

    /*Step 3*/
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    
    /*Step 4*/
    self->ob_item = items;
    Py_SET_SIZE(self, newsize);
    self->allocated = new_allocated;
    return 0;
}

list_resize() 的处理逻辑为:

  1. 先判断原 list 对象已分配的空间是否满足新需求:大于 newsize,且不超过 newsize 的两倍(超过 newsize 两倍时,需要缩短已分配空间)。满足,则无需再调整。
  2. 计算新数组的需要容纳的元素的数目:new_allocated。这个算法有点难理解:它会额外分配一些内存,并将这块内存以 4 的倍数进行对齐。可以不用去细究为什么要这样计算。
  3. 计算需要重新分配的内存大小:num_allocated_bytes。调用 PyMem_Realloc() 分配内存。
  4. 更新 self 指向对象的相关属性:调整变长数组指针的指向,设置 list 中元素的个数,设置已分配空间的大小。

【哪些操作会导致列表 resize?】

我们已经了解了 resize 的执行逻辑。那么 list 会在什么情况下 resize 底层数组呢?

  1. 数组内存不够用的时候

insert、append、extend、切片赋值,这些操作都有可能需要分配更多的内存。

2. 数组内存冗余的时候

pop、remove 可能需要缩减数组的空间,避免浪费。

看起来,凡是修改 list 元素数目的操作都有可能导致 resize 的发生。这些操作函数(定义在 listobject.c 中)确实也全部调用了 list_resize() 函数。

根据上边的 resize 算法,如果你的 list 中的元素数目抖动很大,发生 resize 的概率就大很多。

因此,我们在开发中应尽量避免频繁大幅度增减 list 元素的情况,以提升程序的运行效率。


欢迎转载,请注明出处。谢绝搬运,抄袭必究!

欢迎关注本站公众号【python学与思】

python 学与思