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

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

Python中的字符串对象 - PyStringObject

在最一开始的概述中, 我们提到了Python中的字符串是不可变对象, 并且我们还知道这个字符串对象还是一个不定长对象. 也就是说, 除了前面说的整数对象这种定长对象分为可变和不可变, 不定长对象按照是否可变也分成可变和不可变.

不可变的字符串特性其实是很麻烦的, 这对于处理效率是个挑战, 例如我们常常说的字符串拼接, 就是一个效率较低的操作. 那么到底字符串对象在Python底层是如何存储的, 是不是也像整数对象那样, 有一个缓冲池之类的呢? 我们来看看吧.

初探PyStringObject

当然先去头文件中看看定义了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct {
PyObject_VAR_HEAD
long ob_shash;
int ob_sstate;
char ob_sval[1];

/* Invariants:
* ob_sval contains space for 'ob_size+1' elements.
* ob_sval[ob_size] == 0.
* ob_shash is the hash of the string or -1 if not computed yet.
* ob_sstate != 0 iff the string object is in stringobject.c's
* 'interned' dictionary; in this case the two references
* from 'interned' to this object are *not counted* in ob_refcnt.
*/
} PyStringObject;

源码中还给足了注释, 我们简单翻译一下就是这个样子: 这个ob_shash是这个string的哈希值, 为了节省重新计算的性能消耗和效率降低, 在计算之前是-1. ob_sstate这个玩意我们在后面再介绍.至于ob_sval一看名字也就猜到了, 是这个字符串具体的值. 但是你会疑问呀, 为啥只有一个长度啊? 其实这个东西是个字符指针, 指向一块内存. 也就是这个字符串真正的内容. 那么到底是多长呢, 看这个结构体的头部. 对了, 就是Python变长对象的通用头部, 里面的ob_size就是长度了.

另外, 我们知道在C中, 遇到\0就会认定字符串结束了, 但是Python中可不是这样. 所以说实际上的ob_size再加上1才是真正的字符串内存, 并且一个确定的事实是: ob_sval[ob_size] == '\0'

顺带附送一个字符串hash函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static long
string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;

if (a->ob_shash != -1)
return a->ob_shash;
len = a->ob_size;
p = (unsigned char *) a->ob_sval;
x = *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= a->ob_size;
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}

至于为啥这么算 我就不懂了…

接着我们来看下字符串类型对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PyTypeObject PyString_Type = {
PyObject_HEAD_INIT(&PyType_Type)
0,
"str",
sizeof(PyStringObject),
sizeof(char),
...
&string_as_number, /* tp_as_number */
&string_as_sequence, /* tp_as_sequence */
&string_as_mapping, /* tp_as_mapping */
...
&PyBaseString_Type, /* tp_base */
...
string_new, /* tp_new */
PyObject_Del, /* tp_free */
};

可以看到字符串支持数字, 序列和字典的各种行为. 另外值得注意的一个地方 — 它的基类, 指向了一个叫做PyBaseString的类型对象.

创建一个字符串对象

直接突入它最基本的创建函数, 来看下(还是有点长的, 我们慢慢分析吧):

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
PyObject *
PyString_FromString(const char *str)
{
register size_t size;
register PyStringObject *op;

assert(str != NULL);
size = strlen(str);
if (size > PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"string is too long for a Python string");
return NULL;
}
if (size == 0 && (op = nullstring) != NULL) {
#ifdef COUNT_ALLOCS
null_strings++;
#endif
Py_INCREF(op);
return (PyObject *)op;
}
if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL) {
#ifdef COUNT_ALLOCS
one_strings++;
#endif
Py_INCREF(op);
return (PyObject *)op;
}
#### 我自己的分割线 ####
/* Inline PyObject_NewVar */
op = (PyStringObject *)PyObject_MALLOC(sizeof(PyStringObject) + size);
if (op == NULL)
return PyErr_NoMemory();
PyObject_INIT_VAR(op, &PyString_Type, size);
op->ob_shash = -1;
op->ob_sstate = SSTATE_NOT_INTERNED;
Py_MEMCPY(op->ob_sval, str, size+1);
/* share short strings */
if (size == 0) {
PyObject *t = (PyObject *)op;
PyString_InternInPlace(&t);
op = (PyStringObject *)t;
nullstring = op;
Py_INCREF(op);
} else if (size == 1) {
PyObject *t = (PyObject *)op;
PyString_InternInPlace(&t);
op = (PyStringObject *)t;
characters[*str & UCHAR_MAX] = op;
Py_INCREF(op);
}
return (PyObject *) op;
}

