Python源码剖析笔记4-内建数据类型
Python内建数据类型包括整数对象PyIntObject，字符串对象PyStringObject，列表对象PyListObject以及字典对象PyDictObject等。整数对象之前已经分析过了，这一篇文章准备分析下余下几个对象，这次在《python源码剖析》中已经写的很详细的部分就不赘述了，主要是总结一些之前看书时疑惑的地方。
1 整数对象-PyIntObject
参见 python整数对象。
2 字符串对象-PyStringObject
2.1 基本定义
python中的字符串对象PyStringObject，对应的类型对象是PyString_Type。PyStringObject对象的定义如下：
#define PyObject_VAR_HEAD \
Py_ssize_t ob_refcnt; \
struct _typeobject *ob_type; \
Py_ssize_t ob_size;
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;
字符串长度在头部PyObject_VAR_HEAD的ob_size字段中维护，而ob_sval则是指向一段长度为ob_size+1个字节的内存，比如字符串'hello'，ob_size=5，而ob_sval长度为6，ob_sval[6] = '\0'。 ob_sstate是字符串状态，标示字符串是否经过intern机制处理。ob_shash是字符串的哈希值，在字典以及字符串比较等多处有用到这个哈希值。
2.2 字符串interned机制
当然在字符串对象中一个比较重要的就是intern机制。那么问题来了，什么样的字符串才会interned呢？实验一下先，可以发现如果字符串有空格是不会被interned的，实际上，字符串中的字符必须都是属于"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"才会interned。例子中的hello world因为有空格不在interned字符集中，所以该字符串不会interned。这个是在构建PyCodeObject对象的时候进行的。之前已经分析过，python的py文件需要编译成字节码执行，当然直接执行和import导入模块有所不同，不过都会构建PyCodeObject对象。在构建PyCodeObject对象函数PyCode_New(Objects/codeObject.c文件)中，会执行变量名、常量等字符串的interned操作。
另外一个需要说明的是，在编译py文件成字节码并保存到pyc文件过程中，字符串对象分为三种情况处理。其一是非interned字符串，比如刚刚说的hello world字符串，对象标识是s。其二是interned字符串，比如hello，对象标识是t。其三是已经interned过的字符串，在pyc中记录的对象标识是R。之所以有R标记的字符串，是为了节省空间，因为它最终只记录一个字符串的偏移位置。比如之前已经有了字符串'hello',则写入标记s以及字符串内容'hello',第二次遇到'hello'时则只是写入标记R以及'hello'在常量元组co_consts中的索引值。这样从pyc内容中构建PyCodeObject对象的时候，根据R标识类型字符串记录的索引得到字符串。
#测试intern机制test_interned.py
a = 'hello world'
b = 'hello'
def test():
c = 'hello world'
d = 'hello'
print c is a #False，'hello world' 没有interned
print d is b #True， 'hello' 已经interned
test()
关于R标记，还要多说一点，我之前看书的时候也有点疑惑什么情况下会用到R标记呢，因为你在一个模块里面对一个字符串多次引用，在PyCodeObject对象的co_consts中还是只会存在一份的。比如下面的代码，显然s和t针对test.py对应的PyCodeObject对象，只会有一个常量'hello',虽然这个字符串会被interned，那么R标记是用在哪里呢？其实是用在另外的PyCodeObject中。比如下面的代码，对应两个PyCodeObject，其中test_stringref.py本身一个，以及函数test对应一个PyCodeObject。编译后得到的pyc文件内容如下所示，根据前面的文章pyc格式分析，可以看到在test_stringref.py本身对应的PyCodeObject中，co_consts为('hello', <code object test at 0x10c130af8, file "str.py"", line 4>, None)，这里看到s和t引用的是同一个字符串，这一点通过字节码指令也可以看到。 在pyc中'hello'存储的是标识t以及字符串内容。而函数test对应的PyCodeObject中，对应的co_consts为(None, hello)，但是在pyc中对应字符串hello存储的是标记R以及索引0。
此外，如果直接运行python xxx.py，虽然也会编译成PyCodeObject对象，但是不会生成pyc文件，也不会有R标识类型这些东西了，不过interned机制在运行的时候同样会生效。不同的地方在于，如果是从pyc文件运行会根据R标识类型来将对应字符串指向同一个对象，而如果是直接运行的，则需要通过interned字典来对后面遇到的相同的可以interned字符串对象赋值为interned字符串对象的地址，进行并回收后面遇到的那个字符串。
单个字符和空字符都会interned，这个可以很简单的验证。
#测试字符串类型标识 test_stringref.py
s = 'hello'
t = 'hello'
def test():
k = 'hello'
#test_stringref.py对应的字节码
0 LOAD_CONST 0 (0)
3 STORE_NAME 0 (0)
6 LOAD_CONST 0 (0)
9 STORE_NAME 1 (1)
12 LOAD_CONST 1 (1)
15 MAKE_FUNCTION 0
18 STORE_NAME 2 (2)
21 LOAD_CONST 2 (2)
24 RETURN_VALUE
#test_stringref.pyc文件
00000000 03 f3 0d 0a 78 3e 99 55 63 00 00 00 00 00 00 00 |....x>.Uc.......|
00000010 00 01 00 00 00 40 00 00 00 73 19 00 00 00 64 00 |.....@...s....d.|
00000020 00 5a 00 00 64 00 00 5a 01 00 64 01 00 84 00 00 |.Z..d..Z..d.....|
00000030 5a 02 00 64 02 00 53 28 03 00 00 00 74 05 00 00 |Z..d..S(....t...|
00000040 00 68 65 6c 6c 6f 63 00 00 00 00 01 00 00 00 01 |.helloc.........|
00000050 00 00 00 43 00 00 00 73 0a 00 00 00 64 01 00 7d |...C...s....d..}|
00000060 00 00 64 00 00 53 28 02 00 00 00 4e 52 00 00 00 |..d..S(....NR...|
00000070 00 28 00 00 00 00 28 01 00 00 00 74 01 00 00 00 |.(....(....t....|
00000080 6b 28 00 00 00 00 28 00 00 00 00 73 1d 00 00 00 |k(....(....s....|
00000090 2f 55 73 65 72 73 2f 73 73 6a 2f 50 72 6f 67 2f |/Users/ssj/Prog/|
000000a0 70 79 74 68 6f 6e 2f 73 74 72 2e 70 79 74 04 00 |python/str.pyt..|
000000b0 00 00 74 65 73 74 04 00 00 00 73 02 00 00 00 00 |..test....s.....|
000000c0 01 4e 28 03 00 00 00 74 01 00 00 00 73 74 01 00 |.N(....t....st..|
000000d0 00 00 74 52 02 00 00 00 28 00 00 00 00 28 00 00 |..tR....(....(..|
000000e0 00 00 28 00 00 00 00 73 1d 00 00 00 2f 55 73 65 |..(....s..../Use|
000000f0 72 73 2f 73 73 6a 2f 50 72 6f 67 2f 70 79 74 68 |rs/ssj/Prog/pyth|
00000100 6f 6e 2f 73 74 72 2e 70 79 74 08 00 00 00 3c 6d |on/str.pyt....<m|
00000110 6f 64 75 6c 65 3e 01 00 00 00 73 04 00 00 00 06 |odule>....s.....|
00000120 01 06 02 |...|
00000123
2.3 字符串拼接效率问题
另外一个需要注意的就是字符串拼接的效率问题。如果是简单的 s1+s2+s3这样拼接，那么每次拼接都要分配一次内存，这样需要分配两次内存。而如果通过''.join([s1, s2, s3])来拼接，则只需要分配一次内存，在拼接字符串较多的时候，通过join操作拼接字符串效率会有大幅提高。
3 列表对象-PyListObject
Python中的List对象实现有点类似STL中的vector，依托的是数组形式来实现列表。定义如下：
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
可以看到前面跟PyStringObject是一样的头部，其中的ob_size是当前列表元素数目，而allocated是分配的空间大小， ob_size <= allocated，也就是说一般情况下会多分配一点空间，以减少多次分配带来性能问题。列表初始化分为两部分，列表本身结构初始化和列表维护的对象列表ob_item初始化。当然，列表本身初始化也采用了缓冲池机制，如果缓冲池列表中有空闲的列表可以用，就可以直接拿来用而不需要再次分配内存了。当然，虽然列表结构本身可以通过缓冲池复用，但是其中维护的对象列表ob_item是不会复用的，从缓冲池中得到列表结构后还需要给ob_item分配空间（空间大小为 size * sizeof(PyObject *),size为创建的列表大小）。
列表分配的空间大小allocated在通过insert，append操作插入元素时或者通过remove, del操作时会进行调整，也就是说即可能变大也可能变小。调整列表大小的函数是list_resize()，调整条件如下:
(1) newsize <= allocated && newsize >= allocated / 2:简单调整ob_size的值，不需要扩容。
(2) 否则，调整大小为 new_allocated = (newsize >> 3) + (newsize < 9 ? 3: 6) + newsize.
那么，假定有一个语句如下list = [1]，则字节码其实就是创建一个大小为1(ob_size和allocated此时都是1)的列表，然后将列表list中的ob_item的第0个元素设置为整数对象1。需要注意的是，当你创建一个空列表然后直接赋值则会出错的，比如下面那样，这是因为你创建一个空列表时ob_item被设置为NULL，并没有分配内存，因此会报错。
##test1.py 未分配对象列表内存导致赋值错误
list = []
list[0] = 1 #错误
还是继续刚刚那个栗子，现在有列表list=[1]，然后执行list.append(2)，此时ob_size=2，而根据上面的策略，allocated调整为5.再执行list.append(3)插入3，则此时ob_size=3，而allocated=5不变。如果接着list.remove(2)，则ob_size=2，allocated=5不变。此时如果再执行list.remove(3)，则根据上面的调整公式，ob_size=1，allocated减小到4。
4 字典对象-PyDictObject
python字典对象采用的散列冲突解决方法为开放定址法，不同于STL中的开链法。python采用的开放定址法在发生散列冲突时，会根据一个冲突探测函数计算下一个探测的位置，直到找到一个不冲突的位置。而在删除元素的时候，并不会直接删除，而是设置一个dummy标记，这样可以保证在冲突探测的时候不出错，此外这个dummy标记的元素下次插入新元素时可以被再次利用。
字典中的一个键值对称为一个entry，字典由PyDictEntry的数组构成。定义如下：
typedef struct {
Py_ssize_t me_hash; //me_key的哈希值
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
#define PyDict_MINSIZE 8
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; /* # Active + # Dummy */
Py_ssize_t ma_used; /* # Active */
Py_ssize_t ma_mask;
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
};
键值对有active， dummy以及unused三个状态。初始为unused状态，me_key == NULL, me_value == NULL。而如果是active状态，则me_key != NULL, me_key != dummy, me_value != NULL,如果是dummy状态，则me_key == dummy, me_value == NULL.三个状态的转换则是：执行插入操作则由unused或者dummy状态变成active状态，执行删除操作则从active状态变成dummy状态。
PyDictObject定义如上面所示，其中ma_fill是元素总数目，包括active和dummy状态的键值对。而ma_used是active键值对数目，ma_mask用来定位元素在数组中的索引，大小为数组长度减一。如果数组ma_table为8，则ma_mask值为7.注意，这里还有个ma_smalltable，大小初始为8,初始化时，字典的ma_table会指向ma_smalltable，当装载率大于等于2/3时，字典扩容。(即ma_fill / (ma_mask + 1)) >=2/3)，会将ma_table指向新分配的空间，并搬移键值对到新的table中。
PyDictObject也采用了缓冲池机制，其原理类似PyListObject，这里不再赘述。需要额外提到的一点是字典中的元素搜索机制，这里说下常用的lookdict_string函数，其针对的是字符串键的查找。查找流程如下：
a. 查找的时候会先根据字符串hash值获取键值对索引，如果对应的键值对entry为unused状态，则表示搜索失败，如果freeslot不为NULL，则返回freeslot（freeslot指向dummy状态的entry），否则返回entry。
b. 如果entry为其他状态，则检查me_key引用是否相同，相同则返回该entry.
c. 如果me_key引用不同，则检查me_key值是否相同(即比较hash值以及me_key的值)，如果相同，则返回entry，否则继续下一轮查询。
python中冲突探测函数如下，其中j为当前的索引，perturb初始化为me_key的hash值，通过不断调整j和perturb值，会不断探测ma_table数组中的元素。由于perturb值是不断减小的，所以最终会退化为j = 5 * j + 1，假定元素数为8，初始j = 0， 使用退化后的探测函数探测到的索引依次是 0, 1, 6, 7, 4, 5, 2, 3, 0。这个探测函数顺序有一定随机性，这其实是通过一个线性同余方程来获取2**i范围内的伪随机数作为索引，比线性探测函数如f(x) = x + 1效果要好一些。其中2**i是哈希表大小。至于为什么 j = (5*j) + 1; j % 2**i;这样能够得到0...2**i-1范围内的数字后再从头开始循环，证明方法暂时没有找到，不过简单验证确实是没有问题的。
j = (5*j) + 1 + perturb; // perturb初始值为键的hash值
perturb >>= PERTURB_SHIFT; // PERTURB_SHIFT=5，据说效果比较好
use j % 2**i as the next table index;
根据这个冲突探测算法，可以看到字典中插入键值对时的冲突探测和解决流程。具体例子参见http://www.laurentluce.com/posts/python-dictionary-implementation/
