关于python:深入理解-Python-虚拟机字典dict的优化

深刻了解 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 当中的负载因子是 $\frac{2}{3}$。而一个 entry 的大小是 24 个字节，如果 dk_entries 的长度是 1024 的话，那么大略有 1024 / 3 * 24 = 8K 的内存空间是节约的。为了解决这个问题，在新版的 cpython 当中采取了一个策略用于缩小内存的应用。具体的设计如下图所示：

在新的字典当中 cpython 对于 dk_entries 来说如果失常的哈希表的长度为 8 的话，因为负载因子是 $\frac{2}{3}$ 真正给 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 虚拟机系列文章之一，文章地址：https://github.com/Chang-LeHung/dive-into-cpython

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHung/CSCore

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。