Python源码阅读-内建对象(4)

(Updated: )
,

这是《Python源码剖析 — 深度探索动态语言核心技术》的阅读记录.

Python中的列表对象 - PyListObject.

对象概述

Python中的列表对象是可以结束各种类型的对象的, 例如:

1
2
3
4
5
6
>>> l = []
>>> l.append(1)
>>> l.append("P")
>>> l.append([])
>>> l
[1, 'P', []]

这也就是说, 在Python的列表对象中, 存放的都是PyObject*类型的指针. 而这样的一个List显然是一个可变长对象, 并且还支持元素的操作: set, insert, delete等等. 对于这样的一个变长对象来说, 内存空间的维护就变得尤为重要了.

还是先从对象的定义开始看吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

如我们所料, 是一个PyObject_VAR_HEAD可变对象头. 后面的指针就是指向列表中的元素的指针了.(因为Python设计列表对象和具体的元素是分离的, 他们之间就通过这个**ob_item来连接) 最后面的那个属性就很重要了, 通过注释我们就可以大概猜出来这个的作用. 如果说一个列表有10个元素, 那么这10个元素的大小应该就可以从这个PyObject_VAR_HEAD中的ob_size中得到, 为啥会需要一个叫做allocated的值来标明分配的内存大小呢?

稍微想想就可以搞懂了, 如果说我们采取插入一个元素就申请一个内存, 那效率也太低了. 因此, 我们总是会申请一大块内存, 将这个大块内存的容量记录在allocated这个值, 而ob_size记录的则是使用的内存大小.

这就是最基本的PyListObject内存管理策略.

创建列表对象, 维护和列表操作

创建对象

那么就具体看下是怎么进行内存申请的吧:

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
PyObject *
PyList_New(Py_ssize_t size)
{
	PyListObject *op;
	size_t nbytes;

	if (size < 0) {
		PyErr_BadInternalCall();
		return NULL;
	}
	nbytes = size * sizeof(PyObject *);
	/* Check for overflow without an actual overflow,
	 *  which can cause compiler to optimise out */
	if (size > PY_SIZE_MAX / sizeof(PyObject *))
		return PyErr_NoMemory();
	if (num_free_lists) {
		num_free_lists--;
		op = free_lists[num_free_lists];
		_Py_NewReference((PyObject *)op);
	} else {
		op = PyObject_GC_New(PyListObject, &PyList_Type);
		if (op == NULL)
			return NULL;
	}
	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);
	}
	op->ob_size = size;
	op->allocated = size;
	_PyObject_GC_TRACK(op);
	return (PyObject *) op;
}

这就是唯一的一个创建函数. 他需要接受一个长度. 接着就是检查参数传递的正确性, 是否出现溢出, 接着就要开始申请内存了. 中间的那些free_list我们先忽略掉, 直接看后面的内存申请. 我们申请nbytes大小的内存, 这个大小就是size * sizeof(PyObject *). 接着使用0去填充我们的ob_item指向的内存区域, 并且为了日后的维护, 我们把这个新列表的大小和分配的内存大小赋值, 第一次创建的列表的ob_size和allocated的大小是一样的. 后面的GC宏我们先忽略.

设置元素

得到了一个新的列表对象,接着就要向里面添加元素了. 调用的底层函数就是这个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 >= ((PyListObject *)op) -> ob_size) {
		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;
}

当我们进行l[1] = "a"这样的操作的时候, 就是在调用这个函数了, 首先还是会进行一下类型检查, 如果不是列表对象就会报错, 接着检查索引, 如果是超出列表范围就抛出IndexError异常. 这些都检查没问题了, 就可以开始进行赋值了, 首先, 我们把要被替换的那个位置的元素指针拿到, 接着先丢给另一个olditem代为存储, 然后就可以进行覆盖操作了. 接着把踢出来的那个元素的引用计数减一, 注意这里使用的是XDECREF. 这是因为有可能在空列表中插入元素的时候原来的元素就是NULL.

XDECREF和DECREF的区别就是X版本会检查一下元素是否为NULL, 如果是就不做任何操作. 感觉就有点像是Redis中的NX和XX.

插入元素

可能你会觉得, 插入不就是设置元素嘛, 那就肯定可以重用接口了吧? 可惜并不能, 插入和设置的一个本质区别就是在插入的时候会导致ob_item的指向发生变化. 在底层实现, 插入使用的是这个函数:

