Python中字典的缓存池

#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFEELIST];
static int numfree = 0;  //缓存池当前存储的元素个数

static void
dict_dealloc(PyDictObject *mp)
{  
    //获取ma_values指针
    PyObject **values = mp->ma_values;
    //获取ma_keys指针
    PyDictKeysObject *keys = mp->ma_keys;
    Py_ssize_t i, n;

    //因为要被销毁，所以让GC不再跟踪
    PyObject_GC_UnTrack(mp);
    //用于延迟释放
    Py_TRASHCAN_SAFE_BEGIN(mp)
        
    //调整引用计数
    //如果values不为NULL，说明是分离表    
    if (values != NULL) {
    //将指向的value、key的引用计数减1
    //然后释放ma_values和ma_keys
        if (values != empty_values) {
            for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
                Py_XDECREF(values[i]);
            }
            free_values(values);
        }
        DK_DECREF(keys);
    }
    //否则说明是结合表
    else if (keys != NULL) {
    //结合表的话，dk_refcnt一定是1
    //此时只需要释放ma_keys，因为键值对全部由它来维护
    //在DK_DECREF里面，会将每个key、value的引用计数减1
    //然后释放ma_keys
        assert(keys->dk_refcnt == 1);
        DK_DECREF(keys);
    }
    //将被销毁的对象放到缓存池当中
    if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
        free_list[numfree++] = mp;
    else
    //如果缓存池已满，则将释放内存
        Py_TYPE(mp)->tp_free((PyObject *)mp);
    Py_TRASHCAN_SAFE_END(mp)
}

static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
    //...
    if (numfree) {
        mp = free_list[--numfree];
    }
    //...
}

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): 1363335780736
id(d2): 1363335780800
id(d3): 1363335780800
id(d4): 1363335780736
"""

//PyDictObject的缓存池叫 free_list
//PyDictKeysObject的缓存池叫 keys_free_list
//两者不要搞混了
static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
static int numfreekeys = 0;  //缓存池当前存储的元素个数

static void
free_keys_object(PyDictKeysObject *keys)
{
    //将每个entry的me_key、me_value的引用计数减1
    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
    //将其放在缓存池当中
    //当缓存池未满、并且dk_size为8的时候被缓存
    if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
        keys_free_list[numfreekeys++] = keys;
        return;
    }
#endif
    PyObject_FREE(keys);
}

static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t es, usable;
    //...
    //创建 ma_keys，如果缓存池有可用对象、并且size等于8，
    //那么会从 keys_free_list 中获取
    if (size == PyDict_MINSIZE && numfreekeys > 0) {
        dk = keys_free_list[--numfreekeys];
    }
    else {
        // 否则malloc重新申请
        dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             + es * size
                             + sizeof(PyDictKeyEntry) * usable);
        }
    }
    //...
    return dk;
}

import ctypes
class PyObject(ctypes.Structure):
    _fields_ = [("ob_refcnt", ctypes.c_ssize_t),
                ("ob_type", ctypes.c_void_p)]
class PyDictObject(PyObject):
    _fields_ = [("ma_used", ctypes.c_ssize_t),
                ("ma_version_tag", ctypes.c_uint64),
                ("ma_keys", ctypes.c_void_p),
                ("ma_values", ctypes.c_void_p)]
d1 = {_: 1 for _ in "mnuvwxyz12345"}
print(
    PyDictObject.from_address(id(d1)).ma_keys
)  # 1962690551536
# 键值对个数超过了8，dk_size必然也超过了 8
# 那么当销毁d1的时候，d1.ma_keys不会被缓存
# 而是会直接释放掉
del d1
d2 = {_: 1 for _ in "a"}
print(
    PyDictObject.from_address(id(d2)).ma_keys
)  # 1962387670624

# d2 的 dk_size 显然等于 8
# 因此它的 ma_keys 是会被缓存的
del d2
d3 = {_: 1 for _ in "abcdefg"}
print(
    PyDictObject.from_address(id(d3)).ma_keys
)  # 1962699215808
# 尽管 d2 的 ma_keys 被缓存起来了
# 但是 d3 的 dk_size 大于 8
# 因此它不会从缓存池中获取，而是重新创建
# d4 的 dk_size 等于 8
# 因此它会获取 d2 被销毁的 ma_keys
d4 = {_: 1 for _ in "abc"}
print(
    PyDictObject.from_address(id(d4)).ma_keys
)  # 1962387670624