47. 身虽死，道未消，解密字典的缓存池

楔子

本篇文章来聊一聊字典的缓存池，我们知道字典有一个 ma_keys 字段和一个 ma_values 字段。当哈希表为分离表时，键由 ma_keys 维护，值由 ma_values 维护；当哈希表为结合表时，键和值均由 ma_keys 维护。

那么当我们销毁一个 PyDictObject 时，也肯定要先释放 ma_keys 和 ma_values。

如果是分离表，会将每个 value 的引用计数减 1，然后释放 ma_values；再将每个 key 的引用计数减 1，然后释放 ma_keys。最后再释放 PyDictObject 本身。
如果是结合表，由于 key、value 都在 ma_keys 中，将每个 key、value 的引用计数减 1 之后，只需释放 ma_keys 即可。最后再释放 PyDictObject 本身。

整个过程还是很清晰的，只不过这里面遗漏了点什么东西，没错，就是缓存池。在介绍浮点数的时候，我们说不同的对象都有自己的缓存池，当然字典也不例外。并且除了 PyDictObject 之外，PyDictKeysObject 也有相应的缓存池，毕竟它负责存储具体的键值对。

那么下面我们就来研究一下这两者的缓存池。

PyDictKeysObject 缓存池

PyDictKeysObject 也有自己的缓存池，同样基于数组实现，大小是 80。

// Objects/dictobject.c

#define PyDict_MAXFREELIST 80
// PyDictObject 缓存池以及容量
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;
// PyDictKeysObject 缓存池以及容量
static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
static int numfreekeys = 0;

来看一下 PyDictKeysObject 的销毁过程：

// Objects/dictobject.c

static inline void
dictkeys_decref(PyDictKeysObject *dk)
{
    assert(dk->dk_refcnt > 0);
    _Py_DEC_REFTOTAL;
    // 分离表：多组 value 可以共享一组 key
    // 结合表：每组 value 独占一组 key
    // 因此要先将 dk_refcnt 减 1，如果结果为 0，那么才能释放 ma_keys
    if (--dk->dk_refcnt == 0) {
        free_keys_object(dk);
    }
}

static void
free_keys_object(PyDictKeysObject *keys)
{
    // 获取键值对数组
    PyDictKeyEntry *entries = DK_ENTRIES(keys);
    Py_ssize_t i, n;
    // 遍历 dk_entries，减少 key、value 的引用计数
    for (i = 0, n = keys->dk_nentries; i < n; i++) {
        Py_XDECREF(entries[i].me_key);
        // 如果是分离表，那么 me_value == NULL
        // 而当参数为 NULL 时，Py_XDECREF 不做任何处理
        Py_XDECREF(entries[i].me_value);
    }
    // 放入缓存池，除了要保证缓存池没满之外，还要保证 dk_size = 8
    // 也就是说，只有容量为 8 的哈希表的 PyDictKeysObject 才会被缓存
    if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
        keys_free_list[numfreekeys++] = keys;
        return;
    }
    // 如果条件不满足，释放 ma_keys，将内存交还给系统堆
    PyObject_FREE(keys);
}

所以 PyDictKeysObject 的缓存池和列表的缓存池同样是高度相似的，只不过它想要被缓存，除了保证缓存池有剩余空间之外，还要满足哈希表的容量等于 8，这个限制是出于对内存方面的考量。

以上是 ma_keys 的销毁过程，再来看看它的创建过程。

// Objects/dictobject.c

// 为 PyDictKeysObject 实例申请内存
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t es, usable;

    assert(size >= PyDict_MINSIZE);
    assert(IS_POWER_OF_2(size));
    
    // 获取键值对数组的长度
    usable = USABLE_FRACTION(size);
    // 计算哈希索引数组中每个元素的大小
    if (size <= 0xff) {
        es = 1;
    }
    else if (size <= 0xffff) {
        es = 2;
    }
#if SIZEOF_VOID_P > 4
    else if (size <= 0xffffffff) {
        es = 4;
    }
