867571eb5710892ab786ea26a83a74a8
Python字典对象的实现

上周我们在探讨PyStringObject的优化的过程中接触到了Python中字典对象的实现,因此我们今天就接着这个话题深入探讨下其的具体实现。

熟悉高级编程语言的同学肯定对字典这个数据结构不陌生,比如C++中的unordered_map之类的。但是今天我们要从纯C的角度一起来剖析如何实现一个字典类的数据结构。

PyDictObject的结构

展开[dictobject.h],不难发现PyDictObject的结构如下所示:

typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  /* # Active + # Dummy */
    Py_ssize_t ma_used;  /* # Active */

    /* The table contains ma_mask + 1 slots, and that's a power of 2.
     * We store the mask instead of the size because the mask is more
     * frequently needed.
     */
    Py_ssize_t ma_mask;

    /* ma_table points to ma_smalltable for small tables, else to
     * additional malloc'ed memory.  ma_table is never NULL!  This rule
     * saves repeated runtime null-tests in the workhorse getitem and
     * setitem calls.
     */
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

其中,ma_fill, ma_used代表当前存入了多少个对象(这里的Dummy我们下文再谈)。而ma_table则是真正字典实现的内存所在。ma_lookup是一个利用函数指针进行C多态可以重定向的查询算法。

最后,必须要提的是,PyDictObject与生俱来就创建了一个PyDict_MINSIZE的数组,当字典里面容纳的个数比较小的时候,直接就使用了这块内存当作散列表。散列表中每个slot存储的都是PyDictEntry,就是一个简单的key-value结构,具体如下:

typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

而当数据量比较大的时候,ma_table会指向新申请的一块内存(当然ma_smalltable是不会被销毁的,因为字典的散列表结构ma_table会动态修改大小,仍然有可能缩小重新指向ma_smalltable。)

一定要注意,PyDictObjectPyObject_HEAD,不是变长对象哦。

PyDictObject的创建

[dictobject.h]来看,PyDictObject创建的API只有如下函数:

PyAPI_FUNC(PyObject *) PyDict_New(void);

其具体实现如下:

PyObject *
PyDict_New(void)
{
    register PyDictObject *mp;
    // 1. dummy节点
    if (dummy == NULL) { /* Auto-initialize dummy */
        dummy = PyString_FromString("<dummy key>");
        if (dummy == NULL)
            return NULL;
    }
    if (numfree) {
          // 2. 缓存池,复用
        mp = free_list[--numfree];
        assert (mp != NULL);
        assert (Py_TYPE(mp) == &PyDict_Type);
        _Py_NewReference((PyObject *)mp);
        if (mp->ma_fill) {
            EMPTY_TO_MINSIZE(mp);
        } else {
            /* At least set ma_table and ma_mask; these are wrong
               if an empty but presized dict is added to freelist */
            INIT_NONZERO_DICT_SLOTS(mp);
        }
        assert (mp->ma_used == 0);
        assert (mp->ma_table == mp->ma_smalltable);
        assert (mp->ma_mask == PyDict_MINSIZE - 1);
    } else {
         // 3. 创建
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL)
            return NULL;
        EMPTY_TO_MINSIZE(mp);

    }
    mp->ma_lookup = lookdict_string;

    return (PyObject *)mp;
}
  • 如果你认真读过我之前写的Python 的数组实现,你一定记得PyListObject的对象缓存,这里PyDictObject也使用了相应的技术,不再赘述。

  • EMPTY_TO_MINSIZE, INIT_NONZERO_DICT_SLOTS就是初始化值域而已。

    #define INIT_NONZERO_DICT_SLOTS(mp) do {                                \
        (mp)->ma_table = (mp)->ma_smalltable;                               \
        (mp)->ma_mask = PyDict_MINSIZE - 1;                                 \
        } while(0)
    
    #define EMPTY_TO_MINSIZE(mp) do {                                       \
        memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable));        \
        (mp)->ma_used = (mp)->ma_fill = 0;                                  \
        INIT_NONZERO_DICT_SLOTS(mp);                                        \
        } while(0)

key-value的插入

字典key-value插入的大致流程上周我们已经探讨,我们这次来完整回顾一下:

  1. 先是计算keyhash

    int
    PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
    {
        register long hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    assert(value);
    if (PyString_CheckExact(key)) {
        hash = ((PyStringObject *)key)-&gt;ob_shash;
        if (hash == -1)
            hash = PyObject_Hash(key);
    }
    else {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }
    return dict_set_item_by_hash_or_entry(op, key, hash, NULL, value);
    }

继续到真正的函数:

static int
insertdict_by_entry(register PyDictObject *mp, PyObject *key, long hash,
                    PyDictEntry *ep, PyObject *value)
{
    PyObject *old_value;

    MAINTAIN_TRACKING(mp, key, value);
    // 替换
    if (ep->me_value != NULL) {
        old_value = ep->me_value;
        ep->me_value = value;
        Py_DECREF(old_value); /* which **CAN** re-enter */
        Py_DECREF(key);
    }
    else {
          // 全新的
        if (ep->me_key == NULL)
            mp->ma_fill++;
top Created with Sketch.