我们先来看分割线上面的.首先检测是否为NULL, 如果不是就继续检查长度, 字符串的长度不能超过最大值, 这个最大值是一个和平台相关的值:

1
#define PY_SSIZE_T_MAX ((Py_ssize_t)(((size_t)-1)>>1))

这个值在我电脑上的测试结果:

1
9223372036854775807

这个数值是多大呢? 这么说吧, 你的硬盘上全是字符串, 把他们一股脑全部丢过来都没有超过长度, 而且还绰绰有余.

接下来先分成两种情况: 长度为0的空串或者是长度为1的字符.

Python预先准备了一个空字符串对象nullstring, 这个对象一开始是NULL, 当接收到空字符串的创建需求的时候, 会给他开辟一块内存, 这样 当以后再有需要空字符串的创建需求的时候, 就通过这个nullstring来检测, 如果nullstring已经存在了, 就直接返回引用. 可以做一个这样的小实验:

1
2
3
4
5
6
>>> a = str()
>>> b = str()
>>> hex(id(a))
'0x10c83e508'
>>> hex(id(b))
'0x10c83e508'

他们的内存指向是一样的.

如果长度是1, 那么和上面的空字符串处理几乎是一样的, Python维护了一个单字符的内存空间characters, 也就是printf("UCHAR_MAX = %u\n", UCHAR_MAX);这个语句输出的结果大小, 至于那个宏, 熟悉C的肯定都知道了, 定义在limits.h中.

接下来就来看分割线下面的部分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
op = (PyStringObject *)PyObject_MALLOC(sizeof(PyStringObject) + size);
if (op == NULL)
return PyErr_NoMemory();
PyObject_INIT_VAR(op, &PyString_Type, size);
op->ob_shash = -1;
op->ob_sstate = SSTATE_NOT_INTERNED;
Py_MEMCPY(op->ob_sval, str, size+1);
/* share short strings */
if (size == 0) {
PyObject *t = (PyObject *)op;
PyString_InternInPlace(&t);
op = (PyStringObject *)t;
nullstring = op;
Py_INCREF(op);
} else if (size == 1) {
PyObject *t = (PyObject *)op;
PyString_InternInPlace(&t);
op = (PyStringObject *)t;
characters[*str & UCHAR_MAX] = op;
Py_INCREF(op);
}
return (PyObject *) op;

为我们的字符串对象先分配内存, 之后根据PyString_Type的定义来进行初始化, 长度就是待创建的字符的长度. 接着初始化哈希为-1, 然后将ob_sstate加上了一个状态, 关于这个我们也先放一下. 继续向后面看, 我们把C类型的字符串赋值给PyStringObject的ob_sval, 当然还要加上最后的\0 此时就差不多了, 后面的那些我们先忽略.

仔细算一下, 一开始申请内存的时候长度的计算. 我们知道C中的字符串的最后有一个\0. 而string标准库中的strlen是会把最后的\0减掉的, 这样的申请的内存空间就会缺少最后的\0. 那就不对了.

真的是这样吗? 在PyStringObject的定义中, 有一个char类型的指针, 指向真实的字符串内存. 如果把这个加上 那就对了. 其实真实的内存分配就是这个样子的:

比如”Python”这个字符串:

1
ref type size hash state P(这个P就是val) [y t h o n \0] 加上的strlen("Python") = 6

这样计算的一个大前提就是, 传入的字符串必须是\0结束. 否则内存的申请就会出问题. 所以为了更灵活, 还有一个创建的函数:

1
2
3
PyObject *
PyString_FromStringAndSize(const char *str, Py_ssize_t size)
{...}

这里就不再需要使用\0结尾了, 但是要求就变成了这样了:

1
assert(size >= 0);

其他的过程几乎就和前一个创建函数一样了.

PyStringObject的Intern机制

现在我们来把之前遗漏的地方补充一下, 也就是当字符串长度为0或者为1的时候, 发生的特殊动作. 也就是**intern**机制.

这个机制存在的意义是什么呢? 要搞清楚这个, 我们要先知道这个机制是干嘛的.

当我们在比较两个字符串是不是相等的时候, 是不是要确保每一个字符都一样呀. 另外, 如果是两个相等的字符串, 我是不是可以考虑把他们存在一个地方, 只要返回引用从而节省内存. 这个Intern机制就同时解决了这两个问题.

