AdjWang

AdjWang

关注
发信
关注(28)粉丝(399)

细说 PEP 468: Preserving Keyword Argument Order

细说 PEP 468: Preserving Keyword Argument Order

Python 3.6.0 版本对字典做了优化，新的字典速度更快，占用内存更少，非常神奇。从网上找了资料来看，大部分都指向了 [Python-Dev] More compact dictionaries with faster iteration 这篇文章，里面概括性地介绍了旧字典和新字典的差别，以及优化的地方，很有创意。

然而我非常好奇这样的结构是怎么用C语言实现的，所以去看了源码。我分别找到 3.5.9 和 3.6.0 版本的 Python 字典源代码，对比了一下，发现 Python 里字典的实现到处都是神操作，令人振奋。于是，一个想法产生了，不如就从源码角度，细说一下 PEP 468 对字典的改进，也算是对 [Python-Dev] More compact dictionaries with faster iteration 的补充。

如果上来就对比 3.5.9 和 3.6.0 的代码差异，是没有办法把事情说清楚的，所以我还得多啰嗦一些，把字典数据结构先完整地分析一下，然后就可以愉快地对比差异了 : )

如无特殊说明，默认参考Python 3.6.0版本。

新特性

在 Python 的新特性变更记录页面，可以看到 Python 从 3.6 版本开始，支持有序字典，而且内存占用更少。

dict 数据结构简述

我本来想拿 Python 3.5.9 的结构来对比一下，不过后来想了想，没有必要。二者差异不大，不需要把对比搞得很麻烦，我直接介绍 Python 3.6.0 的字典结构，然后直接对比源码细节，就已经够清楚了。再参考 [Python-Dev] More compact dictionaries with faster iteration ，就更清晰了。

结构

涉及到字典对象的结构主要有3个：

  • PyDictObject (./Include/dictobject.h)
  • PyDictKeysObject (./Objects/dict-common.h) 就是头文件里面的 struct _dictkeysobject
  • PyDictKeyEntry (./Objects/dict-common.h)

细说 PEP 468: Preserving Keyword Argument Order-LMLPHP

下面依次说明一下各个数据的定义：

  • PyDictObject

    字典对象，Python里面所有字典，不管是我们自己用dict()创建的还是类的__dict__属性，都是它。

    • PyObject_HEAD

      Python里所有东西都是对象，而且这些对象都是无类型的，那么想想这两个问题：在C语言里，类型是固定的，而且没有运行时类型检查，那么怎么样实现动态调用呢？动态调用以后怎么识别类型呢？

      没错，就是"看脸"，假如每个对象都有一个这样的PyObject_HEAD，其中包含类型信息，那么就可以用指针动态调用，然后根据其中的类型信息动态识别类型了。

      再多说一句，一定要做好“类型检查”，

    • ma_used

      当前字典里的item数量。

    • ma_version_tag

      有一个64位无符号全局变量pydict_global_version，字典的创建和每次更改，都会给这个全局变量+1，然后不过为什么必须是 2 的整数次幂？我摘出来几行代码。

      #define DK_MASK(dk) (((dk)->dk_size)-1)
size_t mask = DK_MASK(k);
i = (size_t)hash & mask;	// 通过哈希值计算哈希表索引

      这就明白了，哈希值的数据类型是size_t，可能导致哈希表访问越界，所以要对哈希表长度取余数，为了用与操作加速取余数运算，把dk_size规定为 2 的整数次幂。

    • 。跟随 PEP 468 说明链接找到 [Python-Dev] More compact dictionaries with faster iteration ，里面描述的第一个entries数组对应 3.5.9 版本的dk_entries；后面的indices和entries对应 3.6.0 版本的dk_indices和dk_entries数组，跟上面的代码对上了。

      看完源码，对这个说明的理解就更加深刻了吧，嘿嘿 : )

      不过，到这里还没完，new_keys_object()函数只是创建了PyDictKeysObject对象，最终目标应该是PyDictObject，创建PyDictObject对象的函数是PyDict_New()

      /* Python 3.6.0 */
/* ./Objects/dictobject.c */
PyObject *
PyDict_New(void)
{
    PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
    if (keys == NULL)
        return NULL;
    return new_dict(keys, NULL);	// combined 模式下 values 是 NULL
}

      new_keys_object()看过了，接着看看new_dict()，仍然省略掉部分类型检查和异常检查代码。

      /* Python 3.6.0 */
