《python解释器源码剖析》第4章--python中的list对象

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

4.0 序

python中的list对象，底层对应的则是PyListObject。如果你熟悉C++，那么会很容易和C++中的list联系起来。但实际上，这个C++中的list大相径庭，反而和STL中的vector比较类似

4.1 PyListObject对象

我们知道python里面的list对象是支持对元素进行增删改查等操作的，list对象里面存储的，底层无一例外都是PyObject * 指针。所以实际上我们可以这样看待python底层的PyListObject：vector<PyObject *>。

根据我们使用python的list的经验，我们可以得出以下两个结论。

每个PyListObject维护的元素个数可以不一样：所以这是一个变长对象
可以对PyListObject维护的元素进行添加、删除等操作，所以这是一个可变对象

我们来看一下，PyListObject对象的定义。

typedef struct { //不用解释，PyObject加上一个ob_size PyObject_VAR_HEAD /* ob_item就对应list对象存储的元素，ob_item[0]就是list[0] 但是我们发现这是一个二级指针，至于这里的二级指针是如何和 python中list挂上钩的，我们后面会详细介绍 */ PyObject **ob_item; /* 这个allocated是什么呢?其实我在最开始的那一章介绍python源码的时候就已经解释过了。这里再来说一遍，我们知道PyObject_VAR_HEAD里面有一个ob_size，这是表示变长对象里面已经存储了多少个元素了。而这个allocated，则表示最大能存储多少个元素，因为这是一个变长对象，因此就意味着可以随时对其进行删除、增加等操作，如果每次添加都要malloc，那么效率会非常低下，因此python会事先申请一大份内存，而allocated正是记录了这个一大份内存的容量是多少。而ob_size则是目前已经存了多少个，如果你学过golang，你会发现ob_size对应 golang里面切片的len，而allocated则对应cap。假设一个能容纳10个元素的PyListObject对象已经存了5个元素，那么ob_size就是5，allocated就是10。从这里我们已经能够看出： 0 <= ob_size <= allocated len(list) == ob_size 注意这里的list指的都是list的实例对象，而不是list这个类本身 ob_item == NULL 意味着 ob_size == allocated == 0 */ Py_ssize_t allocated; } PyListObject;

刚才说了，python事先会申请一大份内存，这个并不是指在创建的时候申请一大份内存，而是在扩容的时候，会申请更多的内存。

PyListObject有一个resize操作，不用想，这个肯定是修改列表容量的。因为allocated一开始是固定的，但是随着ob_size越来越大，肯定要申请更多的内存，即增大allocated

static int list_resize(PyListObject *self, Py_ssize_t newsize) { //参数self就是PyListObject *对象本身 //参数newsize就是当前的ob_size PyObject **items; //既然resize，所以new_allocated就是新的最大容量 size_t new_allocated, num_allocated_bytes; //这里的获取当前PyListObject的allocated Py_ssize_t allocated = self->allocated;//如果当前的容量大于newsize(ob_size)，并且newsize >= 容量除以2 //基本上啥也没干直接返回，这一步不需要关心。 //因为执行这一步表示内存不需要重新分配 if (allocated >= newsize && newsize >= (allocated >> 1)) { assert(self->ob_item != NULL || newsize == 0); Py_SIZE(self) = newsize; return 0; } /* 计算重新分配的内存的大小这一步很重要，新分配的容量就等于newsize + newsize >> 3 + 3 if newsize < 9 else 6 */ 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; } //如果新的ob_size是0，那么新分配的容量也是0 if (newsize == 0) new_allocated = 0; //所占的字节，就是new_allocated * sizeof(PyObject *) //但是我们发现这里乘上的是一个指针的大小，这是一个很关键的问题，我们后面会详谈 num_allocated_bytes = new_allocated * sizeof(PyObject *); //为ob_item申请内存 items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes); if (items == NULL) { PyErr_NoMemory(); return -1; } //指向新的内存块，扩展列表。 self->ob_item = items; //将ob_size变为newsize Py_SIZE(self) = newsize; //将allocated变为新的new_allocated self->allocated = new_allocated; return 0; }

我们来刚才说，python中的list申请容量是按照new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)这样的规则来的，我们来看看。

allocated = 0 print(allocated, end=" ") for size in range(100): if allocated < size: allocated = size + (size >> 3) + (3 if size < 9 else 6) print(allocated, end=" ") # 0 4 8 16 25 35 46 58 72 88 106

我们具体来计算一下。

l = []allocated = 0 print(allocated, end=" ") for _ in range(100): l.append(_) if len(l) > allocated: # 从变量名也能看出，这获取的是容量，但是为什么要除以8呢？ # 因为[]里面的每一个元素占8个字节啊，咦，那列表里面存"xx" * 1000，这也占8个字节？ # 没错，是的，关于为什么我们会后面说。 # 同时这也引出了一个问题：为什么python中list对象在支持存储不同类型数据的前提下，还能保证查询的时间复杂度是O(1)呢？ # 先保留这些疑问，后面会解答 allocated = (l.__sizeof__() - [].__sizeof__()) // 8 print(allocated, end=" ") # 0 4 8 16 25 35 46 58 72 88 106

可以看到我们计算的结果和官方源码给的是一样的，其实这是废话，python解释器就是按照官方源码写的。但还有一个特殊情况：

l = [1, 2, 3, 4, 5] print((l.__sizeof__() - [].__sizeof__()) // 8) # 5 """ 结果是5，我们在之前的结果并没有看见5啊。这是因为对于初始化一个列表时，有多少元素，容量就是多少，此时allocated和ob_size是相等的 """ l.append(6) """ 什么时候会扩容呢？是当我们往列表进行append的时候，解释器发现容量不够。比如此时上面的ob_size和allocated都是5，但是当append一个6的时候，解释器发现容量不够了 ob_size已经超过allocated了，于是才会扩容。按照 newsize + (newsize >> 3) + (if newsize < 9 ? 3 : 6) """ # 此时扩容的结果就是9，尽管里面只存储的了6个元素，但是人家内存已经分配了 # 所以计算的就是9个元素的内存，那么除以8，得到的就是9，即分配的内存能够容纳9个元素 print((l.__sizeof__() - [].__sizeof__()) // 8) # 9

在这里还想问一句，对于初始化一个列表，你认为l = []和l = list()哪个速度更快呢？首先这两者你print之后得到的都是一个[]

答案是l = []更快，因为python中的list在C语言的层面可以看做是allocated-array：过分配数组，直接使用的是底层C语言的数据结构。而l = list()相当于是python层面上的一个函数调用，既然调用肯定要创建栈帧、记录函数参数等等，会进行额外的资源消耗。

为什么list通过索引查找元素的时间复杂度是O(1)

我们之前说了，其实不说大家也知道，python里面列表通过索引定位元素的时间复杂度是O(1)，可是列表里面存放的元素大小不一，是怎么做到的呢？还记的我们之前说，列表里面存储的元素都占8个字节吗？我们再来验证一下。

import sysl = ["a" * 1000, "b" * 1000] print(sys.getsizeof(l) - sys.getsizeof([])) # 16print(sys.getsizeof(l[0]) - sys.getsizeof("")) # 1000 """ 由于python中的对象除了值本身，还有其他的信息比如引用计数、ob_size等等，这些都是要占内存的。我们把这些值减掉，比如列表的话减去一个[]，字符串减去一个""，把共同具有的那些特征那么所占的内存去掉，那么剩下来的就是值本身占的内存 """

可以看到，加上本身的信息，l[0]占了不止1000个字节，同理l[1]也是，但是我们计算列表的时候，发现里面的值只占了16个字节，说明每一个值占了8个字节。其实任何一个对象存在列表里面都是8个字节，而我们看PyListObject的定义，里面有一个PyObject **ob_item，因此很容易猜到，python的list里面存储的实际上是指针。其实这个ob_item是一个指向指针数组的指针，这个指针指向了指针数组的首地址。因此我们可以看到，python的list、tuple，实际是哪个都是采用了元素外置的方法，元素的实际的值都存储在堆上，至于列表本身，存储的不过是这些元素的内存指针。不管你值本身占的内存有多大，但是内存地址是固定的，在64位机器上是8个字节。通过索引可以瞬间计算出指针的偏移量，从而找到对应元素的指针，打印的时候会自动打印指针所指向的内存。索引我们使用id(l[0])查看第一个元素的内存地址时，会打印一串数字，也就是内存地址，但是实际上l[0]在python的底层中，存储的就是地址。我们打印的时候，打印的也是指针，只不过我们没有权限操作指针，能有权限操作指针的只有解释器，因此当我们打印会自动打印指针的指向内存，我们可以认为尽管存储的是指针，但是最终操作的都是指针指向的内存。

4.2 PyListObject对象的创建与维护

4.2.1 创建对象

为了创建一个列表，python底层只提供了唯一的一条途径--PyList_New。这个函数接收一个size参数，从而允许我们在创建一个PyListObject对象时指定元素个数。这里仅仅是指定了元素个数，却没有指定元素是什么，我们来看看创建PyListObject对象的过程

PyObject * PyList_New(Py_ssize_t size) { //声明一个PyListObject *对象 PyListObject *op; #ifdef SHOW_ALLOC_COUNT static int initialized = 0; if (!initialized) { Py_AtExit(show_alloc); initialized = 1; } #endif //如果size小于0，直接抛异常 if (size < 0) { PyErr_BadInternalCall(); return NULL; } //缓冲池是否可用，如果可用 if (numfree) { //直接使用缓冲池的空间 numfree--; op = free_list[numfree]; _Py_NewReference((PyObject *)op); #ifdef SHOW_ALLOC_COUNT count_reuse++; #endif } else { //不可用的时候，申请内存 op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == NULL) return NULL; #ifdef SHOW_ALLOC_COUNT count_alloc++; #endif } //如果size小于0，ob_item设置为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(); } } //设置ob_size和allocated，然后返回op Py_SIZE(op) = size; op->allocated = size; _PyObject_GC_TRACK(op); return (PyObject *) op; }

通过源码我们可以看到，python在创建列表的时候，底层实际上是分为两部分的，一部分是创建PyListObject对象，另一部分是PyListObject对象所维护的列表，这是两块分离的内存，它们通过ob_item建立了联系。咦，有人会问，维护的列表不是PyListObject结构体的一个属性吗？是的，在这里PyListObject指的是不包含其维护列表的PyListObject，当然有时我们也用PyListObject专门只指其维护的列表、或者我们有时也说PyListObject所维护的列表等等，这些说法不用刻意区分，通过上下文是可以理解的。

我们注意到源码里面有一个缓冲池，是的，创建PyListObject对象时，会先检测缓冲池free_lists里面是否有可用的对象，有的话直接拿来用，否则通过malloc在系统堆上申请。缓冲池中最多维护80个PyListObject对象。

/* 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 void list_dealloc(PyListObject *op) { Py_ssize_t i; PyObject_GC_UnTrack(op); Py_TRASHCAN_SAFE_BEGIN(op) if (op->ob_item != NULL) { /* Do it backwards, for Christian Tismer. There's a simple test case where somehow this reduces thrashing when a *very* large list is created and immediately deleted. */ i = Py_SIZE(op); //释放list中的每一个元素 while (--i >= 0) { Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } //然后判断缓冲池里面PyListObject对象的个数，如果没满，就添加到缓冲池， if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) free_list[numfree++] = op; else Py_TYPE(op)->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) }

4.2.2 添加元素

在第一个PyListObject创建时，显然numfree是0，不会走缓冲池，而是直接在堆上申请，假设我们申请创建有6个元素的PyListObject对象，那么会调用PyList_New(6)来创建PyListObject对象，在对象完成之后，第一个PyListObject对象就完成了。

通过上图，我们可以抛出一个问题。

import pandas as pd# 具有6个元素的列表 l = [1, "xx", int, {}, pd, ()] print(l.__sizeof__()) # 88 print([].__sizeof__()) # 40 """ 两者相减得到48,6个元素，每个指针正好8字节。 """

我们看到元素外置、存储指针，6个元素总共用了48个字节，但是剩下的40个字节是哪来的。还记得吗？python中的对象在底层都是一个结构体实例，我们计算的可以不仅仅是维护的值，还有其他的信息啊。首先从图中可以看出，ob_refcnt:引用计数，占八个字节、ob_type：PyTypeObject对象的一个指针，八个字节、ob_size：容纳元素的个数，八个字节、ob_item：这是一个二级指针，指向了指针数组的指针，八个字节、allocated：容量，八个字节，正好40个字节，再加上ob_item指向的指针数组里面有6和元素，再加上6*8=48，正好88个字节。

然后我们看看PyListObject对象是如何设置元素的。

int PyList_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem) {//参数为：PyObject *、索引、值 //一个二级指针 PyObject **p; //类型检查 if (!PyList_Check(op)) { Py_XDECREF(newitem); PyErr_BadInternalCall(); return -1; } //索引检查 if (i < 0 || i >= Py_SIZE(op)) { Py_XDECREF(newitem); PyErr_SetString(PyExc_IndexError, "list assignment index out of range"); return -1; } //ob_item表示数组的首地址 //ob_item + i直接获取数组中索引为i的元素的指针 //当然数组里面存储的本身也是一个指针，所以这里的p是一个二级指针 p = ((PyListObject *)op) -> ob_item + i; //直接将*p，也就是数组中索引为i的指针(一级)指向的元素设置为newitem Py_XSETREF(*p, newitem); return 0; }

假设我们设置l[2]=100的话，那么

4.2.3 插入元素

设置元素和和插入元素是不同的，设置元素不会导致ob_item指向的内存发生改变，而插入元素可能会导致ob_item指向的内存发生变化

int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem) { //类型检查 if (!PyList_Check(op)) { PyErr_BadInternalCall(); return -1; } //底层又调用ins1 return ins1((PyListObject *)op, where, newitem); }static int ins1(PyListObject *self, Py_ssize_t where, PyObject *v) { /*参数self：PyListObject * 参数where：索引参数v：插入的值，这是一个PyObject *指针，因为list里面存的都是指针 */ //i:后面for循环遍历用的，n则是当前列表的元素个数 Py_ssize_t i, n = Py_SIZE(self); //指向指针数组的二级指针 PyObject **items; //如果v是NULL，错误的内部调用 if (v == NULL) { PyErr_BadInternalCall(); return -1; } //列表的元素个数不可能无限增大，一般当你还没创建到PY_SSIZE_T_MAX个对象时 //你内存就已经玩完了，但是python仍然做了检测当达到这个PY_SSIZE_T_MAX时，会报出内存溢出错误 if (n == PY_SSIZE_T_MAX) { PyErr_SetString(PyExc_OverflowError, "cannot add more objects to list"); return -1; } //调整列表容量，既然要inert，那么就势必要多出一个元素 //这个元素还没有设置进去，但是先把这个坑给留出来 //当然如果容量够的话，是不会扩容的，只有当容量不够的时候才会扩容 if (list_resize(self, n+1) < 0) return -1; //确定插入点 //这里可以看到如果where小于0，那么我们就加上n，也就是当前列表的元素个数 //比如有6个元素，那么我们where=-1，加上6，就是5，显然就是insert在最后一个索引的位置上 if (where < 0) { where += n; //如果吃撑了，写个-100，加上元素的个数还是小于0 if (where < 0) //那么where=0，就在开头插入 where = 0; } //如果where > n，那么就索引为n的位置插入， //可元素个数为n，最大索引是n-1啊，对，所以此时就相当于append if (where > n) where = n; //拿到原来的二级指针，指向一个指针数组 items = self->ob_item; //然后让不断遍历，把索引为i的值赋值给索引为i+1，既然是在where处插入 //那么where之前的就不需要动了，到where处就停止了 for (i = n; --i >= where; ) items[i+1] = items[i]; //增加引用计数，因为它作为列表的一个元素了 Py_INCREF(v); //将where处的值设置成v，还记得这个v吗？对，没错，这是一个PyObject *指针 //打印的话，会打印*v items[where] = v; return 0; }

所以可以看到，python插入数据是非常灵活的。不管你在什么位置插入，都是合法的。因为它会自己调整位置，在确定位置之后，会将当前位置以及之后的所有元素向后挪动一个位置，空出来的地方设置为插入的值。因此熟悉C++的话，会发现这和vector是非常类似的，但是和C++中的list确实大相径庭的，尽管名字一样。

既然插入元素，那么自然少不了append直接往尾部追加元素了。这个就比较简单了，就相当于insert的where>n，直接将索引为n的地方设置为append的值即可。这里就不看源码了，比较简单。只是如果容量够的话，是不需要重新分配空间的。

4.2.4 删除元素

删除元素，对于python的列表来说，直接调用l.remove即可

l = [1, 1, 2, 3] l.remove(1) print(l) # [1, 2, 3] # 会自动删除第一个出现的元素

那么底层是如何实现的呢？

static PyObject * list_remove(PyListObject *self, PyObject *value) { //删除值，对于底层来说，就是删除数组中值对应的指针。 //所以value仍然是PyObject *类型 //i，for循环遍历用的 Py_ssize_t i; //从0开始，直到不小于ob_size for (i = 0; i < Py_SIZE(self); i++) { //将指针数组里面的每一个元素和value进行比较 int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ); //如果cmp大于0，表示元素和value匹配 if (cmp > 0) { //调用list_ass_slice将其删除 if (list_ass_slice(self, i, i+1, (PyObject *)NULL) == 0) Py_RETURN_NONE; return NULL; } else if (cmp < 0) return NULL; } //否则报错，x不再list中。 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list"); return NULL; }//另外这个list_ass_slice其实起到的是替换的作用，只不过也可以充当删除 //从源码中可以看出把i: i+1部分的元素给删了 /* l = [1, 2, 3, 4] l[0: 1] = [] print(l) # [2, 3, 4] */

既然是删除，那么和insert一样。全局都会进行移动，比如我把第一个元素删了，那么第二个元素要顶在第一个元素的位置，第n个元素要顶在第n-1个元素的位置上。

4.3 PyListObject对象缓冲池

还记的我们之前说的缓冲池free_lists吗？是用来缓冲PyListObject对象的，但是现在问题来了，这些缓冲的PyListObject对象从哪里获取的呢？或者说是何时创建的呢？答案其实一开始就说了，是在一个PyListObject对象销毁的时候创建的。

static void list_dealloc(PyListObject *op) { //遍历用的 Py_ssize_t i; PyObject_GC_UnTrack(op); Py_TRASHCAN_SAFE_BEGIN(op) //改变每一个元素的引用计数 //销毁PyListObject对象维护的元素列表 if (op->ob_item != NULL) { /* Do it backwards, for Christian Tismer. There's a simple test case where somehow this reduces thrashing when a *very* large list is created and immediately deleted. */ i = Py_SIZE(op); while (--i >= 0) { Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } //如果缓冲池未满，那么放回到缓冲池当中 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) free_list[numfree++] = op; else Py_TYPE(op)->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) }

我们知道在创建一个新的PyListObject对象时，实际上是分为两步的，先创建PyListObject，然后创建其维护的元素列表。同理，在销毁一个PyListObject对象时，先销毁销毁维护的元素列表，然后再释放PyListObject对象自身

现在可以很清晰地明白了，原本空荡荡的缓冲池其实是被已经死去的PyListObject对象填充了，在以后创建新的PyListObject对象时，python会首先唤醒这些死去的PyListObject对象，给它们一个洗心革面、重新做人的机会。但注意的是，这里的缓冲仅仅是PyListObject对象，对于其维护的列表，已经不再指向了，引用减少，那么这些元素就大难临头各自飞了，或生存、或毁灭，不再被对应的PyListObject的那个指针所束缚。但是为什么要这么做呢？可以想一下，如果继续维护的，那么很可能会产生悬空指针的问题，因此这些元素所占的空间必须交还给系统(前提是没有指针指向了)

但是实际上，是可以将PyListObject对象维护的元素列表保留的，即只调整引用计数，并将元素都设置为NULL，但是并不释放内存空间。因此这样一来，释放的内存不会交给系统堆，那么再次分配的时候，速度会快很多。但是这样带一个问题就是，这些内存没人用也会一直占着，并且只能供PyListObject对象使用，因此python还是为避免消耗过多内存，采取将元素列表的内存交换给了系统堆这样的做法，在时间和空间上选择了空间。

我们之前的PyListObject对象的示意图，如果在缓冲池当中应该变成什么样子呢？