intern机制使得在Python运行期间, 一个值对应一个PyStringObject对象, 如果值相同就会映射到同一个PyStringObject对象上. 从而节约宝贵的内存. 并且有趣的是, 这种机制同时为字符串判断提供了一个简便方法, 那就是直接比较他们是不是一个PyObject*指针指向就好了.

接下来我们来看看具体是怎么做的:

1
2
3
4
5
6
7
8
9
10
11
12
13
if (size == 0) {
PyObject *t = (PyObject *)op;
PyString_InternInPlace(&t);
op = (PyStringObject *)t;
nullstring = op;
Py_INCREF(op);
} else if (size == 1 && str != NULL) {
PyObject *t = (PyObject *)op;
PyString_InternInPlace(&t);
op = (PyStringObject *)t;
characters[*str & UCHAR_MAX] = op;
Py_INCREF(op);
}

关键的函数就是那个PyString_InternInPlace了, 来看下:

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
void
PyString_InternInPlace(PyObject **p)
{
register PyStringObject *s = (PyStringObject *)(*p);
PyObject *t;
if (s == NULL || !PyString_Check(s))
Py_FatalError("PyString_InternInPlace: strings only please!");
/* If it's a string subclass, we don't really know what putting
it in the interned dict might do. */
if (!PyString_CheckExact(s))
return;
if (PyString_CHECK_INTERNED(s))
return;
if (interned == NULL) {
interned = PyDict_New();
if (interned == NULL) {
PyErr_Clear(); /* Don't leave an exception */
return;
}
}
t = PyDict_GetItem(interned, (PyObject *)s);
if (t) {
Py_INCREF(t);
Py_DECREF(*p);
*p = t;
return;
}

if (PyDict_SetItem(interned, (PyObject *)s, (PyObject *)s) < 0) {
PyErr_Clear();
return;
}
/* The two references in interned are not counted by refcnt.
The string deallocator will take care of this */
s->ob_refcnt -= 2;
PyString_CHECK_INTERNED(s) = SSTATE_INTERNED_MORTAL;
}

一开始就进行了严格的类型审查, 甚至连string的子类也纳入考虑范围. 在确定了是PyStringObject之后, 就要判断他的intern状态了. 这个状态保存在什么地方呢? 对啦, 就是我们之前一直都在忽略的地方: ob_sstate. 最一开始创建对象的时候 先是给他赋了一个SSTATE_NOT_INTERNED的初始值, 这个其实就是0, 还有两个状态, 定义是这样的:

1
2
3
#define SSTATE_NOT_INTERNED 0
#define SSTATE_INTERNED_MORTAL 1
#define SSTATE_INTERNED_IMMORTAL 2

也就是说, 当没有intered的时候, if判断会返回False的. 所以在一开始的时候不会返回, 如果一个字符串对象已经获得了intern状态, 那么就会直接返回了.

好, 那我们继续. 到了检查一个叫做intered的玩意, 这是什么呢? 这个就是intern机制的一个核心元素了, 这个Python对象指针指向的字典储存了所有interned的字符串, 至于为什么说是个字典, 我们继续向后看.

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
void
PyString_InternInPlace(PyObject **p)
{
...
if (interned == NULL) {
interned = PyDict_New();
if (interned == NULL) {
PyErr_Clear(); /* Don't leave an exception */
return;
}
}
t = PyDict_GetItem(interned, (PyObject *)s);
if (t) {
Py_INCREF(t);
Py_DECREF(*p);
*p = t;
return;
}

if (PyDict_SetItem(interned, (PyObject *)s, (PyObject *)s) < 0) {
PyErr_Clear();
return;
}
/* The two references in interned are not counted by refcnt.
The string deallocator will take care of this */
s->ob_refcnt -= 2;
PyString_CHECK_INTERNED(s) = SSTATE_INTERNED_MORTAL;
}

如果还未初始化我们的interned指针, 就会调用一个PyDictObject的New方法, 这个等我们到后面说到字典对象再细说吧. 反之现在就只需要知道是个字典就好了. 接着我们尝试从这个字典里面取出这个字符串对象, 如果真的存在, 进行引用计数的调整:

  • 字典中的那个interned引用计数加一
  • 这个新的字符串对象的引用计数减一

接着就是关键步骤了, 另这个指向字符串的指针的指针地址调整成字典中的那个指针地址. 最后返回.