/* ./Objects/dictobject.c */
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
    PyDictObject *mp;
    assert(keys != NULL);
    if (numfree) {
        // 缓存池
        mp = free_list[--numfree];
        ...
        _Py_NewReference((PyObject *)mp);
    }
    else {
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        ...
    }
    mp->ma_keys = keys;			// 传递 new_keys_object 函数生成的 PyDictKeysObject 对象
    mp->ma_values = values;		// combined 模式下 values 是 NULL
    mp->ma_used = 0;			// 初始化的字典没有元素
    mp->ma_version_tag = DICT_NEXT_VERSION();	// 版本号，参考上面数据结构里的说明
    assert(_PyDict_CheckConsistency(mp));
    return (PyObject *)mp;
}

      到这里，一个 dict 对象就算正式创建完成了，我们在 Python 里也可以开始愉快地玩耍了。不过注意，这里创建出来的字典是“combined”模式的。“splitted”模式的字典在“combined”模式基础上还初始化了ma_values，我这里就懒得详细介绍了。

      为什么有序

      通过前面分析的数据结构，我们知道，字典元素保存在dk_entries数组中。当一个数据结构有序，指的是它里面元素的顺序与插入顺序相同。元素插入哈希表的索引是哈希函数算出来的，应该是无序的，这就是之前的字典元素无序的原因。而 Python 3.6.0 引入了dk_indices数组，专门记录哈希表信息，那么元素插入的顺序信息就得以保留在dk_entries数组中。为了满足好奇心，下面分析一下插入函数。

      /* Python 3.6.0 */
/* ./Objects/dictobject.c */
/*
Internal routine to insert a new item into the table.
Used both by the internal resize routine and by the public insert routine.
Returns -1 if an error occurred, or 0 on success.
*/
static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyObject *old_value;
    PyObject **value_addr;
    PyDictKeyEntry *ep, *ep0;
    Py_ssize_t hashpos, ix;
	...
    ix = mp->ma_keys->dk_lookup(mp, key, hash, &value_addr, &hashpos);
    ...
    Py_INCREF(value);
    MAINTAIN_TRACKING(mp, key, value);
	...
	/* 插入新值 */
    if (ix == DKIX_EMPTY) {
        /* Insert into new slot. */
        /* dk_entries 数组填满的时候给字典扩容 */
        if (mp->ma_keys->dk_usable <= 0) {
            /* Need to resize. */
            if (insertion_resize(mp) < 0) {
                Py_DECREF(value);
                return -1;
            }
            find_empty_slot(mp, key, hash, &value_addr, &hashpos);
        }
        ep0 = DK_ENTRIES(mp->ma_keys);
        ep = &ep0[mp->ma_keys->dk_nentries];	// 每次插入位置在最后
        dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
        Py_INCREF(key);
        ep->me_key = key;
        ep->me_hash = hash;
        if (mp->ma_values) {
            assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
            mp->ma_values[mp->ma_keys->dk_nentries] = value;
        }
        else {
            ep->me_value = value;
        }
        mp->ma_used++;
        mp->ma_version_tag = DICT_NEXT_VERSION();
        mp->ma_keys->dk_usable--;
        mp->ma_keys->dk_nentries++;
        assert(mp->ma_keys->dk_usable >= 0);
        assert(_PyDict_CheckConsistency(mp));
        return 0;
    }

    assert(value_addr != NULL);
	/* 替换旧值 */
    old_value = *value_addr;
    if (old_value != NULL) {
        *value_addr = value;
        mp->ma_version_tag = DICT_NEXT_VERSION();
        assert(_PyDict_CheckConsistency(mp));

        Py_DECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
        return 0;
    }

    /* pending state */
    assert(_PyDict_HasSplitTable(mp));
    assert(ix == mp->ma_used);
    *value_addr = value;
    mp->ma_used++;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    assert(_PyDict_CheckConsistency(mp));
    return 0;
}

      在插入函数中，第一个重点关注对象应该是ix = mp->ma_keys->dk_lookup(mp, key, hash, &value_addr, &hashpos)这句代码。dk_lookup是一个函数指针，指向四大搜索函数的其中一个，这里有必要说明一下各参数和返回值：

      • 参数

        1. PyDictObject *mp (已知参数)

          字典对象，在该对象中查找。

        2. PyObject *key (已知参数)

          entry里的key，代表key对象的引用，用于第一次判定，如果引用相同就找到了；如果不同再判断hash

        3. Py_hash_t hash (已知参数)

          entry里的hash，用于第二次判定，如果哈希值相同就找到了；如果不同就代表没找到。

        4. PyObject ***value_addr (未知参数，用指针返回数据)

          如果找到元素，则value_addr返回对应的me_value的指针；如果没找到，*value_addr为NULL

        5. Py_ssize_t *hashpos (未知参数，用指针返回数据)

          hashpos返回元素在哈希表中的位置。

      • 返回值

        • Py_ssize_t ix

          返回元素在dk_entries数组中的索引。如果不是有效元素，ix可能是DKIX_EMPTY, DKIX_DUMMY, DKIX_ERROR中的一个，分别代表dk_entries数组中的 新空位，删除旧值留下的空位，错误。

      了解了各个参数的作用，就可以继续愉快地看代码了。然后就看到了这一句ep = &ep0[mp->ma_keys->dk_nentries]，根据它下面的代码可以知道，这个ep就是新元素插入的地方，代表一个PyDictKeyEntry对象指针，而mp->ma_keys->dk_nentries指向的位置，就是dk_entries数组的末尾。也就是说，每次的新元素插入字典，都会依次放到dk_entries数组里，保持了插入顺序。那么哈希函数计算出来的插入位置呢？答案就在dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries)函数里。

      /* Python 3.6.0 */
