|
世界上哪来那么多一见如故，不过是因为我喜欢你，所以眼里都是你。 本篇文章来聊一聊字典的缓存池，我们知道字典有一个 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 也有相应的缓存池，毕竟它负责存储具体的键值对。 那么下面我们就来研究一下这两者的缓存池。 字典的缓存池和列表的缓存池高度相似，都是采用数组实现的，并且容量也是 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 也有自己的缓存池，同样基于数组实现，大小是 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 的缓存池和列表同样是高度相似的，只不过它想要被缓存，除了缓存池有剩余空间之外，还需要满足两个额外的条件。 以上是 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 的集合。
|
