Python源碼剖析[13] —— 字典對象PyDictObject(2)

[絕對原創 轉載請注明出處]

Python源碼剖析

——字典對象PyDictObject(2)

本文作者 : Robert Chen ([email protected])

3         PyDictObject的建立和維護

3.1.1    PyDictObject對象建立

[dictobject.c]

typedef

PyDictEntry dictentry;

typedef

PyDictObject dictobject;

#define INIT_NONZERO_DICT_SLOTS(mp) do {                /

    (mp)->ma_table = (mp)->ma_smalltable;               /

    (mp)->ma_mask = PyDict_MINSIZE - 1;             /

} while

(0)

#define EMPTY_TO_MINSIZE(mp) do {                   /

    memset((mp)->ma_smalltable, 0,

sizeof

((mp)->ma_smalltable));    /

    (mp)->ma_used = (mp)->ma_fill = 0;              /

    INIT_NONZERO_DICT_SLOTS(mp);                    /

} while

(0)

PyObject* PyDict_New(

void

)

{ register

dictobject *mp;

if

(dummy == NULL)

{

        dummy = PyString_FromString("<dummy key>");

if

(dummy == NULL)

return

NULL;

} if

(num_free_dicts)

{

        …… //使用緩沖池

} else {

        mp = PyObject_GC_New(dictobject, &PyDict_Type);

if

(mp == NULL)

return

NULL;

        EMPTY_TO_MINSIZE(mp);

}

    mp->ma_lookup = lookdict_string;

    _PyObject_GC_TRACK(mp);

return

(PyObject *)mp;

}

值得注意的是，在第一次調用PyDict_New時，會建立在前面提到的那個dummy對象。顯而易見，dummy對象僅僅是一個PyStringObject對象，它作為一種訓示标志，表明該entry曾被使用過，且探測序列下一個位置的entry有可能是有效的，進而防止探測序列中斷。

從num_free_dicts可以看出，Python中dict的實作同樣使用了緩沖池。我們把将緩沖池的讨論放到後邊。

建立的過程首先申請合适的記憶體空間，然後在EMPTY_TO_MINSIZE中，會将ma_smalltable清零，同時設定ma_size和ma_fill，當然，在一個PyDictObject對象剛被建立的時候，這兩個變量都應該是0。然後會将ma_table指向ma_smalltable，并設定ma_mask，可以看到，ma_mask确實與一個PyDictObject對象中entry的數量有關。在建立過程的最後，将lookdict_string賦給了ma_lookup。正是ma_lookup指定了PyDictObject在entry集合中搜尋某一特定entry時要進行的動作，它是PyDictObject的搜尋政策，萬衆矚目。

3.1.2    元素搜尋

PyDictObject引入了兩個不同的搜尋政策，lookdict和lookdict_string。實際上，這兩個政策使用的是相同的算法，lookdict_string隻是lookdict的一種針對PyStringObject對象的特化形式。以PyStringObject對象作為PyDictObject對象中entry的鍵在Python中是如此地廣泛和重要，是以lookdict_string也就成為了PyDictObject建立時所預設采用的搜尋政策：

[dictobject.c]

static

dictentry* lookdict_string(dictobject *mp, PyObject *key,

register long

hash)

{ register int

i;

register unsigned int

perturb;

register

dictentry *freeslot;

register unsigned int

mask = mp->ma_mask;

    dictentry *ep0 = mp->ma_table;

register

dictentry *ep;

if

(!PyString_CheckExact(key))

{

        mp->ma_lookup = lookdict;

return

lookdict(mp, key, hash);

}

//[1]

    i = hash & mask;

ep = &ep0[i];

//[2]

//if NULL or interned

if

(ep->me_key == NULL || ep->me_key == key)

return

ep;

//[3]

if

(ep->me_key == dummy)

        freeslot = ep;

else {

//[4]

if

(ep->me_hash == hash && _PyString_Eq(ep->me_key, key))

{ return

ep;

}

        freeslot = NULL;

} for

(perturb = hash; ; perturb >>= PERTURB_SHIFT)

{

        i = (i << 2) + i + perturb + 1;

        ep = &ep0[i & mask];

if

(ep->me_key == NULL)

return

freeslot == NULL ? ep : freeslot;

if

(ep->me_key == key

            || (ep->me_hash == hash

                && ep->me_key != dummy

            && _PyString_Eq(ep->me_key, key)))

return

ep;

if

(ep->me_key == dummy && freeslot == NULL)

            freeslot = ep;

} }

