Python 源码阅读：list
来源：Python开发者
ID：PythonCoder
源码位置 Include/listobject.h | Objects/listobject.c
定义
typedef struct { PyObject_VAR_HEAD PyObject **ob_item; Py_ssize_t allocated; } PyListObject;
说明
1. PyObject_VAR_HEAD PyListObject是变长对象 2. PyObject **ob_item; 指向列表元素的指针数组, list[0] 即 ob_item[0] 3. Py_ssize_t allocated; allocated列表分配的空间, ob_size为已使用的空间 allocated 总的申请到的内存数量 ob_size 实际使用内存数量 等式: 0
结构
构造
只有一个方法
定义如下
PyObject * PyList_New(Py_ssize_t size) { PyListObject *op; size_t nbytes; #ifdef SHOW_ALLOC_COUNT static int initialized = 0; if (!initialized) { Py_AtExit(show_alloc); initialized = 1; } #endif // 大小为负数, return if (size 0) { PyErr_BadInternalCall(); return NULL; } // 如果大小超过, 报错 /* 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(); // 计算需要的字节数(PyObject指针数组) nbytes = size * sizeof(PyObject *); // 如果缓冲池非空, 从缓冲池取 if (numfree) { // 取缓冲池数组最后一个对象 numfree--; op = free_list[numfree]; // set refcnt=1 _Py_NewReference((PyObject *)op); #ifdef SHOW_ALLOC_COUNT count_reuse++; #endif } else { // 否则, GC_New分配内存空间 op = PyObject_GC_New(PyListObject, &PyList_Type); // 分配失败 if (op == NULL) return NULL; #ifdef SHOW_ALLOC_COUNT count_alloc++; #endif } // 确定ob_item列表元素指针的值 // 若大小 if (size 0) op->ob_item = NULL; else { // 分配内存 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); if (op->ob_item == NULL) { Py_DECREF(op); return PyErr_NoMemory(); } // 初始化, 填充 memset(op->ob_item, 0, nbytes); } // ob_size = size Py_SIZE(op) = size; // allocated op->allocated = size; // gc用 _PyObject_GC_TRACK(op); return (PyObject *) op; }
简化步骤
1. 判断列表缓冲池是否为空, 是的话从缓冲池取(复用) 2. 否则, 从内存中分配空间 3. 然后初始化数据
结论
Py_SIZE(op) = size; op->allocated = size; 第一次生成list, 其allocated = ob_size
list_resize
同时注意list_resize方法
extends方法, list_resize(self, m + n) pop方法, list_resize(self, Py_SIZE(self) - 1) append方法, list_resize(self, n+1)
其定义
list_resize(PyListObject *self, Py_ssize_t newsize) { ........... // 如果 allocated/2 <= newsize <= allocated // 直接修改ob_size if (allocated >= newsize && newsize >= (allocated >> 1)) { assert(self->ob_item != NULL || newsize == 0); Py_SIZE(self) = newsize; return 0; } //否则 new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); new_allocated += newsize; ............. Py_SIZE(self) = newsize; self->allocated = new_allocated; }
即
if allocated/2 <= newsize <= allocated allocated 不变 ob_size = newsize else allocated = newsize + ((newsize >> 3) + (newsize < 9 ? 3 : 6)) ob_size = newsize
回收和PyListObject对象缓冲池
看下缓冲池相关的定义
/* Empty list reuse scheme to save calls to malloc and free */ #ifndef PyList_MAXFREELIST #define PyList_MAXFREELIST 80 #endif // 80个 static PyListObject *free_list[PyList_MAXFREELIST]; static int numfree = 0;
我们先看下list_dealloc的定义
static void list_dealloc(PyListObject *op) { Py_ssize_t i; PyObject_GC_UnTrack(op); Py_TRASHCAN_SAFE_BEGIN(op) // 遍历ob_item, 释放所有类表内元素空间 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); } // 如果free_list还没满, PyListObject加入到列表中 if (numfree tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) }
即
对一个列表对象PyListObject, 回收时, ob_item会被回收, 其每个元素指向的对象引用-1. 但是PyListObject对象本身, 如果缓冲池未满, 会被放入缓冲池, 复用
缓冲池结构
List的操作过程
插入
1. resize n+1 2. 确定插入点 3. 插入点后所有元素后移 4. 执行插入
示例
>>> a = [1, 2, 3] >>> a.insert(0, 9) >>> a [9, 1, 2, 3]
append
1. resize n+1 2. 放入最后一个位置(ob_size)
示例
>>> a = [1, 2, 3] >>> a.append(4) >>> a [1, 2, 3, 4]
extend
1. 计算两个list大小 m n 2. resize m+n(此时本身被复制) 3. 遍历长度为n的数组, 从ob_item+m的位置开始加入
示例
>>> m = [1, 2, 3] >>> n = [4, 5] >>> m.extend(n) >>> m [1, 2, 3, 4, 5]
删除
1. 找到要删除元素位置 2. 删除之, 后面元素前移
示例
>>> a = [1, 2, 3, 2] >>> a.remove(2) >>> a [1, 3, 2]
来源：伯乐在线 - wklken
*声明：推送内容及图片来源于网络，部分内容会有所改动，版权归原作者所有，如来源信息有误或侵犯权益，请联系我们删除或授权事宜。
- END -