1
2
3
4
5
6
7
8
9
int
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{
	if (!PyList_Check(op)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return ins1((PyListObject *)op, where, newitem);
}

其实调用的是一个叫做ins1的函数, 来看下:

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
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
	Py_ssize_t i, n = self->ob_size;
	PyObject **items;
	if (v == NULL) {
		PyErr_BadInternalCall();
		return -1;
	}
	if (n == PY_SSIZE_T_MAX) {
		PyErr_SetString(PyExc_OverflowError,
			"cannot add more objects to list");
		return -1;
	}

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

	if (where < 0) {
		where += n;
		if (where < 0)
			where = 0;
	}
	if (where > n)
		where = n;
	items = self->ob_item;
	for (i = n; --i >= where; )
		items[i+1] = items[i];
	Py_INCREF(v);
	items[where] = v;
	return 0;
}

这里传入的op已经可以确定是一个列表对象了. 首先还是进行的类型审查和溢出检查, 接着就是一个关键的步骤了, 那就是进行大小的重新变化:list_resize. 这里就是在确保列表对象有足够的内存来容纳插入的元素了. 那么我们就来具体的看下是如何进行resize的.

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
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
	PyObject **items;
	size_t new_allocated;
	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);
		self->ob_size = 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, ...
	 */
	new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

	/* check for integer overflow */
	if (new_allocated > PY_SIZE_MAX - newsize) {
		PyErr_NoMemory();
		return -1;
	} else {
		new_allocated += newsize;
	}

	if (newsize == 0)
		new_allocated = 0;
	items = self->ob_item;
	if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))
		PyMem_RESIZE(items, PyObject *, new_allocated);
	else
		items = NULL;
	if (items == NULL) {
		PyErr_NoMemory();
		return -1;
	}
	self->ob_item = items;
	self->ob_size = newsize;
	self->allocated = new_allocated;
	return 0;
}

可以看到, 如果当前已经分配的内存大小要比新分配的大, 并且新分配的大小是比原来的1/2还要大的 那么就不需要再分配了, 反而, 还要通过调整ob_size的值, 缩小范围. 后面就是在计算新分配的内存大小了, 新分配的大小是新大小/8再加上3或许6. 接着我们先把当前列表的元素都搬出来, 然后进行新空间的搬运, 最后把属性重新维护, 这样resize的过程就结束了.

接着回到我们的ins1, 此时使用的就是负数索引了, 接着就是把边界约束了一下. 这样就确保任何输入都是合法的.

除了规定index的insert, 还有一个直接插入到最后的append, 来看看吧:

1
2
3
4
5
6
7
static PyObject *
listappend(PyListObject *self, PyObject *v)
{
	if (app1(self, v) == 0)
		Py_RETURN_NONE;
	return NULL;
}

和Insert真是类似啊, 我们来看看这个app1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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) == -1)
		return -1;

	Py_INCREF(v);
	PyList_SET_ITEM(self, n, v);
	return 0;
}

同样的, 还是先继续rsize, 之后就简单了, 我们直接调用设置元素的API就可以了. 这个就比insert要简单的多.

删除元素

PyListObject删除元素的方法在这里:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static PyObject *
listremove(PyListObject *self, PyObject *v)
{
	Py_ssize_t i;

	for (i = 0; i < self->ob_size; i++) {
		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
		if (cmp > 0) {
			if (list_ass_slice(self, i, i+1,
					   (PyObject *)NULL) == 0)
				Py_RETURN_NONE;
			return NULL;
		}
		else if (cmp < 0)
			return NULL;
	}
	PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
	return NULL;
}

其实流程很简单, 就是遍历整个列表然后和你要删除的元素进行挨个的比较, 如果一样就调用另外一个函数来真正删除元素, 如果说比较了所有的元素还是没有找到待删除的元素, 就会跑完循环然后抛出ValueError异常.

那么我们关注的重点显然就是那个删除元素的函数了, 实际上, 从注释我们可以知道, 这个函数是一个多用途的函数, 它不仅可以用来删除元素, 还可以进行列表元素的替换. 根据传递的参数是否为NULL来判定执行什么样的操作: (我们可以理解成是删除元素就是把某个位置的元素替换成空罢了)

1
2
3
4
5
6
a[ilow:ihigh] = v if v != NULL.
del a[ilow:ihigh] if v == NULL.

函数的签名是这样的: 
static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

我们主要来看删除元素的操作步骤.

1
2
if (v == NULL)
		n = 0;

首先如果我们传入的v参数是NULL的话, 就是执行删除操作, 这样就把替换列表元素的数量设置成0. 

1
2
3
4
5
6
7
8
9
10
11
12
if (ilow < 0)
    ilow = 0;
else if (ilow > a->ob_size)
    ilow = a->ob_size;

if (ihigh < ilow)
    ihigh = ilow;
else if (ihigh > a->ob_size)
    ihigh = a->ob_size;

