CPython源码分析0002

发表于 | 分类于 | 阅读次数:
字数统计: 1.3k | 阅读时长 ≈ 5

python 内置了dict list等

Python中的的PyListObject是对列表的一个抽象，内置了插入、添加、删除等操作。不同List中存储的元素的个数会是不同的，所以PyListObject是一个变长对象。而PyListObject中支持插入删除等操作，可以在运行时动态地调整其所维护的内存和元素，所以它又是一个可变对象。

我们知道，用户选用list正是为了可以频繁的执行插入或删除等操作，如果是需要存多少就申请多大的内存，这种内存管理显然是低效的。那么Python内部是怎么实现的呢？这就与刚才所提到的allocated有关了，我们知道，在PyObject_VAE_HEAD中有一个ob_size，在PyListObject中，每一次需要申请内存时，总会申请一大块内存存，这时申请的总内存的大小记录记录在allocated中，而其中实际被使用了的内存的数量则记录在ob_size中。

在列表对象的实现文件listObject.c文件中，我们可以看到，Python对于创建一个列表，提供了唯一的一条途径，就是PyList_New（）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


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

if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
//进行溢出检查
if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
return PyErr_NoMemory();
nbytes = size * sizeof(PyObject *);
//为PyListObject对象申请空间，使用到缓冲池技术
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
}
//为PyListObject对象中维护的元素列表申请空间
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);
}
Py_SIZE(op) = size;
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}

首先，进行溢出检查。接下来，就是List对象的创建了，Python中的list对象实际上是分为两部分的，一是PyListObject对象本身，二是PyListObject对象维护的元素列表，而这两块内存是通过ob_item建立联系的。

　　在创建PyListObject对象时，首先检查缓冲池中free_list是否有可用的对象，如果有，则直接使用，若没有可用对象，则通过PyObject_GC_New在系统堆中申请内存， 　　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int
PyList_SetItem(register PyObject *op, register Py_ssize_t i,
register PyObject *newitem)
{
register PyObject *olditem;
register 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;
}
//存放元素
p = ((PyListObject *)op) -> ob_item + i;
olditem = *p;
*p = newitem;
Py_XDECREF(olditem);
return 0;
}

在创建PyListObject对象时，会首先检查缓冲区中的free_lists中是否有可用的对象。
　　在创建一个新的的对象时，实际也是分为两部，首先创建PyListObject对象，然后创建PyListObject对象所维护的元素列表，与之对应，在销毁一个list时，销毁的过程也是分离的，首先销毁PyListObject所维护的元素列表，然后释放PyListObject对象自身。。
　　在删除PylsitObject对象自身时，Python会先检查我们开始提到的那个缓冲池free_list，查看其中缓存的PyListObject的数量是否已经满了，如果没有，就将待删除的PyListObject对象放到缓冲池中，以备后用。
　　因此，那个在Python启动时空荡荡的缓冲池原来都是被本应该死去的PyListObject对象给填充了，在以后需要创建新的PyListObject的时候，Python会首先唤醒这些对象，重新分配Pyobject*元素列表占用的内存，重新拥抱新的对象。
　　
　　
insert 追加元素性能极差 谨慎使用
append 常数级别
pop 从头部弹出也需要挪动整个列表
pop 从尾部弹出元素 常数级别

list 对象可以根据元素个数进行自动扩容

内部结构在头文件 include/listobject.h 当中

变长对象 包含变长对象公共头部 内部维护了一个动态数组

尾部增删可以快速完成 无需挪动其他元素

如果list对象内部数组已经用满 再添加元素的时候 需要进行扩容

由于内部数组扩容时，需要将列表元素从旧数组拷贝到新数组，时间复杂度为 O(N)，开销较大，需要尽量避免。为此， Python 在为内部数组扩容时，会预留一定裕量，一般是

1/8 左右。假设为长度为 1000 的列表对象扩容， Python 会预留大约 125 个空闲位置，分配一个长度 1125 的新数组。 也就是基数上增加0.125

由于扩容操作的存在， append 方法最坏情况下时间复杂度为

O(n) 。由于扩容操作不会频繁发生，将扩容操作时的元素拷贝开销平摊到多个 append 操作中，平均时间复杂度还是 O(1) 。

拷贝

浅拷贝 只是对列表对象进行浅拷贝 对信列表可变元素的修改对旧列表依然可见

拷贝的是元素对象的指针