#endif
    else {
        es = sizeof(Py_ssize_t);
    }
    // 如果容量等于 8，并且缓存池有可用元素，那么从缓存池中获取
    if (size == PyDict_MINSIZE && numfreekeys > 0) {
        dk = keys_free_list[--numfreekeys];
    }
    else {
        // 否则在堆区申请内存，而内存包含三部分
        // sizeof(PyDictKeysObject)：结构体 PyDictKeysObject 的大小
        // es * size：哈希索引数组的大小
        // sizeof(PyDictKeyEntry) * usable)：键值对数组的大小
        dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             + es * size
                             + sizeof(PyDictKeyEntry) * usable);
        if (dk == NULL) {
            PyErr_NoMemory();
            return NULL;
        }
    }
    _Py_INC_REFTOTAL;
    // 初始化字段
    dk->dk_refcnt = 1;
    dk->dk_size = size;
    dk->dk_usable = usable;
    dk->dk_lookup = lookdict_unicode_nodummy;
    dk->dk_nentries = 0;
    // 将哈希索引数组中的每个元素都设置成 -1
    memset(&dk->dk_indices[0], 0xff, es * size);
    // 将键值对数组中的每个元素（entry）的所有字段都设置成 0
    memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
    return dk;
}

非常简单，我们来验证一下。

from ctypes import *

class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]

class PyDictObject(PyObject):
    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", c_void_p),
                ("ma_values", c_void_p)]

d1 = {k: 1 for k in "komeiji satori"}
print(
    "d1.ma_keys:", PyDictObject.from_address(id(d1)).ma_keys
)
# 键值对个数超过了 8，哈希表的容量必然也超过了 8
# 那么当销毁 d1 的时候，d1.ma_keys 不会被缓存，而是会直接释放掉
del d1

d2 = {k: 1 for k in "abc"}
print(
    "d2.ma_keys:", PyDictObject.from_address(id(d2)).ma_keys
)
# 容量等于 8，所以 d2.ma_keys 会被缓存
del d2

d3 = {k: 1 for k in "komeiji koishi"}
print(
    "d3.ma_keys:", PyDictObject.from_address(id(d3)).ma_keys
)
# 尽管 d2 的 ma_keys 被缓存起来了，但是 d3 的 dk_size 大于 8
# 因此它不会从缓存池中获取，而是重新创建

d4 = {k: 1 for k in "abc"}
print(
    "d4.ma_keys:", PyDictObject.from_address(id(d4)).ma_keys
)
# d4 的 dk_size 等于 8，因此它会从缓存池中获取，从而复用被销毁的 d2.ma_keys
# 最终打印结果如下
"""
d1.ma_keys: 94324986272656
d2.ma_keys: 140165216613312
d3.ma_keys: 140165225069456
d4.ma_keys: 140165216613312
"""

从打印的结果来看，由于 d4.ma_keys 和 d2.ma_keys 是相同的，因此证实了我们的结论。不像列表和字典，它们是只要被销毁，就会放到缓存池里面，因为它们没有存储具体的数据，大小是固定的。但 PyDictKeysObject 不同，由于它存储了 entry，每个 entry 占 24 字节，如果内部的 entry 非常多，那么缓存起来会有额外的内存开销。因此 Python 的策略是，只有在哈希表容量等于 8 的时候，才会缓存。当然这三者在缓存池的实现上，是基本一致的。

不难看出，Python 在性能和内存使用方面都做了考量。但如果你追求更高的效率，那么也可以自己定制 Python 解释器，比如增大缓存池的容量等等，用更多的空间去换取时间。

小结

到此，字典相关的内容就全部介绍完了。和元组一样，字典也在我们看不到的地方被大量使用，比如对象的属性字典、名字空间等等。正因为解释器内部也在大量使用字典，所以字典是一个被高度优化的数据结构，不仅要保证搜索效率，还要减少内存使用。

下一篇文章，我们来介绍 Python 的集合。

欢迎大家关注我的公众号：古明地觉的编程教室。

如果觉得文章对你有所帮助，也可以请作者吃个馒头，Thanks♪(･ω･)ﾉ。

CPython3.8 源码探秘

楔子

PyDictObject 缓存池

PyDictKeysObject 缓存池

小结