Python?虛擬機字典dict內存優(yōu)化方法解析

更新時間：2023年03月26日 08:49:03 作者：一無是處的研究僧

這篇文章主要為大家介紹了Python?虛擬機字典dict內存優(yōu)化方法解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

引言

在前面的文章當中我們討論的是 python3 當中早期的內嵌數據結構字典的實現，在本篇文章當中主要介紹在后續(xù)對于字典的內存優(yōu)化。

字典優(yō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 數組當中，比如對于 "Hello" "World" 這個鍵值對存儲過程如下所示，如果 "Hello" 的哈希值等于 8 ，那么計算出來對象在 dk_entries 數組當中的下標位 0 。

在前面的文章當中我們談到了，在 cpython 當中 dk_entries 數組當中的一個對象占用 24 字節(jié)的內存空間，在 cpython 當中的負載因子是 23\frac{2}{3}32? 。而一個 entry 的大小是 24 個字節(jié)，如果 dk_entries 的長度是 1024 的話，那么大概有 1024 / 3 * 24 = 8K 的內存空間是浪費的。為了解決這個問題，在新版的 cpython 當中采取了一個策略用于減少內存的使用。具體的設計如下圖所示：

在新的字典當中 cpython 對于 dk_entries 來說如果正常的哈希表的長度為 8 的話，因為負載因子是 23\frac{2}{3}32? 真正給 dk_entries 分配的長度是 5 = 8 / 3，那么現在有一個問題就是如何根據不同的哈希值進行對象的存儲。dk_indices 就是這個作用的，他的長度和真正的哈希表的長度是一樣的，dk_indices 是一個整型數組這個數組保存的是要保存對象在 dk_entries 當中的下標，比如在上面的例子當中 dk_indices[7] = 0，就表示哈希值求余數之后的值等于 7，0 表示對象在 dk_entries 當中的下標。

現在我們再插入一個數據 "World" "Hello" 鍵值對，假設 "World" 的哈希值等于 8，那么對哈希值求余數之后等于 0 ，那么 dk_indices[0] 就是保存對象在 dk_entries 數組當中的下標的，圖中對應的下標為 1 （因為 dk_entries 數組當中的每個數據都要使用，因此直接遞增即可，下一個對象來的話就保存在 dk_entries 數組的第 3 個（下標為 2）位置）。

內存分析

首先我們先來分析一下數組 dk_indices 的數據類型，在 cpython 的內部實現當中并沒有一刀切的直接將這個數組當中的數據類型設置成 int 類型。

dk_indices 數組主要有以下幾個類型：

當哈希表長度小于 0xff 時，dk_indices 的數據類型為 int8_t ，即一個元素值占一個字節(jié)。
當哈希表長度小于 0xffff 時，dk_indices 的數據類型為 int16_t ，即一個元素值占 2 一個字節(jié)。
當哈希表長度小于 0xffffffff 時，dk_indices 的數據類型為 int32_t ，即一個元素值占 4 個字節(jié)。
當哈希表長度大于 0xffffffff 時，dk_indices 的數據類型為 int64_t ，即一個元素值占 8 個字節(jié)。

與這個相關的代碼如下所示：

/* 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;
}

現在來分析一下相關的內存使用情況：