/* ./Objects/dictobject.c */
/* write to indices. */
static inline void
dk_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
{
    Py_ssize_t s = DK_SIZE(keys);

    assert(ix >= DKIX_DUMMY);

    if (s <= 0xff) {
        int8_t *indices = keys->dk_indices.as_1;
        assert(ix <= 0x7f);
        indices[i] = (char)ix;	// 填充 dk_indices 数组
    }
    else if (s <= 0xffff) {
        ...
    }
}

      可以看到，哈希函数计算出来的插入位置保存到了dk_indices数组里，而对应插入位置保存的信息就是这个元素在dk_entries数组里的索引。
      如果没看明白，就再回顾一下 [Python-Dev] More compact dictionaries with faster iteration 中的描述。

      是时候了，现在拿出 Python 3.5.9 的代码对比一下，只对比 Empty 状态的 slot 插入代码即可。

      /* Python 3.5.9 */
/* ./Objects/dictobject.c */
/*
Internal routine to insert a new item into the table.
Used both by the internal resize routine and by the public insert routine.
Returns -1 if an error occurred, or 0 on success.
*/
static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyObject *old_value;
    PyObject **value_addr;
    PyDictKeyEntry *ep;
    assert(key != dummy);

    Py_INCREF(key);
    Py_INCREF(value);
    ...
    ep = mp->ma_keys->dk_lookup(mp, key, hash, &value_addr);
    ...
    old_value = *value_addr;
    /* Active 状态 */
    if (old_value != NULL) {
        ...
    }
    else {
        /* Empty 状态 */
        if (ep->me_key == NULL) {
            if (mp->ma_keys->dk_usable <= 0) {
                /* Need to resize. */
                ...
            }
            mp->ma_used++;
            *value_addr = value;	// 直接向 dk_entries 数组插入元素
            mp->ma_keys->dk_usable--;
            assert(mp->ma_keys->dk_usable >= 0);
            ep->me_key = key;
            ep->me_hash = hash;
            assert(ep->me_key != NULL && ep->me_key != dummy);
        }
        /* Dummy 状态 */
        else {
            ...
        }
    }
    return 0;
    ...
}

      可以看到*value_addr = value这句代码填充了dk_entries，但是这里信息是不够的，value_addr来自搜索函数，于是我找到通用搜索函数lookdict，来看下它里面获取插入位置的关键代码。

      /* Python 3.5.9 */
