字典的整理收納課(下)
在上個章節我們已經看到如何建立字典物件,不過隨著字典物件的 dk_indices
陣列越來越滿,發生碰撞的頻率也會越來越高,導致效能下降。所以當容量快不夠的時候,Python 就會自動幫我們增加容量,我們身為一般使用者完全不用擔心這些細節,但是,這是怎麼做到的?
可用空間太小跟系統討更多的記憶體來用,如果一口氣拿了過多的空間,碰撞機率雖然降低了,但同時可能也造成空間的浪費,所以「什麼時候」應該要再去拿更多記憶體空間以及「應該拿多少」,才能在性能跟記憶體空間之間取得平衡?這一章節我們就來看看 Python 是怎麼處理這些問題的。
字典的空間管理術
繼續新增元素
在上個章節我們看到如果是針對全新的字典物件,要加入第一顆元素的時候是呼叫 insert_to_emptydict()
函數,但如果要新增到一個不是空的字典物件裡, 也就是要在同一個字典裡加入第二顆物件的時候,它會呼叫 insertdict()
函數。這個函數的行數比較多,做的事也比較複雜,我們分段來看:
static int
insertdict(PyInterpreterState *interp, PyDictObject *mp,
PyObject *key, Py_hash_t hash, PyObject *value)
{
PyObject *old_value;
if (DK_IS_UNICODE(mp->ma_keys) && !PyUnicode_CheckExact(key)) {
if (insertion_resize(interp, mp, 0) < 0)
goto Fail;
assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
}
// ... 略 ...
}
DK_IS_UNICODE()
巨集透過比對這顆字典物件的 ma_keys
成員裡的 dk_kind
確認目前這顆字典物件是否使用了專門為 Unicode 字串做最佳化的狀態,如果是,但接下來要加入的 Key 不是卻 Unicode 字串,例如 hero[42] = "Kitty"
,Python 為了可以存放不同類型的 Key,會把原本對已經針對 Unicode 的 Key 最佳化的格式轉換為一般通用的格式,這種轉換本質上就是一個變更容量的操作,所以這裡呼叫了 insertion_resize()
進行容量變更。變更容量的細節晚點再討論,這裡我舉個例子:
import sys
fruits1 = {"apple": "蘋果", "banana": "香蕉"}
fruits2 = {"apple": "蘋果", "banana": "香蕉"}
print(sys.getsizeof(fruits1))
print(sys.getsizeof(fruits2))
fruits1["pineapple"] = "鳳梨"
fruits2[42] = "鳳梨"
print(sys.getsizeof(fruits1))
print(sys.getsizeof(fruits2))
在「為你自己學 Python」一書的字典章節有介紹過,在 Python 裡不是只有字串才能當 Key,只要是可雜湊物件都可以。這裡我分別用字串 "pineapple"
跟數字 42 當做 Key,結果會造成原本一樣的兩個字典變的不一樣大,在我電腦執行之後,會印出以下結果:
184
184
184
352
為什麼 fruits2
的大小會變大呢?因為 fruits2
加入了不是 Unicode 字串的 Key,所以 Python 會把 fruits2
的 dk_kind
從 Unicode 專用格式 DICT_KEYS_UNICODE
轉換為一般通用的格式 DICT_KEYS_GENERAL
,這個轉換會增加記憶體的使用量。也就是說,雖然 Python 的字典沒有規定只能用字串,但用字串當做 Key 的效能會是最好的。
再回來 insertdict()
函數繼續往下看:
static int
insertdict(PyInterpreterState *interp, PyDictObject *mp,
PyObject *key, Py_hash_t hash, PyObject *value)
{
// ... 略 ...
Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
// ... 略 ...
if (ix == DKIX_EMPTY) {
assert(old_value == NULL);
if (mp->ma_keys->dk_usable <= 0) {
if (insertion_resize(interp, mp, 1) < 0)
goto Fail;
}
// ... 略 ...
}
}
這裡再次發現 insertion_resize()
函數,當 ix
的值是 DKIX_EMPTY
時,代表這個 Key 是全新的,也就是要新增這個 Key,這時候就要檢查目前的字典物件是否還有可用的空間,這其實是這個函數裡主要變更容量的檢查點,如果字典裡的空間不夠用的話,就要呼叫 insertion_resize()
函數來增加容量。
這個 dk_usable <= 0
判斷看起來很簡單,但其實不是它帳面上看起來這麼單純...
要拿更多容量嗎?
dk_usable
是 PyDictKeysObject
結構裡的一個成員變數,從名字可能可以猜的出來在這個字典還可以使用的空格數量,但其實不是。如果真的是這樣,這裡判斷 dk_usable <= 0
的話才準備增加容量的話是不是有點太節省啦?前面才提到如果字典內的可用空間不足會因為容易碰撞而導致效能變差,所以等到 db_usable <= 0
才要求更多空間有點沒道理。其實 dk_usable
這個值不是它表面看起來這麼簡單。
先看一下上個章節介紹到的 PyDictKeysObject
結構:
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
uint8_t dk_log2_size;
uint8_t dk_log2_index_bytes;
uint8_t dk_kind;
uint32_t dk_version;
Py_ssize_t dk_usable;
Py_ssize_t dk_nentries;
char dk_indices[];
};
順便借用上個章節的例子:
dk_indices:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| | | 2 | 1 | | 3 | | |
+---+---+---+---+---+---+---+---+
來看一下目前這個 PyDictKeysObject
結構的成員變數:
dk_log2_size
這顆字典的大小是 23 = 8,就是可以容納 8 個元素的意思,所以這個欄位的值就是 23 的 3。dk_nentries
也是 3,就是目前這顆字典裡已經存了 3 個 Key,表示目前有 3 個 Entry 的意思。
dk_log2_index_bytes
比較特別一點,另外特別拿出來說明。在上個章節有講到 new_keys_object()
函數,是用來建立一個新的 PyDictKeysObject
結構的,這個函數裡有一段程式碼是這樣寫的:
static PyDictKeysObject*
new_keys_object(PyInterpreterState *interp, uint8_t log2_size, bool unicode)
{
// ... 略 ...
if (log2_size < 8) {
log2_bytes = log2_size;
}
else if (log2_size < 16) {
log2_bytes = log2_size + 1;
}
else {
log2_bytes = log2_size + 2;
}
// ... 略 ...
}