在这里我们插一句, 之前我们说intern机制是为了节约内存. 没错是节省了, 但不是像一开始说的是仅创建一个字符串对象. 对象还是会被创建的. 只不过在后面的检查中由于引用计数减了1变成了0导致被Python的垃圾回收机制销毁掉了. 难道就不能不创建这么一个麻烦的temp变量吗? 答案是, 不能. 原因就是因为整体的设计以及PyDict的接口设计. 最一开始我们就说过在Python中对象都是用PyObject这个头指针来引用的, 这样的话就一定需要一个Object才可以引用

如果没有, 那自然就是加入到字典了, 这里正常应该是返回0, 如果出现异常则会返回-1.

那么想想看, 为啥插入之后要把引用计数-2? 来思考这样的问题哦, 在interned字典中的字符串是自带两个引用的, 也就是来自Key和Value. 而interned是陪伴Python程序一生的, 也就是说只要Python进程不终结, Python虚拟机还在运行, 这两个引用就会一直存在, 这肯定是不行的. 于是, interned中的引用不算做有效引用. 这就是-2的原因. 继续深入下去, 我们来看看析构方法:

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
string_dealloc(PyObject *op)
{
switch (PyString_CHECK_INTERNED(op)) {
case SSTATE_NOT_INTERNED:
break;

case SSTATE_INTERNED_MORTAL:
/* revive dead object temporarily for DelItem */
op->ob_refcnt = 3;
if (PyDict_DelItem(interned, op) != 0)
Py_FatalError(
"deletion of interned string failed");
break;

case SSTATE_INTERNED_IMMORTAL:
Py_FatalError("Immortal interned string died.");

default:
Py_FatalError("Inconsistent interned string state.");
}
op->ob_type->tp_free(op);
}

只需要看SSTATE_INTERNED_MORTAL这个判断就行了, 可以看到为了删除interned字典中的键值对, 直接就把引用计数变成3, 就像是复活一样嘿嘿.

最后, 作为intern机制的补充. 我们看到还有一个SSTATE_INTERNED_IMMORTAL状态. 这个状态和之前我们接触的那个有什么不同吗? 看名字也就知道了, 这种状态的字符串是和虚拟机寿命相同的:

1
2
3
4
5
6
7
8
9
void
PyString_InternImmortal(PyObject **p)
{
PyString_InternInPlace(p);
if (PyString_CHECK_INTERNED(*p) != SSTATE_INTERNED_IMMORTAL) {
PyString_CHECK_INTERNED(*p) = SSTATE_INTERNED_IMMORTAL;
Py_INCREF(*p);
}
}

其实关键的地方也就是那个引用计数的增加, 以及象征性的状态改变.

字符缓冲池以及典型问题效率讨论

接下来我们来看看Python对于字符的处理. 我们之前在说整数对象的时候, 说Python会为小整数开个缓冲对象池. 那么对于简单的字符, Python自然也采取了类似的处理. 我们之前其实已经提到过的, 就是characters, 这个缓冲池的大小就是UCHAR_MAX所定义的大小.

所以说, 当我们进行一个char长度的字符串(其实就是字符)的创建的时候, 会经过下面的过程:

  • 申请内存创建PyStringObject
  • 对这个PyStringObject进行Intern操作
  • 缓存到characters缓冲池中

OK, 这个缓冲池的设计要比整数对象好理解多了; 现在我们来探讨一个典型问题 — 字符串拼接

你一定知道这样的结论, 尽量使用str.join函数而不要使用+运算符进行字符串拼接. 但是为什么呢? 到底底层是什么样子的呢? 现在我们就从源代码层面来看看:

如果使用+运算符的话, 调用的函数是这个:

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
static PyObject *
string_concat(register PyStringObject *a, register PyObject *bb)
{
register Py_ssize_t size;
register PyStringObject *op;
if (!PyString_Check(bb)) {
#ifdef Py_USING_UNICODE
if (PyUnicode_Check(bb))
return PyUnicode_Concat((PyObject *)a, bb);
#endif
PyErr_Format(PyExc_TypeError,
"cannot concatenate 'str' and '%.200s' objects",
bb->ob_type->tp_name);
return NULL;
}
#define b ((PyStringObject *)bb)
/* Optimize cases with empty left or right operand */
if ((a->ob_size == 0 || b->ob_size == 0) &&
PyString_CheckExact(a) && PyString_CheckExact(b)) {
if (a->ob_size == 0) {
Py_INCREF(bb);
return bb;
}
Py_INCREF(a);
return (PyObject *)a;
}
size = a->ob_size + b->ob_size;
if (size < 0) {
PyErr_SetString(PyExc_OverflowError,
"strings are too large to concat");
return NULL;
}

/* Inline PyObject_NewVar */
op = (PyStringObject *)PyObject_MALLOC(sizeof(PyStringObject) + size);
if (op == NULL)
return PyErr_NoMemory();
PyObject_INIT_VAR(op, &PyString_Type, size);
op->ob_shash = -1;
op->ob_sstate = SSTATE_NOT_INTERNED;
Py_MEMCPY(op->ob_sval, a->ob_sval, a->ob_size);
Py_MEMCPY(op->ob_sval + a->ob_size, b->ob_sval, b->ob_size);
op->ob_sval[size] = '\0';
return (PyObject *) op;
#undef b
}

