本篇文章来聊一聊字典的缓存池，我们知道字典有一个 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 也有相应的缓存池，毕竟它负责存储具体的键值对。
那么下面我们就来研究一下这两者的缓存池。
PyDictObject 缓存池
字典的缓存池和列表的缓存池高度相似，都是采用数组实现的，并且容量也是 80 个。
// Include/internal/pycore_dict_state.h #define PyDict_MAXFREELIST 80 struct _Py_dict_state { // 全局计数器，用于设置字典的 ma_version_tag 字段 // 每次创建字典以及修改字典时，该计数器都会递增 // 当然这两个字段我们不用关注 uint64_t global_version; uint32_t next_keys_version; #if PyDict_MAXFREELIST > 0 PyDictObject *free_list[PyDict_MAXFREELIST]; PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST]; int numfree; int keys_numfree; #endif PyDict_WatchCallback watchers[DICT_MAX_WATCHERS]; };
我们看到 PyDictObject 和 PyDictKeysObject 的缓存池都位于该结构体中，容量都是 80。
下面看一下字典的销毁过程，因为放入缓存池这个动作，一定是在对象销毁时发生的。
// Objects/dictobject.c // 缓存池位于 _Py_dict_state 结构体实例当中 // 该实例在解释器启动之后会自动初始化好，并挂在进程状态对象上面 static struct _Py_dict_state * get_dict_state(PyInterpreterState *interp) { return &interp->dict_state; } // 减少 ma_keys->dk_refcnt static inline void dictkeys_decref(PyInterpreterState *interp, PyDictKeysObject *dk) { // 如果 dk_refcnt 等于 2 ** 32 - 1，说明这组 key 永远不会被释放 if (dk->dk_refcnt == _Py_IMMORTAL_REFCNT) { return; } assert(dk->dk_refcnt > 0); // 将 dk_refcnt 减 1 // 如果字典是结合表，那么 dk->dk_refcnt 减 1 之后一定为 0 // 如果字典是分离表，那么 dk->dk_refcnt 减 1 之后则不一定为 0 if (--dk->dk_refcnt == 0) { // 释放 ma_keys，该函数稍后再聊 free_keys_object(interp, dk); } } static void dict_dealloc(PyDictObject *mp) { PyInterpreterState *interp = _PyInterpreterState_GET(); // ... PyDictValues *values = mp->ma_values; PyDictKeysObject *keys = mp->ma_keys; Py_ssize_t i, n; // 因为要被销毁，所以让 GC 不再跟踪 PyObject_GC_UnTrack(mp); // 用于延迟释放 Py_TRASHCAN_BEGIN(mp, dict_dealloc) // 如果 values 不为 NULL，说明是分离表 if (values != NULL) { // 将每个 value 的引用计数减 1 for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) { Py_XDECREF(values->values[i]); } // 释放 ma_values free_values(values); // 将 ma_keys->dk_refcnt 减 1，至于是否会释放 ma_keys // 则看是否还有其它组的 value 使用它 dictkeys_decref(interp, keys); } // 否则说明是结合表 else if (keys != NULL) { // 结合表的话，dk_refcnt 一定等于 1，因为每组 value 都独占一组 key assert(keys->dk_refcnt == 1 || keys == Py_EMPTY_KEYS); // dk_refcnt 减 1 之后等于 0，内部会调用 free_keys_object // 在里面会先将每个 key 的引用计数减 1，然后再释放 ma_keys dictkeys_decref(interp, keys); } #if PyDict_MAXFREELIST > 0 // 获取 _Py_dict_state 结构体实例 struct _Py_dict_state *state = get_dict_state(interp); // 如果 numfree 没达到 80，那么放入缓存池 if (state->numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) { // PyDictObject 缓存池是一个数组，直接添加在数组的尾部即可 state->free_list[state->numfree++] = mp; OBJECT_STAT_INC(to_freelist); } else #endif { // 否则将空间交还给系统堆 Py_TYPE(mp)->tp_free((PyObject *)mp); } Py_TRASHCAN_END }
同理，当创建字典时，也会优先从缓存池里面获取。
// Objects/dictobject.c static PyObject * new_dict(PyInterpreterState *interp, PyDictKeysObject *keys, PyDictValues *values, Py_ssize_t used, int free_values_on_failure) { PyDictObject *mp; assert(keys != NULL); #if PyDict_MAXFREELIST > 0 struct _Py_dict_state *state = get_dict_state(interp); // 如果 state->numfree > 0，证明缓存池有可用元素 if (state->numfree) { // 从缓存池当中获取 mp = state->free_list[--state->numfree]; assert (mp != NULL); assert (Py_IS_TYPE(mp, &PyDict_Type)); OBJECT_STAT_INC(from_freelist); // 将引用计数设置为 1 _Py_NewReference((PyObject *)mp); } else #endif { // 否则从堆区申请内存 mp = PyObject_GC_New(PyDictObject, &PyDict_Type); // mp == NULL 表示申请失败 if (mp == NULL) { // 如果 ma_keys 申请好了，那么还要释放掉 dictkeys_decref(interp, keys); if (free_values_on_failure) { free_values(values); } return NULL; } } // 初始化字段，然后返回 (PyObject *)mp mp->ma_keys = keys; mp->ma_values = values; mp->ma_used = used; mp->ma_version_tag = DICT_NEXT_VERSION(interp); ASSERT_CONSISTENT(mp); return (PyObject *)mp; }
因此在缓存池的实现上，字典和列表有着很高的相似性。不仅都由数组实现，在销毁的时候也会放在数组的尾部，创建的时候也会从数组的尾部获取。当然啦，因为这么做符合数组的特性，如果销毁和创建都是在数组的头部操作，那么时间复杂度就从 O(1) 变成了 O(n)。
我们用 Python 来测试一下：
d1 = {k: 1 for k in "abcdef"} d2 = {k: 1 for k in "abcdef"} print("id(d1):", id(d1)) print("id(d2):", id(d2)) # 放到缓存池的尾部 del d1 del d2 # 缓存池：[d1, d2] # 从缓存池的尾部获取 # 显然 id(d3) 和上面的 id(d2) 是相等的 d3 = {k: 1 for k in "abcdefghijk"} # id(d4) 和上面的 id(d1) 是相等的 d4 = {k: 1 for k in "abcdefghijk"} print("id(d3):", id(d3)) print("id(d4):", id(d4)) """ id(d1): 140079181793600 id(d2): 140079181775488 id(d3): 140079181775488 id(d4): 140079181793600 """
输出结果和我们的预期是相符合的，以上就是 PyDictObject 的缓存池。
PyDictKeysObject 缓存池
PyDictKeysObject 也有自己的缓存池，同样基于数组实现，大小是 80，我们上面已经看到了。
来看一下它的销毁过程：
// Objects/dictobject.c static inline void dictkeys_decref(PyInterpreterState *interp, PyDictKeysObject *dk) { if (dk->dk_refcnt == _Py_IMMORTAL_REFCNT) { return; } assert(dk->dk_refcnt > 0); // 分离表：多组 value 可以共享一组 key // 结合表：每组 value 独占一组 key // 因此要先将 dk_refcnt 减 1，如果结果为 0，那么才能释放 ma_keys if (--dk->dk_refcnt == 0) { free_keys_object(interp, dk); } } static void free_keys_object(PyInterpreterState *interp, PyDictKeysObject *keys) { // Py_EMPTY_KEYS 是针对空字典而预定义好的，它不会被回收 // 因此这里 keys 一定不等于 Py_EMPTY_KEYS assert(keys != Py_EMPTY_KEYS); // 如果字典的 key 都是字符串 // 那么 keys->dk_entries 里面的 entry 由 PyDictUnicodeEntry 结构体表示 if (DK_IS_UNICODE(keys)) { PyDictUnicodeEntry *entries = DK_UNICODE_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); } } // key 的类型不做限制 // 那么 keys->dk_entries 里面的 entry 由 PyDictKeyEntry 结构体表示 else { 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); Py_XDECREF(entries[i].me_value); } } #if PyDict_MAXFREELIST > 0 struct _Py_dict_state *state = get_dict_state(interp); // 放入缓存池，但需要满足三个条件 /* 1) dk_log2_size == 3，即哈希表的容量等于 8 */ /* 2) 缓存池中已缓存的元素个数小于 80 */ /* 3) 所有的 key 必须都是字符串，换句话说，缓存的必须是 Unicode table 的 ma_keys Generic table 的 ma_keys 不会被缓存 */ if (DK_LOG_SIZE(keys) == PyDict_LOG_MINSIZE && state->keys_numfree < PyDict_MAXFREELIST && DK_IS_UNICODE(keys)) { state->keys_free_list[state->keys_numfree++] = keys; OBJECT_STAT_INC(to_freelist); return; } #endif // 如果条件不满足，释放 ma_keys，将内存交还给系统堆 PyObject_Free(keys); }
所以 PyDictKeysObject 的缓存池和列表同样是高度相似的，只不过它想要被缓存，除了缓存池有剩余空间之外，还需要满足两个额外的条件。
- 哈希表的容量等于 8，这个限制是出于对内存方面的考量。
- 必须是 Unicode table。
以上是 ma_keys 的销毁过程，再来看看它的创建过程。
// Objects/dictobject.c static PyDictKeysObject* new_keys_object(PyInterpreterState *interp, uint8_t log2_size, bool unicode) { // ... #if PyDict_MAXFREELIST > 0 struct _Py_dict_state *state = get_dict_state(interp); // 如果 log2_size == 3、unicode == 1、缓存池有可用元素 // 那么从缓存池当中获取 if (log2_size == PyDict_LOG_MINSIZE && unicode && state->keys_numfree > 0) { dk = state->keys_free_list[--state->keys_numfree]; OBJECT_STAT_INC(from_freelist); } else #endif // 否则从堆区申请内存 { dk = PyObject_Malloc(sizeof(PyDictKeysObject) + ((size_t)1 << log2_bytes) + entry_size * usable); if (dk == NULL) { PyErr_NoMemory(); return NULL; } } // ... 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 [1, 2, 3]} print( "d2.ma_keys:", PyDictObject.from_address(id(d2)).ma_keys ) # d2 的容量虽然等于 8，但不满足 key 全部是字符串 # 换句话说，字典使用的是 Generic table，不是 Unicode table # 因此它的 ma_keys 也不会被缓存 del d2 d3 = {k: 1 for k in ["a", "b", "c"]} print( "d3.ma_keys:", PyDictObject.from_address(id(d3)).ma_keys ) # 容量等于 8，key 都是字符串，所以 d3.ma_keys 会被缓存 del d3 d4 = {k: 1 for k in "komeiji koishi"} print( "d4.ma_keys:", PyDictObject.from_address(id(d4)).ma_keys ) # 尽管 d3 的 ma_keys 被缓存起来了，但是 d4 的容量大于 8 # 因此 d4.ma_keys 不会从缓存池中获取，而是重新创建 d5 = {k: 1 for k in "abc"} print( "d5.ma_keys:", PyDictObject.from_address(id(d5)).ma_keys ) # d5 满足 key 都是字符串，并且容量等于 8 # 因此 d5.ma_keys 会从缓存池中获取，并且会复用 d3.ma_keys 的地址 # 最终打印结果如下 """ d1.ma_keys: 140487120770976 d2.ma_keys: 140487123034448 d3.ma_keys: 140487120873136 d4.ma_keys: 140487123100656 d5.ma_keys: 140487120873136 """
从打印的结果来看，由于 d5.ma_keys 和 d3.ma_keys 是相同的，因此证实了我们的结论。不像列表和字典，它们是只要被销毁，就会放到缓存池里面，因为它们没有存储具体的数据，大小是固定的。
但是 PyDictKeysObject 不同，由于它存储了 entry，每个 entry 占 16 或 24 字节，如果内部的 entry 非常多，那么缓存起来会有额外的内存开销。因此 Python 的策略是，只有在哈希表容量等于 8 的时候，才会缓存。当然这三者在缓存池的实现上，是基本一致的。
小结
到此，字典相关的内容就全部介绍完了。和元组一样，字典也在我们看不到的地方被大量使用，比如对象的属性字典、变量命名空间等等。正因为解释器内部也在大量使用字典，所以字典是一个被高度优化的数据结构，不仅要保证搜索效率，还要减少内存使用。
下一篇文章，来介绍 Python 的集合。