其中的[1]，[2]，[3]，[4]标注出了搜尋過程中的關鍵步驟，這些步驟會在後面講述PyDictObject對象的一般搜尋政策時詳細讨論。

lookdict_string并不是PyDictObject中最一般的搜尋政策，它是一種有條件限制的搜尋政策。lookdict_string背後有一個假設，即PyDictObject對象中每一個entry的key都是PyStringObject*。隻有在這種假設成立的情況下，lookdict_string才會被使用。可以看到，lookdict_string首先會檢查需要搜尋的key是否嚴格對應一個PyStringObject對象，隻有在檢查通過後，才會進行下面的動作；如果檢查不通過，那麼就會轉向PyDictObject中的通用搜尋政策lookdict：

[dictobject.c]

static

dictentry* lookdict(dictobject *mp, PyObject *key,

register long

hash)

{ register int

i;

register unsigned int

perturb;

register

dictentry *freeslot;

register unsigned int

mask = mp->ma_mask;

    dictentry *ep0 = mp->ma_table;

register

dictentry *ep;

register int

restore_error;

register int

checked_error;

register int

cmp;

    PyObject *err_type, *err_value, *err_tb;

    PyObject *startkey;

    //[1]

    i = hash & mask;

ep = &ep0[i];

//[2]

if

(ep->me_key == NULL || ep->me_key == key)

return

ep;

    //[3]

if

(ep->me_key == dummy)

        freeslot = ep;

else {

//[4]

if

(ep->me_hash == hash)

{

            startkey = ep->me_key;

            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);

if

(cmp < 0)

                PyErr_Clear();

if

(ep0 == mp->ma_table && ep->me_key == startkey)

{ if

(cmp > 0)

goto

Done;

} else {

                ep = lookdict(mp, key, hash);

goto

Done;

} }

        freeslot = NULL;

} 。。。。。。

Done:

return

ep;

}

PyDictObject中維護的entry的數量是有限的，比如100個或1000個。而傳入lookdict中的key的hash值卻不一定會在這個範圍内，是以這就要求lookdict将hash值映射到某個entry上去。Lookdict采取的政策非常簡單，直接将hash值與entry的數量做一個與操作，結果自然落在entry的數量之下。由于ma_mask會被用來進行大量的與操作，是以這個與entry數量相關的變量被命名為ma_mask，而不是ma_size。

我們注意到，lookdict永遠都不會傳回NULL，如果在PyDictObject中搜尋不到待查找的元素，同樣會傳回一個entry，這個entry的me_value為NULL。

在搜尋的過程中freeslot是一個重要的變量。如果在探測序列中的某個位置上，entry處于Dummy态，那麼如果在這個序列中搜尋不成功，就會傳回這個處于Dummy态的entry。我們知道，處于Dummy态的entry其me_value是為NULL的，是以這個傳回結果訓示了搜尋失敗；同時，傳回的entry也是一個可以立即被使用的entry，因為Dummy态的entry并沒有維護一個有效的（key，value）對。這個freeslot正是用來指向探測序列中第一個處于Dummy态的entry，如果搜尋失敗，freeslot就會挺身而出，提供一個能訓示失敗并立即可用的entry。當然，如果探測序列中并沒有Dummy态entry，搜尋失敗時，一定是在一個處于Unused态的entry上結束搜尋過程的，這時會傳回這個處于Unused态的entry，同樣是一個能訓示失敗且立即可用的entry。

下面是lookdict中進行第一次檢查時需要注意的動作：

[1]：根據hash值獲得entry的序号。

[2]：如果ep->me_key為NULL，且與key相同，搜尋失敗。

[3]：若目前entry處于Dummy态，設定freeslot。

[4]：檢查目前Active的entry中的key與待查找的key是否相同，如果相同，則立即傳回，搜尋成功。

在[4]中，需要注意那個PyObject_RichCompareBool，它的函數原形為：

int PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)

當(v op w)成立時，傳回1；當(v op w)不成立時，傳回0；如果在比較中發生錯誤，則傳回-1。

現在我們考察的是根據hash值獲得的第一個entry與待查找的元素的比較。實際上，由于對應于某一個散列值，幾乎都有一個探測序列與之對應，是以我們現在隻是考察了探測序列中第一個位置的entry。萬裡長征僅僅邁出了第一步。

如果第一個entry與待查找的key不比對，那麼很自然地，lookdict會沿着探測序列，順藤摸瓜，依次比較探測序列上的entry與待查找的key：

[dictobject.c]

static

dictentry* lookdict(dictobject *mp, PyObject *key,

register long

hash)