/* ./Objects/dictobject.c */
static PyDictKeyEntry *
lookdict(PyDictObject *mp, PyObject *key,
         Py_hash_t hash, PyObject ***value_addr)
{
    ...
    mask = DK_MASK(mp->ma_keys);
    ep0 = &mp->ma_keys->dk_entries[0];
    i = (size_t)hash & mask;	// 靠哈希值找到插入位置
    ep = &ep0[i];	// 直接按照位置插入到 dk_entries 数组中
    if (ep->me_key == NULL || ep->me_key == key) {
        *value_addr = &ep->me_value;	// 用指针返回 me_value 作为插入地址
        return ep;
    }
    ...
}

      可以清晰地看到，哈希函数计算出来的位置是直接对应到dk_entries数组中的，元素也直接放进去，没有dk_indices数组。因为哈希值不是连续的，所以我们依次插入到dk_entries数组里的元素也就不连续了。
      如果又没看明白，就再回顾一下 [Python-Dev] More compact dictionaries with faster iteration 中的描述。

      为什么快

      迭代变快的原因源自dk_entries数组的密集化，迭代时遍历的数量少。Python 3.5.9 和 3.6.0 版本代码的写法差异不大，所以这里只摘取一段dictresize()的数据复制代码对比。对dictresize()函数的具体分析放在附录里。

      /* ./Objects/dictobject.c */
/* Python 3.5.9 */
static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
    ...
    /* Main loop */
    for (i = 0; i < oldsize; i++) {
        PyDictKeyEntry *ep = &oldkeys->dk_entries[i];
        if (ep->me_value != NULL) {
            assert(ep->me_key != dummy);
            insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
        }
    }
    mp->ma_keys->dk_usable -= mp->ma_used;
    ...
}
/* Python 3.6.0 */
static int
dictresize(PyDictObject *mp, Py_ssize_t minsize)
{
    ...
    /* Main loop */
    for (i = 0; i < oldkeys->dk_nentries; i++) {
        PyDictKeyEntry *ep = &ep0[i];
        if (ep->me_value != NULL) {
            insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
        }
    }
    mp->ma_keys->dk_usable -= mp->ma_used;
    ...
}

      现在知道是哪些代码节省了时间吗？就是所有for (i = 0; i < oldkeys->dk_nentries; i++){...}代码块。在 Python 3.5.9 中，它们对应for (i = 0; i < oldsize; i++){...}，其中的oldsize等于oldkeys->dk_size，只看代码的写法，没有什么区别，但是根据USABLE_FRACTION的设置，dk_nentries只占dk_size的2/3，所以新的字典迭代次数少了1/3。在dict_items()函数中的迭代操作速度变快也是同样的原因。

      现在再来看看 [Python-Dev] More compact dictionaries with faster iteration 里面的这几段话：

      源码观后感

      Python 的字典实现就是一套 tradeoff 的艺术，有太多的东西值得深思：

      • 使用空间占申请空间的比重
      • 哈希函数和探测函数的选用
      • 初始化需要申请的最小空间
      • 字典扩容时扩到多少
      • 元素分布对 CPU 缓存的影响

      目前 Python 里的各个参数都是通过大量测试得到的，考虑的场景很全面。然而，tradeoff 的艺术，也包括针对特定应用场景优化，如果能根据实际业务场景优化 Python 参数，性能还是可以提高的。

      此外，几个性能优化的点：

      • 缓存池只缓存小对象，大容量的字典的创建和扩容每次都要重新申请内存。多小算小呢？

      • 鉴于lookdict_unicode()函数的存在，尽量用字符串作为key

      参考./Objects/dictnotes.txt及./Objects/dictobject.c里的部分注释。

      参考资料

      附录

      dict 扩容源码分析

      扩容操作发生在元素插入的时候，当mp->ma_keys->dk_usable <= 0的时候，就对字典扩容，新容量使用GROWTH_RATE宏计算。dictresize()函数处理"combined"和"splitted"两种情况，需要分开看。

      /* Python 3.6.0 */
/* ./Objects/dictobject.c */
/* GROWTH_RATE. Growth rate upon hitting maximum load.
 * Currently set to used*2 + capacity/2.
 * This means that dicts double in size when growing without deletions,
 * but have more head room when the number of deletions is on a par with the
 * number of insertions.
 * Raising this to used*4 doubles memory consumption depending on the size of
 * the dictionary, but results in half the number of resizes, less effort to
 * resize.
 * GROWTH_RATE was set to used*4 up to version 3.2.
 * GROWTH_RATE was set to used*2 in version 3.3.0
 */
#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))

