Python两个有趣的细节

书到用时方很少。

给客户培训Python,被两个问题问住了。虽然略感窘迫,但也因此督促我去更深入的了解Python。且容我一一道来。

Python的小整数缓存问题

CPython是Python的官方解释器,它会对小整数进行缓存,默认的范围是-5到257,也就是说,在这个范围内的数字,CPython会直接使用缓存的引用地址,也就是说,所有在这个范围内的小整数,都是指向同一个地址。

1
2
3
4
5
6
7
8
9
10
11
a = 1
b = 1
print(id(a)) # 140382087155128
print(id(b)) # 140382087155128
c = 257
d = 257
print(id(c)) # 140382085685584
print(id(d)) # 140382085685488

可以看到,上面ab因为使用了小整数,他们的地址是一样的,而超过了这个范围的其他整数,分配的地址是不一样的。

为了验证这个说法,我们来查看一下源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Python-2.7.9/Objects/intobject.c:67 */
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS 257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS 5
#endif
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
/* References to small integers are saved in this array so that they
can be shared.
The integers that are saved are those in the range
-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

上面这段代码就是定义缓存的小整数范围的部分,我们再来看下这个数组是如何初始化的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* Python-2.7.9/Objects/intobject.c:1457 */
int
_PyInt_Init(void)
{
PyIntObject *v;
int ival;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
if (!free_list && (free_list = fill_free_list()) == NULL)
return 0;
/* PyObject_New is inlined */
v = free_list;
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
small_ints[ival + NSMALLNEGINTS] = v;
}
#endif
return 1;
}

上面这段代码大概的意思是说,从free_list里取个值,设置成一个小整数对象并赋值,然后把这个对象的地址存在对应的small_ints数组中。这里的free_list又是个什么东东呢?

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
/* Python-2.7.9/Objects/intobject.c:16 */
/* Integers are quite normal objects, to make object handling uniform.
(Using odd pointers to represent integers would save much space
but require extra checks for this special case throughout the code.)
Since a typical Python program spends much of its time allocating
and deallocating integers, these operations should be very fast.
Therefore we use a dedicated allocation scheme with a much lower
overhead (in space and time) than straight malloc(): a simple
dedicated free list, filled when necessary with memory from malloc().
block_list is a singly-linked list of all PyIntBlocks ever allocated,
linked via their next members. PyIntBlocks are never returned to the
system before shutdown (PyInt_Fini).
free_list is a singly-linked list of available PyIntObjects, linked
via abuse of their ob_type members.
*/
#define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */
#define BHEAD_SIZE 8 /* Enough for a 64-bit pointer */
#define N_INTOBJECTS ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
struct _intblock {
struct _intblock *next;
PyIntObject objects[N_INTOBJECTS];
};
typedef struct _intblock PyIntBlock;
static PyIntBlock *block_list = NULL;
static PyIntObject *free_list = NULL;
static PyIntObject *
fill_free_list(void)
{
PyIntObject *p, *q;
/* Python's object allocator isn't appropriate for large blocks. */
p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
if (p == NULL)
return (PyIntObject *) PyErr_NoMemory();
((PyIntBlock *)p)->next = block_list;
block_list = (PyIntBlock *)p;
/* Link the int objects together, from rear to front, then return
the address of the last int object in the block. */
p = &((PyIntBlock *)p)->objects[0];
q = p + N_INTOBJECTS;
while (--q > p)
Py_TYPE(q) = (struct _typeobject *)(q-1);
Py_TYPE(q) = NULL;
return p + N_INTOBJECTS - 1;
}

在Python中,即使是int,也是个对象,CPython的实现中,这个整数对象也是存在堆中,通过malloc来分配,那么每次申请整数变量,都将消耗资源来分配内存。所以CPython采用PyIntBlocks来预先分配一部分内存,需要的时候直接从这里面取,注意一下,这里么个PyIntBlocks的长度是通过两个宏来计算出来的,每个PyIntObject占用12个字节,所以每个PyIntBlocks的长度为82。即,CPython会每次预先分配82个整数的位置,如果用完了,再分配82个。所有的PyIntBlocks存在block_list这个链表中。

free_list这个链表记录了已经分配了内存但还没有被使用的整数对象,每次需要一个整数时,从free_list中取,如果free_list是空,说明已经没有可用的整数对象,就会调用fill_free_list函数再重新分配一个PyIntBlocks并加到block_list中。

总结一下,CPython对于整数类型的缓存,通过两层缓存机制来提高效率,首先通过预先分配大块内存,减少整数分配时堆栈操作;其次是通过对-5到256这部分小整数进行缓存,进一步提高小整数的访问效率。为什么还要缓存负数呢?别忘了,Python里是可以通过-1来索引的。

好了,终于搞清楚这个小整数缓存机制的原理了。

最后,利用这个缓存机制,讲一个Hack技巧,大家可以玩一下。因为每一个小整数,都指向同一个地址,那么,如果我们把这个地址指向的内存值改掉,就可以改变所有引用这个值的位置。

1
2
3
4
5
6
7
import ctypes
value = 2
ob_ival_offset = ctypes.sizeof(ctypes.c_size_t) + ctypes.sizeof(ctypes.c_voidp)
ob_ival = ctypes.c_int.from_address(id(value) + ob_ival_offset)
ob_ival.value = 3
print(1 + 1) # 3