{ register int

i;

register unsigned int

perturb;

register

dictentry *freeslot;

register unsigned int

mask = mp->ma_mask;

    dictentry *ep0 = mp->ma_table;

register

dictentry *ep;

register int

restore_error;

register int

checked_error;

register int

cmp;

    PyObject *err_type, *err_value, *err_tb;

PyObject *startkey;

。。。。。。 for

(perturb = hash; ; perturb >>= PERTURB_SHIFT)

{

//[5]

        i = (i << 2) + i + perturb + 1;

        ep = &ep0[i & mask];

        //[6]

if

(ep->me_key == NULL)

{ if

(freeslot != NULL)

                ep = freeslot;

break

;

} if

(ep->me_key == key)//[7]

break

;

if

(ep->me_hash == hash && ep->me_key != dummy)

{

            startkey = ep->me_key;

            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);

if

(cmp < 0)

                PyErr_Clear();

if

(ep0 == mp->ma_table && ep->me_key == startkey)

{ if

(cmp > 0)

break

;

} else {

                ep = lookdict(mp, key, hash);

break

;

} }

 //[8]

else if

(ep->me_key == dummy && freeslot == NULL)

            freeslot = ep;

}

Done:

return

ep;

}

[5]：獲得探測序列中的下一個待探測的entry。

[6]：ep到達一個Unused态entry，表明搜尋結束。這是如果freeslot不為空，則傳回freeslot所指entry。

[7]：entry與待查找的key比對，搜尋成功。

[8]：在探測序列中發現Dummy态entry，設定freeslot。

到這裡，我們已經清晰地了解了PyDictObject中的搜尋政策。再回過頭去看看那個lookdict_string，可以很清晰地看到，lookdict_string實際上就是一個lookdict對于PyStringDict對象的優化版本。在這裡展示的lookdict代碼經過了删節，實際上，在lookdict中有許多捕捉錯誤并處理錯誤的代碼，因為lookdict面對的是PyObject*，是以會出現很多意外情況。而在lookdict_string中，完全沒有了這些處理錯誤的代碼。而另一方面，在lookdict中，使用的是非常通用的PyObject_RichCompareBool，而lookdict_string使用的是_PyString_Eq，比要簡單很多，這些因素使得lookdict_string的搜尋效率要比lookdict高很多。

此外，Python自身也大量使用了PyDictObject對象，用來維護一個作用域中變量名和變量值之間的對應關系，或是用來在為函數傳遞參數時維護參數名與參數值的對應關系。這些對象幾乎都是用PyStringObject對象作為entry中的key，是以lookdict_string的意義就顯得非常重要了，它對Python整體的運作效率都有着重要的影響。

3.1.3    插入與删除

PyDictObject對象中元素的插入動作建立在搜尋的基礎之上：

[dictobject.c]

static void

insertdict(

register

dictobject *mp, PyObject *key,

long

hash, PyObject *value)

{

    PyObject *old_value;

register

dictentry *ep;

ep = mp->ma_lookup(mp, key, hash);

//[1]

if

(ep->me_value != NULL)

{

        old_value = ep->me_value;

        ep->me_value = value;

        Py_DECREF(old_value);

        Py_DECREF(key);

}

//[2]

else { if

(ep->me_key == NULL)

            mp->ma_fill++;

else

            Py_DECREF(ep->me_key);

        ep->me_key = key;

        ep->me_hash = hash;

        ep->me_value = value;

        mp->ma_used++;

} }

前面我們提到了，搜尋操作在成功時，傳回相應的處于Active态的entry，而在搜尋失敗時會傳回兩種不同的結果：一是處于Unused态的entry；二是處于Dummy态的entry。那麼插入操作對應不同的entry，所需要進行的動作顯然也是不一樣的。對于Active的entry，隻需要簡單地替換me_value值就可以了；而對于Unused或Dummy的entry，則需要完整地設定me_key，me_hash和me_value。

在insertdict中，正是根據搜尋的結果采取了不同的動作：

[1] ：搜尋成功，傳回處于Active的entry，直接替換me_value。

[2] ：搜尋失敗，傳回Unused或Dummy的entry，完整設定me_key，me_hash和me_value。

在Python中，對PyDictObject中的元素進行插入或設定有兩種方式：

[python code]

d = {}

d[1] = 1

d[1] = 2

第二行Python代碼是在PyDictObject對象中沒有這個entry的情況下插入元素，第三行是在PyDictObject對象中已經有這個entry的情況下重新設定元素。可以看到，insertdict完全可以适應這兩種情況，在insertdict中，[2]處代碼處理第二行Python代碼，[1]處代碼處理第三行Python代碼。實際上，這兩行Python代碼也确實都調用了insertdict。