norig = ihigh - ilow;
assert(norig >= 0);

接着进行一波索引正确性和边界判断. 这里的norig就是即将发生变化的, 可以使即将被替换的, 也可以是即将被删除的. 

1
2
3
4
5
6
7
8
9
10
11
d = n - norig;
item = a->ob_item;
s = norig * sizeof(PyObject *);
if (s > sizeof(recycle_on_stack)) {
    recycle = (PyObject **)PyMem_MALLOC(s);
    if (recycle == NULL) {
        PyErr_NoMemory();
        goto Error;
    }
}
memcpy(recycle, &item[ilow], s);

接着我们把列表中的元素都提出来, 之后在开辟的回收空间(8个PyObject的大小)上把待删除的元素先复制到上面去.

1
2
3
4
5
6
if (d < 0) { /* Delete -d items */
    memmove(&item[ihigh+d], &item[ihigh],
            (a->ob_size - ihigh)*sizeof(PyObject *));
    list_resize(a, a->ob_size + d);
    item = a->ob_item;
}

之后就是删除了, 始终记得删除的时候满足ihigh-ilow = 1.(看之前的调用参数).所以这就相当于是把后面的向前覆盖移动, 然后重新规划大小. 最后再把其余的元素重新赋值成NULL并且统一处理引用计数.

缓冲池

最后还是来说说List对象的对象缓冲池吧.

在之前我们是见到过的, 就是那个叫做free_lists的玩意:

1
2
3
#define MAXFREELISTS 80
static PyListObject *free_lists[MAXFREELISTS];
static int num_free_lists = 0;

我们在之前的创建对象那个地方忽略掉的, 就是这个缓冲池:

1
2
3
4
5
6
7
8
9
if (num_free_lists) {
    num_free_lists--;
    op = free_lists[num_free_lists];
    _Py_NewReference((PyObject *)op);
} else {
    op = PyObject_GC_New(PyListObject, &PyList_Type);
    if (op == NULL)
        return NULL;
}

只有在没有命中的时候才会进行创建. 当你在代码中寻找这个变量是如何被增加的时候, 你会定位到析构函数的上面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 = op->ob_size;
		while (--i >= 0) {
			Py_XDECREF(op->ob_item[i]);
		}
		PyMem_FREE(op->ob_item);
	}
	if (num_free_lists < MAXFREELISTS && PyList_CheckExact(op))
		free_lists[num_free_lists++] = op;
	else
		op->ob_type->tp_free((PyObject *)op);
	Py_TRASHCAN_SAFE_END(op)
}

呵. 列表对象被毁灭的时候不是直接被杀掉, 而是被放在了这个缓冲池中, 当以后再次需要它的时候, 才会让他重生. 而不需要重新创造.

但是你也可以看到, 我们仅仅留下了op, 也就是PyListObject, 至于他所包含的所有元素, 都释放掉了引用计数.

行吧, 接下来我们就来实际观察下Python对列表对象的内存管理吧.

结论测试

我们再源码中进行修改, 使得打印列表函数可以输出一些信息, 接着就开始测试, 我们这一次使用脚本来测试缓冲池(这是为了防止交互式环境对缓冲池数量的影响).

1
2
3
4
5
6
7
8
9
10
list1 = [1]
print list1
list2 = [1]
print list1
list3 = [1]
print list1
del list3
print list1
del list2
print list1

输出的结果是这样的:

1
2
3
4
5
6
7
8
root@Ubuntu:/tmp/bin# ./python2.5 list_test
Could not find platform dependent libraries <exec_prefix>
Consider setting $PYTHONHOME to <prefix>[:<exec_prefix>]
[]Allocated: 1, ob_size: 1; num_free_lists: 3
[]Allocated: 1, ob_size: 1; num_free_lists: 2
[]Allocated: 1, ob_size: 1; num_free_lists: 1
[]Allocated: 1, ob_size: 1; num_free_lists: 2
[]Allocated: 1, ob_size: 1; num_free_lists: 3

请忽略其他奇怪的输出…能看到效果就好了.

随着元素的删除, 缓冲池的数量在增加. 并且在创建的时候 会直接从池子中取.

最后再看下那个resize的效果吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> l = [1]
>>> l
[]Allocated: 1, ob_size: 1; num_free_lists: 4
>>> l.append(2)
>>> l
[, ]Allocated: 5, ob_size: 2; num_free_lists: 5
>>> l.append(3)
>>> l
[, , ]Allocated: 5, ob_size: 3; num_free_lists: 5
>>> l.append(4)
>>> l.append(5)
>>> l.append(6)
>>> l
[, , , , , ]Allocated: 9, ob_size: 6; num_free_lists: 5