深入了解 Python 虚拟机：字典（dict）的优化

在前面的文章傍边咱们评论的是 python3 傍边前期的内嵌数据结构字典的完成，在本篇文章傍边主要介绍在后续关于字典的内存优化。

字典优化

在前面的文章傍边咱们介绍的字典的数据结构主要如下所示：

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 字节的内存空间，在 cpython 傍边的负载因子是 23\frac{2}{3}32​ 。而一个 entry 的大小是 24 个字节，假如 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 ，即一个元素值占一个字节。
• 当哈希表长度小于 0xffff 时，dk_indices 的数据类型为 int16_t ，即一个元素值占 2 一个字节。
• 当哈希表长度小于 0xffffffff 时，dk_indices 的数据类型为 int32_t ，即一个元素值占 4 个字节。
• 当哈希表长度大于 0xffffffff 时，dk_indices 的数据类型为 int64_t ，即一个元素值占 8 个字节。

与这个相关的代码如下所示：

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

现在来剖析一下相关的内存运用情况：

从上面的表格咱们可以看到哈希表的长度越大咱们节省的内存就越大，优化的作用就越明显。

总结

在本篇文章傍边主要介绍了在 python3 傍边关于字典的优化操作，主要是通过一个内存占用量比较小的数组去保存键值对在实在保存键值对傍边的下标完成的，这个办法关于节省内存的作用是十分明显的。

本篇文章是深入了解 python 虚拟机系列文章之一，文章地址：github.com/Chang-LeHun…

更多精彩内容合集可拜访项目：github.com/Chang-LeHun…

关注大众号：一无是处的研究僧，了解更多计算机（Java、Python、计算机体系基础、算法与数据结构）知识。