哦对了, 这个是作为序列的行为, 所以你会在序列行为方法里面找到, 如果你在数字里面找的话是找不到的.

那我们来分析下吧.

27行之前的代码可以忽略掉了, 就是在做类型检查, 以及如果出现空字符串的特殊case的处理.后面的就是一般情况下了, 我们先计算两个字符串加起来的总长度, 接着就根据这个长度进行内存申请, 然后进行常规的初始化和hash略过计算以及Intern状态初始化, 接着执行两次内存拷贝, 就像是先把前面的贴在前面紧接着把后面的那个贴在后面. 最后把\0补充上, 就可以返回新对象了.

注意 这个过程是每两个String对象加起来. 如果是多个字符串, 这个过程就要进行多次. 那么我们的join函数在干什么呢?

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
static PyObject *
string_join(PyStringObject *self, PyObject *orig)
{
char *sep = PyString_AS_STRING(self);
const Py_ssize_t seplen = PyString_GET_SIZE(self);
PyObject *res = NULL;
char *p;
Py_ssize_t seqlen = 0;
size_t sz = 0;
Py_ssize_t i;
PyObject *seq, *item;

seq = PySequence_Fast(orig, "");
if (seq == NULL) {
return NULL;
}

seqlen = PySequence_Size(seq);
if (seqlen == 0) {
Py_DECREF(seq);
return PyString_FromString("");
}
if (seqlen == 1) {
item = PySequence_Fast_GET_ITEM(seq, 0);
if (PyString_CheckExact(item) || PyUnicode_CheckExact(item)) {
Py_INCREF(item);
Py_DECREF(seq);
return item;
}
}

/* There are at least two things to join, or else we have a subclass
* of the builtin types in the sequence.
* Do a pre-pass to figure out the total amount of space we'll
* need (sz), see whether any argument is absurd, and defer to
* the Unicode join if appropriate.
*/
for (i = 0; i < seqlen; i++) {
const size_t old_sz = sz;
item = PySequence_Fast_GET_ITEM(seq, i);
if (!PyString_Check(item)){
#ifdef Py_USING_UNICODE
if (PyUnicode_Check(item)) {
/* Defer to Unicode join.
* CAUTION: There's no gurantee that the
* original sequence can be iterated over
* again, so we must pass seq here.
*/
PyObject *result;
result = PyUnicode_Join((PyObject *)self, seq);
Py_DECREF(seq);
return result;
}
#endif
PyErr_Format(PyExc_TypeError,
"sequence item %zd: expected string,"
" %.80s found",
i, item->ob_type->tp_name);
Py_DECREF(seq);
return NULL;
}
sz += PyString_GET_SIZE(item);
if (i != 0)
sz += seplen;
if (sz < old_sz || sz > PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"join() result is too long for a Python string");
Py_DECREF(seq);
return NULL;
}
}

/* Allocate result space. */
res = PyString_FromStringAndSize((char*)NULL, sz);
if (res == NULL) {
Py_DECREF(seq);
return NULL;
}

/* Catenate everything. */
p = PyString_AS_STRING(res);
for (i = 0; i < seqlen; ++i) {
size_t n;
item = PySequence_Fast_GET_ITEM(seq, i);
n = PyString_GET_SIZE(item);
Py_MEMCPY(p, PyString_AS_STRING(item), n);
p += n;
if (i < seqlen - 1) {
Py_MEMCPY(p, sep, seplen);
p += seplen;
}
}

Py_DECREF(seq);
return res;
}

有点长哈, 不过没关系. 我们还是可以把我们讨论的重点关系不大的代码踢走. 其实核心部分就是再做这样的事, 先计算间隔(填充符)的长度, 接着遍历整个列表, 把每一个item的长度加上来, 当然还有填充了. 接着一次性的生成结果长度的内存空间.

接着再次遍历, 这一次就是把每一个字符串扔到他该在的位置上, 最后把seq的引用计数减掉让垃圾处理机制把它干掉就行了.