/*
Restructure the table by allocating a new table and reinserting all
items again.  When entries have been deleted, the new table may
actually be smaller than the old one.
If a table is split (its keys and hashes are shared, its values are not),
then the values are temporarily copied into the table, it is resized as
a combined table, then the me_value slots in the old table are NULLed out.
After resizing a table is always combined,
but can be resplit by make_keys_shared().
*/
static int
dictresize(PyDictObject *mp, Py_ssize_t minsize)
{
    Py_ssize_t i, newsize;
    PyDictKeysObject *oldkeys;
    PyObject **oldvalues;
    PyDictKeyEntry *ep0;

    /* Find the smallest table size > minused. */
    /* 1. 计算新大小 */
    for (newsize = PyDict_MINSIZE;
         newsize < minsize && newsize > 0;
         newsize <<= 1)
        ;
    if (newsize <= 0) {
        PyErr_NoMemory();
        return -1;
    }
    /* 2. 申请新的 PyDictKeysObject 对象 */
    oldkeys = mp->ma_keys;
    oldvalues = mp->ma_values;
    /* Allocate a new table. */
    mp->ma_keys = new_keys_object(newsize);
    if (mp->ma_keys == NULL) {
        mp->ma_keys = oldkeys;
        return -1;
    }
    // New table must be large enough.
    assert(mp->ma_keys->dk_usable >= mp->ma_used);
    if (oldkeys->dk_lookup == lookdict)
        mp->ma_keys->dk_lookup = lookdict;
    /* 3. 元素搬迁 */
    mp->ma_values = NULL;
    ep0 = DK_ENTRIES(oldkeys);
    /* Main loop below assumes we can transfer refcount to new keys
     * and that value is stored in me_value.
     * Increment ref-counts and copy values here to compensate
     * This (resizing a split table) should be relatively rare */
    if (oldvalues != NULL) {
        /* 3.1 splitted table 转换成 combined table */
        for (i = 0; i < oldkeys->dk_nentries; i++) {
            if (oldvalues[i] != NULL) {
                Py_INCREF(ep0[i].me_key);	// 要复制key，而原来的key也要用，所以增加引用计数
                ep0[i].me_value = oldvalues[i];
            }
        }
    }
    /* Main loop */
    for (i = 0; i < oldkeys->dk_nentries; i++) {
        PyDictKeyEntry *ep = &ep0[i];
        if (ep->me_value != NULL) {
            insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
        }
    }
    mp->ma_keys->dk_usable -= mp->ma_used;
    /* 4. 清理旧值 */
    if (oldvalues != NULL) {
        /* NULL out me_value slot in oldkeys, in case it was shared */
        for (i = 0; i < oldkeys->dk_nentries; i++)
            ep0[i].me_value = NULL;
        DK_DECREF(oldkeys);
        if (oldvalues != empty_values) {
            free_values(oldvalues);
        }
    }
    else {
        assert(oldkeys->dk_lookup != lookdict_split);
        assert(oldkeys->dk_refcnt == 1);
        DK_DEBUG_DECREF PyObject_FREE(oldkeys);
    }
    return 0;
}

      在分析函数内容前，先看下函数前面的说明：

      这段说明告诉我们 2 件重要的事情：

      1. 新的字典可能比旧的小，因为旧字典可能存在一些删除的entry。(字典删除元素后，为了保持探测序列不断开，元素状态转为dummy，创建新字典的时候去掉了这些dummy状态的元素)

        尽管如此，我仍然把这个操作称为“扩容”。

      2. “splitted”模式的字典经过扩容会永远变成"combined"模式，可以用make_keys_shared()函数重新调整为"splitted"模式。扩容操作会把原来的分离的values拷贝到entry里。

      我把这个函数分成了 4 个步骤：

      1. 计算新大小

        程序重新计算了字典大小，可是参数Py_ssize_t minsize不是字典大小吗？为什么要重新计算？

        minsize顾名思义，指定了调用者期望的字典大小，不过字典大小必须是 2 的整数次幂，所以重新算了下。翻看new_keys_object()函数，也会发现函数开头有这么一句: assert(IS_POWER_OF_2(size))，这是硬性要求，其原因已经在介绍数据结构的时候说过了，参考dk_size的说明。

      2. 申请新的 PyDictKeysObject 对象

        "combined"模式下，需要扩容的部分是PyDictKeysObject对象里面的dk_indices和dk_entries，程序并没有直接扩容这部分，因为

        为了更加便于理解，再说简单一点：key是复制，引用计数+1；value是移动，引用计数+0

    • 清理旧值

      "combined"模式下，直接释放旧的PyDictKeysObject对象；

      "splitted"模式下，需要还原旧的PyDictKeysObject对象里的dk_entries里的me_value为NULL，原因参考 3.1 里面的第一句话。最后释放ma_values数组。

05-06 08:26
Powered by LMLPHP ©2024 AdjWang 0.049015