请听题,1 + 1什么时候等于3?

tee的原理

典型的Pythonic代码,几乎一定会用到迭代器,而itertools就是Pythoner利用迭代器的最佳工具箱。这个工具箱里有一个名为tee的的工具,其命名应该是来源于Linux的命令行工具tee,其作用就是将一个迭代器分成多个,如果需要对一个序列多次迭代,就要用到它了。比如:

1
2
3
4
5
6
7
from itertools import tee
it1 = (x for x in xrange(10))
it2, it3 = tee(it1)
print(next(it2)) # 0
print(next(it3)) # 0

以前只记得用tee的时候,原始的迭代器,即上面代码中的it1在分成两个后,不能再使用,否则会影响生成出来的两个迭代器。比如:

1
2
3
4
5
6
7
8
9
10
from itertools import tee
it1 = (x for x in xrange(10))
it2, it3 = tee(it1)
print(next(it2)) # 0
print(next(it1)) # 1
print(next(it2)) # 2
print(next(it3)) # 0
print(next(it3)) # 2

但是一直以来都没有深究其原因,现在我们来看一下,为什么在调用了tee(it1)之后,不能再修改it1。先看下官方文档给出的Python等价代码:

1
2
3
4
5
6
7
8
9
10
11
def tee(iterable, n=2):
it = iter(iterable)
deques = [collections.deque() for i in range(n)]
def gen(mydeque):
while True:
if not mydeque: # when the local deque is empty
newval = next(it) # fetch a new value and
for d in deques: # load it to all the deques
d.append(newval)
yield mydeque.popleft()
return tuple(gen(d) for d in deques)

简单说来,就是被tee分出来的几个迭代器,跑得快的那个会调用原始迭代器next(it),生成出来的数据会分别缓存到不同的先入先出队列中,跑的慢的,只要直接读队列中的数据,就可以了。而如果调用了原始的那个迭代器it1,它生成的数据不会被缓存到队列中,所以其他生器再调用时,这个数据就跳过了。

如果是为了解释上面例子中的现象,到此已经足矣。但相信一定有人会质疑,这个实现会不会存在资源浪费?记住,这只是Python的等价实现,而这些标准库的真正实现都是C。下面我们在进一步,看看tee的C实现。

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
/* Python-2.7.9/Objects/itertoolsmodule.c:643 */
static PyObject *
tee(PyObject *self, PyObject *args)
{
Py_ssize_t i, n=2;
PyObject *it, *iterable, *copyable, *result;
if (!PyArg_ParseTuple(args, "O|n", &iterable, &n))
return NULL;
if (n < 0) {
PyErr_SetString(PyExc_ValueError, "n must be >= 0");
return NULL;
}
result = PyTuple_New(n);
if (result == NULL)
return NULL;
if (n == 0)
return result;
it = PyObject_GetIter(iterable);
if (it == NULL) {
Py_DECREF(result);
return NULL;
}
if (!PyObject_HasAttrString(it, "__copy__")) {
copyable = tee_fromiterable(it);
Py_DECREF(it);
if (copyable == NULL) {
Py_DECREF(result);
return NULL;
}
} else
copyable = it;
PyTuple_SET_ITEM(result, 0, copyable);
for (i=1 ; i<n ; i++) {
copyable = PyObject_CallMethod(copyable, "__copy__", NULL);
if (copyable == NULL) {
Py_DECREF(result);
return NULL;
}
PyTuple_SET_ITEM(result, i, copyable);
}
return result;
}

这是tee的C实现,大概的意思就是先根据传入参数n生成一个tuple,然后对原始迭代器调用tee_fromiterable(it),得到一个teeobject,并放在这个tuple的第0个位置,tuple的其他维持都通过__copy__方法从第0个teeobject拷贝出来。

那我们再看下teeobject

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* Python-2.7.9/Objects/itertoolsmodule.c:327 */
#define LINKCELLS 57
typedef struct {
PyObject_HEAD
PyObject *it;
int numread;
PyObject *nextlink;
PyObject *(values[LINKCELLS]);
} teedataobject;
typedef struct {
PyObject_HEAD
teedataobject *dataobj;
int index;
PyObject *weakreflist;
} teeobject;

再来看下tee__copy__方法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Python-2.7.9/Objects/itertoolsmodule.c:515 */
static PyObject *
tee_copy(teeobject *to)
{
teeobject *newto;
newto = PyObject_GC_New(teeobject, &tee_type);
if (newto == NULL)
return NULL;
Py_INCREF(to->dataobj);
newto->dataobj = to->dataobj;
newto->index = to->index;
newto->weakreflist = NULL;
PyObject_GC_Track(newto);
return (PyObject *)newto;
}

稍微解释一下这几段代码,teeobjecttee方法返回的迭代器对象的类型,teeobject里保存了一个teedataobject *dataobj,这个数据用来缓存从原始迭代器计算出来的值,也就是Python等价实现中的deque。事实上,CPython中tee调用返回的所有teeobject的其实指向的都是同一个teedataobject,这样即使同时复制了多个迭代器,其缓存占用也只有一份,节省空间。

teeobject中保存teedataobject的数据结构也是一段链表,采用了类似前面说的整数对象缓存技术,而且如果所有迭代器都跑的差不多快,已经没用的teedataobject缓存会被垃圾回收器自动回收,这段实现很巧妙,感兴趣的读者可以去看一下源码。