當這兩行設定PyDictObject對象元素的Python代碼被執行時，并不是直接就調用insertdict，因為觀察代碼可以看到，insertdict需要一個hash值作為調用參數，那麼這個hash值在什麼地方獲得的呢？實際上，在調用insertdict之前，還會調用PyDict_SetItem：

[dictobject.c]

int

PyDict_SetItem(

register

PyObject *op, PyObject *key, PyObject *value)

{ register

dictobject *mp;

register long

hash;

register int

n_used;

mp = (dictobject *)op;

//計算hash值

if

(PyString_CheckExact(key))

{

        hash = ((PyStringObject *)key)->ob_shash;

if

(hash == -1)

            hash = PyObject_Hash(key);

} else {

        hash = PyObject_Hash(key);

if

(hash == -1)

return

-1;

}

    n_used = mp->ma_used;

    Py_INCREF(value);

    Py_INCREF(key);

    insertdict(mp, key, hash, value);

if

(!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))

return

0;

return

dictresize(mp, mp->ma_used*(mp->ma_used>50000 ? 2 : 4));

}

在PyDict_SetItem中，會首先獲得key的hash值，在上面的例子中，也就是一個PyIntObject對象1的hash值。

然後再調用insertdict進行元素的插入或設定。

PyDict_SetItem在插入或設定元素的動作結束之後，并不會草草傳回了事。接下來，它會檢查是否需要改變PyDictObject内部ma_table所值的記憶體區域的大小，在以後的叙述中，我們将這塊記憶體稱為“table”。那麼什麼時候需要改變table的大小呢。在前面我們說過，如果table的裝載率大于2/3時，後續的插入動作遭遇到沖突的可能性會非常大。是以裝載率是否大于或等于2/3就是判斷是否需要改變table大小的準則。在PyDict_SetItem中，有如下的代碼：

if

(!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))

return

0;

經過轉換，實際上可以得到：

(mp->ma_fill)/(mp->ma_mask+1) >= 2/3

這個等式左邊的表達式正是裝載率。

然而裝載率隻是判定是否需要改變table大小的一個标準，還有另一個标準是在insertdict的過程中，是否使用了一個處于Unused态的entry。前面我們說過，在搜尋過程失敗并且探測序列中沒有Dummy态的entry時，就會傳回一個Unused态的entry，insertdict會對這個entry進行填充。隻有當這種情況發生并且裝載率超标時，才會進行改變table大小的動作。而判斷在insertdict的過程中是否填充了Unused态的entry，是通過

mp->ma_used > n_used

來判斷的，其中的n_used就是進行insertdict操作之前的mp->ma_used。通過觀察mp->ma_used是否改變，就可以知道是否有Unused态的entry被填充。

在改變table時，并不一定是增加table的大小，同樣也可能是減小table的大小。更改table的大小時，新的table的空間為：

mp->ma_used*(mp->ma_used>50000 ? 2 : 4)

如果一個PyDictObject對象的table中隻有幾個entry處于Active态，而大多數entry都處于Dummy态，那麼改變table大小的結果顯然就是減小了table的空間大小。

在确定新的table的大小時，通常選用的政策是時新的table中entry的數量是現在table中Active态entry數量的4倍，選用4倍是為了使table中處于Active态的entry的分布更加稀疏，減少插入元素時的沖突機率。當然，這是以記憶體空間為代價的。由于機器的記憶體總是有限的，Python總不能沒心沒肺地在任何時候都要求4倍空間，這樣搞，别的程式會有意見的：）是以當table中Active态的entry數量非常巨大時，Python隻會要求2倍的空間，這次又是以執行速度來交換記憶體空間。Python2.4.1将這個“非常巨大”的标準劃定在50000。如此一來，上帝的歸上帝，撒旦的歸撒旦，萬事大吉 ：）

至于具體的改變table大小的重任，則交到了dictresize一人的肩上：

[dictobject.c]

static int

dictresize(dictobject *mp,

int

minused)

