Python源碼剖析筆記4-內(nèi)建數(shù)據(jù)類型
Python內(nèi)建數(shù)據(jù)類型包括整數(shù)對象PyIntObject，字符串對象PyStringObject奠蹬，列表對象PyListObject以及字典對象PyDictObject等嗡午。整數(shù)對象之前已經(jīng)分析過了，這一篇文章準(zhǔn)備分析下余下幾個對象狸演，這次在《python源碼剖析》中已經(jīng)寫的很詳細的部分就不贅述了僻他，主要是總結(jié)一些之前看書時疑惑的地方吨拗。
1 整數(shù)對象-PyIntObject
參見 python整數(shù)對象婿斥。
2 字符串對象-PyStringObject
2.1 基本定義
python中的字符串對象PyStringObject哨鸭，對應(yīng)的類型對象是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; //對象狀態(tài)
char ob_sval[1]; //字符串內(nèi)容
/* 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個字節(jié)的內(nèi)存，比如字符串'hello'赖舟，ob_size=5夸楣，而ob_sval長度為6，ob_sval[6] = '\0'石洗。 ob_sstate是字符串狀態(tài)紧显，標(biāo)示字符串是否經(jīng)過intern機制處理。ob_shash是字符串的哈希值涉兽，在字典以及字符串比較等多處有用到這個哈希值篙程。
2.2 字符串interned機制
當(dāng)然在字符串對象中一個比較重要的就是intern機制虱饿。那么問題來了，什么樣的字符串才會interned呢渴肉？實驗一下先折柠，可以發(fā)現(xiàn)如果字符串有空格是不會被interned的，實際上前塔，字符串中的字符必須都是屬于"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"才會interned。例子中的hello world因為有空格不在interned字符集中食零，所以該字符串不會interned寂屏。這個是在構(gòu)建PyCodeObject對象的時候進行的迁霎。之前已經(jīng)分析過，python的py文件需要編譯成字節(jié)碼執(zhí)行秘豹，當(dāng)然直接執(zhí)行和import導(dǎo)入模塊有所不同昌粤，不過都會構(gòu)建PyCodeObject對象。在構(gòu)建PyCodeObject對象函數(shù)PyCode_New(Objects/codeObject.c文件)中凄贩，會執(zhí)行變量名袱讹、常量等字符串的interned操作捷雕。
另外一個需要說明的是评肆，在編譯py文件成字節(jié)碼并保存到pyc文件過程中，字符串對象分為三種情況處理非区。其一是非interned字符串，比如剛剛說的hello world字符串盹廷，對象標(biāo)識是s征绸。其二是interned字符串，比如hello俄占，對象標(biāo)識是t管怠。其三是已經(jīng)interned過的字符串，在pyc中記錄的對象標(biāo)識是R缸榄。之所以有R標(biāo)記的字符串，是為了節(jié)省空間甚带，因為它最終只記錄一個字符串的偏移位置她肯。比如之前已經(jīng)有了字符串'hello',則寫入標(biāo)記s以及字符串內(nèi)容'hello',第二次遇到'hello'時則只是寫入標(biāo)記R以及'hello'在常量元組co_consts中的索引值佳头。這樣從pyc內(nèi)容中構(gòu)建PyCodeObject對象的時候，根據(jù)R標(biāo)識類型字符串記錄的索引得到字符串晴氨。
#測試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' 已經(jīng)interned
test()
關(guān)于R標(biāo)記籽前，還要多說一點亭珍，我之前看書的時候也有點疑惑什么情況下會用到R標(biāo)記呢，因為你在一個模塊里面對一個字符串多次引用枝哄，在PyCodeObject對象的co_consts中還是只會存在一份的肄梨。比如下面的代碼，顯然s和t針對test.py對應(yīng)的PyCodeObject對象挠锥，只會有一個常量'hello',雖然這個字符串會被interned众羡，那么R標(biāo)記是用在哪里呢？其實是用在另外的PyCodeObject中瘪贱。比如下面的代碼纱控，對應(yīng)兩個PyCodeObject，其中test_stringref.py本身一個菜秦，以及函數(shù)test對應(yīng)一個PyCodeObject甜害。編譯后得到的pyc文件內(nèi)容如下所示，根據(jù)前面的文章pyc格式分析球昨，可以看到在test_stringref.py本身對應(yīng)的PyCodeObject中尔店，co_consts為('hello', <code object test at 0x10c130af8, file "str.py"", line 4>, None)，這里看到s和t引用的是同一個字符串主慰，這一點通過字節(jié)碼指令也可以看到嚣州。 在pyc中'hello'存儲的是標(biāo)識t以及字符串內(nèi)容。而函數(shù)test對應(yīng)的PyCodeObject中共螺，對應(yīng)的co_consts為(None, hello)该肴，但是在pyc中對應(yīng)字符串hello存儲的是標(biāo)記R以及索引0。
此外藐不，如果直接運行python xxx.py匀哄，雖然也會編譯成PyCodeObject對象，但是不會生成pyc文件雏蛮，也不會有R標(biāo)識類型這些東西了涎嚼，不過interned機制在運行的時候同樣會生效。不同的地方在于挑秉，如果是從pyc文件運行會根據(jù)R標(biāo)識類型來將對應(yīng)字符串指向同一個對象法梯，而如果是直接運行的，則需要通過interned字典來對后面遇到的相同的可以interned字符串對象賦值為interned字符串對象的地址犀概，進行并回收后面遇到的那個字符串立哑。
單個字符和空字符都會interned夜惭，這個可以很簡單的驗證。
#測試字符串類型標(biāo)識 test_stringref.py
s = 'hello'
t = 'hello'
def test():
k = 'hello'
#test_stringref.py對應(yīng)的字節(jié)碼
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這樣拼接滥嘴，那么每次拼接都要分配一次內(nèi)存，這樣需要分配兩次內(nèi)存至耻。而如果通過''.join([s1, s2, s3])來拼接若皱，則只需要分配一次內(nèi)存，在拼接字符串較多的時候尘颓，通過join操作拼接字符串效率會有大幅提高走触。
3 列表對象-PyListObject
Python中的List對象實現(xiàn)有點類似STL中的vector，依托的是數(shù)組形式來實現(xiàn)列表疤苹。定義如下：
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是當(dāng)前列表元素數(shù)目，而allocated是分配的空間大小卧土， ob_size <= allocated惫皱，也就是說一般情況下會多分配一點空間，以減少多次分配帶來性能問題尤莺。列表初始化分為兩部分旅敷，列表本身結(jié)構(gòu)初始化和列表維護的對象列表ob_item初始化。當(dāng)然颤霎，列表本身初始化也采用了緩沖池機制媳谁，如果緩沖池列表中有空閑的列表可以用，就可以直接拿來用而不需要再次分配內(nèi)存了友酱。當(dāng)然晴音，雖然列表結(jié)構(gòu)本身可以通過緩沖池復(fù)用，但是其中維護的對象列表ob_item是不會復(fù)用的缔杉，從緩沖池中得到列表結(jié)構(gòu)后還需要給ob_item分配空間（空間大小為 size * sizeof(PyObject *),size為創(chuàng)建的列表大小）锤躁。
列表分配的空間大小allocated在通過insert，append操作插入元素時或者通過remove, del操作時會進行調(diào)整或详，也就是說即可能變大也可能變小进苍。調(diào)整列表大小的函數(shù)是list_resize()，調(diào)整條件如下:
(1) newsize <= allocated && newsize >= allocated / 2:簡單調(diào)整ob_size的值鸭叙，不需要擴容。
(2) 否則拣宏，調(diào)整大小為 new_allocated = (newsize >> 3) + (newsize < 9 ? 3: 6) + newsize.
那么沈贝，假定有一個語句如下list = [1]，則字節(jié)碼其實就是創(chuàng)建一個大小為1(ob_size和allocated此時都是1)的列表勋乾，然后將列表list中的ob_item的第0個元素設(shè)置為整數(shù)對象1宋下。需要注意的是嗡善，當(dāng)你創(chuàng)建一個空列表然后直接賦值則會出錯的，比如下面那樣学歧，這是因為你創(chuàng)建一個空列表時ob_item被設(shè)置為NULL罩引，并沒有分配內(nèi)存，因此會報錯枝笨。
##test1.py 未分配對象列表內(nèi)存導(dǎo)致賦值錯誤
list = []
list[0] = 1 #錯誤
還是繼續(xù)剛剛那個栗子袁铐，現(xiàn)在有列表list=[1]，然后執(zhí)行l(wèi)ist.append(2)横浑，此時ob_size=2剔桨，而根據(jù)上面的策略，allocated調(diào)整為5.再執(zhí)行l(wèi)ist.append(3)插入3徙融，則此時ob_size=3洒缀，而allocated=5不變。如果接著list.remove(2)欺冀，則ob_size=2树绩，allocated=5不變。此時如果再執(zhí)行l(wèi)ist.remove(3)隐轩，則根據(jù)上面的調(diào)整公式饺饭，ob_size=1，allocated減小到4龙助。
4 字典對象-PyDictObject
python字典對象采用的散列沖突解決方法為開放定址法砰奕，不同于STL中的開鏈法。python采用的開放定址法在發(fā)生散列沖突時提鸟，會根據(jù)一個沖突探測函數(shù)計算下一個探測的位置军援，直到找到一個不沖突的位置。而在刪除元素的時候称勋，并不會直接刪除胸哥，而是設(shè)置一個dummy標(biāo)記，這樣可以保證在沖突探測的時候不出錯赡鲜，此外這個dummy標(biāo)記的元素下次插入新元素時可以被再次利用空厌。
字典中的一個鍵值對稱為一個entry，字典由PyDictEntry的數(shù)組構(gòu)成银酬。定義如下：
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三個狀態(tài)。初始為unused狀態(tài)揩瞪，me_key == NULL, me_value == NULL赋朦。而如果是active狀態(tài)，則me_key != NULL, me_key != dummy, me_value != NULL,如果是dummy狀態(tài)，則me_key == dummy, me_value == NULL.三個狀態(tài)的轉(zhuǎn)換則是：執(zhí)行插入操作則由unused或者dummy狀態(tài)變成active狀態(tài)宠哄，執(zhí)行刪除操作則從active狀態(tài)變成dummy狀態(tài)壹将。
PyDictObject定義如上面所示，其中ma_fill是元素總數(shù)目毛嫉，包括active和dummy狀態(tài)的鍵值對诽俯。而ma_used是active鍵值對數(shù)目，ma_mask用來定位元素在數(shù)組中的索引承粤，大小為數(shù)組長度減一暴区。如果數(shù)組ma_table為8，則ma_mask值為7.注意密任，這里還有個ma_smalltable颜启，大小初始為8,初始化時，字典的ma_table會指向ma_smalltable浪讳，當(dāng)裝載率大于等于2/3時缰盏，字典擴容。(即ma_fill / (ma_mask + 1)) >=2/3)淹遵，會將ma_table指向新分配的空間口猜，并搬移鍵值對到新的table中。
PyDictObject也采用了緩沖池機制透揣，其原理類似PyListObject济炎，這里不再贅述。需要額外提到的一點是字典中的元素搜索機制辐真，這里說下常用的lookdict_string函數(shù)须尚，其針對的是字符串鍵的查找。查找流程如下：
a. 查找的時候會先根據(jù)字符串hash值獲取鍵值對索引侍咱，如果對應(yīng)的鍵值對entry為unused狀態(tài)耐床，則表示搜索失敗，如果freeslot不為NULL楔脯，則返回freeslot（freeslot指向dummy狀態(tài)的entry）撩轰，否則返回entry。
b. 如果entry為其他狀態(tài)昧廷，則檢查me_key引用是否相同堪嫂，相同則返回該entry.
c. 如果me_key引用不同，則檢查me_key值是否相同(即比較hash值以及me_key的值)木柬，如果相同皆串，則返回entry堵第，否則繼續(xù)下一輪查詢肛走。
python中沖突探測函數(shù)如下，其中j為當(dāng)前的索引氯檐，perturb初始化為me_key的hash值，通過不斷調(diào)整j和perturb值寂玲，會不斷探測ma_table數(shù)組中的元素。由于perturb值是不斷減小的梗摇，所以最終會退化為j = 5 * j + 1拓哟，假定元素數(shù)為8，初始j = 0伶授， 使用退化后的探測函數(shù)探測到的索引依次是 0, 1, 6, 7, 4, 5, 2, 3, 0断序。這個探測函數(shù)順序有一定隨機性，這其實是通過一個線性同余方程來獲取2**i范圍內(nèi)的偽隨機數(shù)作為索引糜烹，比線性探測函數(shù)如f(x) = x + 1效果要好一些违诗。其中2**i是哈希表大小。至于為什么 j = (5*j) + 1; j % 2**i;這樣能夠得到0...2**i-1范圍內(nèi)的數(shù)字后再從頭開始循環(huán)疮蹦，證明方法暫時沒有找到诸迟，不過簡單驗證確實是沒有問題的。
j = (5*j) + 1 + perturb; // perturb初始值為鍵的hash值
perturb >>= PERTURB_SHIFT; // PERTURB_SHIFT=5愕乎，據(jù)說效果比較好
use j % 2**i as the next table index;
根據(jù)這個沖突探測算法阵苇，可以看到字典中插入鍵值對時的沖突探測和解決流程。具體例子參見http://www.laurentluce.com/posts/python-dictionary-implementation/
