Python?虛擬機字典dict內(nèi)存優(yōu)化方法解析
引言
在前面的文章當(dāng)中我們討論的是 python3 當(dāng)中早期的內(nèi)嵌數(shù)據(jù)結(jié)構(gòu)字典的實現(xiàn),在本篇文章當(dāng)中主要介紹在后續(xù)對于字典的內(nèi)存優(yōu)化。
字典優(yōu)化
在前面的文章當(dāng)中我們介紹的字典的數(shù)據(jù)結(jié)構(gòu)主要如下所示:
typedef struct { PyObject_HEAD Py_ssize_t ma_used; PyDictKeysObject *ma_keys; PyObject **ma_values; } PyDictObject; struct _dictkeysobject { Py_ssize_t dk_refcnt; Py_ssize_t dk_size; dict_lookup_func dk_lookup; Py_ssize_t dk_usable; PyDictKeyEntry dk_entries[1]; }; typedef struct { /* Cached hash code of me_key. */ Py_hash_t me_hash; PyObject *me_key; PyObject *me_value; /* This field is only meaningful for combined tables */ } PyDictKeyEntry;
用圖示的方式表示如下圖所示:
所有的鍵值對都存儲在 dk_entries 數(shù)組當(dāng)中,比如對于 "Hello" "World" 這個鍵值對存儲過程如下所示,如果 "Hello" 的哈希值等于 8 ,那么計算出來對象在 dk_entries 數(shù)組當(dāng)中的下標(biāo)位 0 。
在前面的文章當(dāng)中我們談到了,在 cpython 當(dāng)中 dk_entries 數(shù)組當(dāng)中的一個對象占用 24 字節(jié)的內(nèi)存空間,在 cpython 當(dāng)中的負(fù)載因子是 23\frac{2}{3}32? 。而一個 entry 的大小是 24 個字節(jié),如果 dk_entries 的長度是 1024 的話,那么大概有 1024 / 3 * 24 = 8K 的內(nèi)存空間是浪費的。為了解決這個問題,在新版的 cpython 當(dāng)中采取了一個策略用于減少內(nèi)存的使用。具體的設(shè)計如下圖所示:
在新的字典當(dāng)中 cpython 對于 dk_entries 來說如果正常的哈希表的長度為 8 的話,因為負(fù)載因子是 23\frac{2}{3}32? 真正給 dk_entries 分配的長度是 5 = 8 / 3,那么現(xiàn)在有一個問題就是如何根據(jù)不同的哈希值進行對象的存儲。dk_indices 就是這個作用的,他的長度和真正的哈希表的長度是一樣的,dk_indices 是一個整型數(shù)組這個數(shù)組保存的是要保存對象在 dk_entries 當(dāng)中的下標(biāo),比如在上面的例子當(dāng)中 dk_indices[7] = 0,就表示哈希值求余數(shù)之后的值等于 7,0 表示對象在 dk_entries 當(dāng)中的下標(biāo)。
現(xiàn)在我們再插入一個數(shù)據(jù) "World" "Hello" 鍵值對,假設(shè) "World" 的哈希值等于 8,那么對哈希值求余數(shù)之后等于 0 ,那么 dk_indices[0] 就是保存對象在 dk_entries 數(shù)組當(dāng)中的下標(biāo)的,圖中對應(yīng)的下標(biāo)為 1 (因為 dk_entries 數(shù)組當(dāng)中的每個數(shù)據(jù)都要使用,因此直接遞增即可,下一個對象來的話就保存在 dk_entries 數(shù)組的第 3 個(下標(biāo)為 2)位置)。
內(nèi)存分析
首先我們先來分析一下數(shù)組 dk_indices 的數(shù)據(jù)類型,在 cpython 的內(nèi)部實現(xiàn)當(dāng)中并沒有一刀切的直接將這個數(shù)組當(dāng)中的數(shù)據(jù)類型設(shè)置成 int 類型。
dk_indices 數(shù)組主要有以下幾個類型:
- 當(dāng)哈希表長度小于 0xff 時,dk_indices 的數(shù)據(jù)類型為 int8_t ,即一個元素值占一個字節(jié)。
- 當(dāng)哈希表長度小于 0xffff 時,dk_indices 的數(shù)據(jù)類型為 int16_t ,即一個元素值占 2 一個字節(jié)。
- 當(dāng)哈希表長度小于 0xffffffff 時,dk_indices 的數(shù)據(jù)類型為 int32_t ,即一個元素值占 4 個字節(jié)。
- 當(dāng)哈希表長度大于 0xffffffff 時,dk_indices 的數(shù)據(jù)類型為 int64_t ,即一個元素值占 8 個字節(jié)。
與這個相關(guān)的代碼如下所示:
/* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */ static inline Py_ssize_t dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i) { Py_ssize_t s = DK_SIZE(keys); Py_ssize_t ix; if (s <= 0xff) { const int8_t *indices = (const int8_t*)(keys->dk_indices); ix = indices[i]; } else if (s <= 0xffff) { const int16_t *indices = (const int16_t*)(keys->dk_indices); ix = indices[i]; } #if SIZEOF_VOID_P > 4 else if (s > 0xffffffff) { const int64_t *indices = (const int64_t*)(keys->dk_indices); ix = indices[i]; } #endif else { const int32_t *indices = (const int32_t*)(keys->dk_indices); ix = indices[i]; } assert(ix >= DKIX_DUMMY); return ix; }
現(xiàn)在來分析一下相關(guān)的內(nèi)存使用情況:
哈希表長度 | 能夠保存的鍵值對數(shù)目 | 老版本 | 新版本 | 節(jié)約內(nèi)存量(字節(jié)) |
---|---|---|---|---|
256 | 256 * 2 / 3 = 170 | 24 * 256 = 6144 | 1 * 256 + 24 * 170 = 4336 | 1808 |
65536 | 65536 * 2 / 3 = 43690 | 24 * 65536 = 1572864 | 2 * 65536 + 24 * 43690 = 1179632 | 393232 |
從上面的表格我們可以看到哈希表的長度越大我們節(jié)約的內(nèi)存就越大,優(yōu)化的效果就越明顯。
總結(jié)
在本篇文章當(dāng)中主要介紹了在 python3 當(dāng)中對于字典的優(yōu)化操作,主要是通過一個內(nèi)存占用量比較小的數(shù)組去保存鍵值對在真實保存鍵值對當(dāng)中的下標(biāo)實現(xiàn)的,這個方法對于節(jié)約內(nèi)存的效果是非常明顯的。
本篇文章是深入理解 python 虛擬機系列文章之一,
更多精彩內(nèi)容合集可訪問項目:github.com/Chang-LeHun…
以上就是Python 虛擬機字典dict的優(yōu)化方法解析的詳細(xì)內(nèi)容,更多關(guān)于Python 虛擬機字典dict優(yōu)化的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
python使用requests實現(xiàn)發(fā)送帶文件請求功能
這篇文章主要介紹了python使用requests實現(xiàn)發(fā)送帶文件請求,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-12-12Python實現(xiàn)腳本轉(zhuǎn)換為命令行程序
使用Python中的scaffold和click庫,你可以將一個簡單的實用程序升級為一個成熟的命令行界面工具,本文就來帶你看看具體實現(xiàn)方法,感興趣的可以了解下2022-09-09Python操作SQLite數(shù)據(jù)庫過程解析
這篇文章主要介紹了Python操作SQLite數(shù)據(jù)庫過程解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09