{ int

newsize;

    dictentry *oldtable, *newtable, *ep;

int

i;

int

is_oldtable_malloced;

    dictentry small_copy[PyDict_MINSIZE];

//[1]

for

(newsize = PyDict_MINSIZE; newsize <= minused && newsize > 0; newsize <<= 1)

        ;

    oldtable = mp->ma_table;

    assert(oldtable != NULL);

    is_oldtable_malloced = oldtable != mp->ma_smalltable;

    //[2]

if

(newsize == PyDict_MINSIZE)

{

        newtable = mp->ma_smalltable;

if

(newtable == oldtable)

{ if

(mp->ma_fill == mp->ma_used)

{

//沒有任何Dummy态entry,直接傳回

return

0;

}

            //将oldtable拷貝，進行備份

            assert(mp->ma_fill > mp->ma_used);

            memcpy(small_copy, oldtable,

sizeof

(small_copy));

            oldtable = small_copy;

} } else {

        newtable = PyMem_NEW(dictentry, newsize);

}

    //[3]

    assert(newtable != oldtable);

    mp->ma_table = newtable;

    mp->ma_mask = newsize - 1;

    memset(newtable, 0,

sizeof

(dictentry) * newsize);

    mp->ma_used = 0;

    i = mp->ma_fill;

    mp->ma_fill = 0;

    //[4]

for

(ep = oldtable; i > 0; ep++)

{ if

(ep->me_value != NULL)

{

            --i;

            insertdict(mp, ep->me_key, ep->me_hash, ep->me_value);

} else if

(ep->me_key != NULL)

{

            --i;

            assert(ep->me_key == dummy);

            Py_DECREF(ep->me_key);

} } if

(is_oldtable_malloced)

        PyMem_DEL(oldtable);

return

0;

}

[1] ：dictresize首先會确定新的table的大小，很顯然，這個大小一定要大于傳入的參數minused，這也是在原來的table中處于Active态的entry的數量。dictresize從8開始，以指數方式增加大小，直到超過了minused為止。是以實際上新的table的大小在大多數情況下至少是原來table中Active态entry數量的4倍。

[2] ：如果在[1]中獲得的新的table大小為8，則不需要在堆上配置設定空間，直接使用ma_smalltable就可以了；否則，則需要在堆上配置設定空間。

[3] ：對新的table進行初始化，并調整原來PyDictObject對象中用于維護table使用情況的變量。

[4] ：對原來table中的非Unused态entry進行處理。對于Active态entry，顯然需要将其插入到新的table中，這個動作由前面考察過的insertdict完成；而對于Dummy态的entry，則略過，不做任何處理，因為我們知道Dummy态entry存在的唯一理由就是為了不使搜尋時的探測序列中斷。現在所有Active态的entry都重新依次插入新的table中，它們會形成一條新的探測序列，不再需要這些Dummy态的entry了。

現在，利用我們對PyDictObject的認識，想象一下從table中删除一個元素應該怎樣操作呢？

[dictobject.c]

int

PyDict_DelItem(PyObject *op, PyObject *key)

{ register

dictobject *mp;

register long

hash;

register

dictentry *ep;

PyObject *old_value, *old_key;

//獲得hash值

if

(!PyString_CheckExact(key) ||

        (hash = ((PyStringObject *) key)->ob_shash) == -1)

{

        hash = PyObject_Hash(key);

if

(hash == -1)

return

-1;

}

//搜尋entry

    mp = (dictobject *)op;

    ep = (mp->ma_lookup)(mp, key, hash);

//删除entry所維護的元素

    old_key = ep->me_key;

    Py_INCREF(dummy);

    ep->me_key = dummy;

    old_value = ep->me_value;

    ep->me_value = NULL;

    mp->ma_used--;

    Py_DECREF(old_value);

    Py_DECREF(old_key);

return

0;

}

流程非常清晰，先計算hash值，然後搜尋相應的entry，最後删除entry中維護的元素，并将entry從Active态變換為Dummy态，同時還将調整PyDictObject對象中維護table使用情況的變量。

下面我們用一個簡單的例子來動态地展示對PyDictObject中table的維護過程，需要提醒的是，這裡采用的散列函數和探測函數都與Python中PyDictObject實際采用的政策不同，這裡隻是想要從觀念上展示對table的維護過程。在下面的圖中，藍色代表Unused态entry，綠色為Active态，黃色為Dummy态。

假如table中有10個entry，散列函數為HASH(x) = x mod 10，沖突解決方案采用線性探測，且探測函數為x = x + 1。假設向table中依次加入了以下元素對：（4，4），（14，14），（24，24），（34，34），則加入元素後的entry為：

現在删除元素對（14，14），然後向table中插入新的元素對（104，104）。則在搜尋的過程中，由于在原來維護14的entry#4處于現在Dummy态，是以freeslots會指向這個可用的entry：

搜尋完成後，填充freeslot所指向的entry：

然後，再向table中插入元素對（14，14），這時由于探測序列上已經沒有Dummy态entry了，是以最後傳回的ep會指向一個處于Unused态的entry：

最後插入元素對（14，14），結果為：