细说 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)
下面依次说明一下各个数据的定义:
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
是一个函数指针,指向四大搜索函数的其中一个,这里有必要说明一下各参数和返回值:参数
PyDictObject *mp
(已知参数)字典对象,在该对象中查找。
PyObject *key
(已知参数)entry
里的key
,代表key
对象的引用,用于第一次判定,如果引用相同就找到了;如果不同再判断hash
Py_hash_t hash
(已知参数)entry
里的hash
,用于第二次判定,如果哈希值相同就找到了;如果不同就代表没找到。PyObject ***value_addr
(未知参数,用指针返回数据)如果找到元素,则
value_addr
返回对应的me_value
的指针;如果没找到,*value_addr
为NULL
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
里的部分注释。参考资料
- 《Python源码剖析》
- 关于python3.6中dict如何保证有序
- [Python-Dev] More compact dictionaries with faster iteration
- PEP 468 -- Preserving the order of **kwargs in a function.
- PEP 468: Preserving Keyword Argument Order
- issue27350
- https://morepypy.blogspot.hk/2015/01/faster-more-memory-efficient-and-more.html
- http://python-weekly.blogspot.com/2017/01/20-best-python-questions-at.html
附录
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 件重要的事情:
新的字典可能比旧的小,因为旧字典可能存在一些删除的
entry
。(字典删除元素后,为了保持探测序列不断开,元素状态转为dummy
,创建新字典的时候去掉了这些dummy
状态的元素)尽管如此,我仍然把这个操作称为“扩容”。
“splitted”模式的字典经过扩容会永远变成"combined"模式,可以用
make_keys_shared()
函数重新调整为"splitted"模式。扩容操作会把原来的分离的values
拷贝到entry
里。
我把这个函数分成了 4 个步骤:
计算新大小
程序重新计算了字典大小,可是参数
Py_ssize_t minsize
不是字典大小吗?为什么要重新计算?minsize
顾名思义,指定了调用者期望的字典大小,不过字典大小必须是 2 的整数次幂,所以重新算了下。翻看new_keys_object()
函数,也会发现函数开头有这么一句:assert(IS_POWER_OF_2(size))
,这是硬性要求,其原因已经在介绍数据结构的时候说过了,参考dk_size
的说明。申请新的 PyDictKeysObject 对象
"combined"模式下,需要扩容的部分是
PyDictKeysObject
对象里面的dk_indices
和dk_entries
,程序并没有直接扩容这部分,因为为了更加便于理解,再说简单一点:
key
是复制,引用计数+1;value
是移动,引用计数+0
清理旧值
"combined"模式下,直接释放旧的
PyDictKeysObject
对象;"splitted"模式下,需要还原旧的
PyDictKeysObject
对象里的dk_entries
里的me_value
为NULL
,原因参考 3.1 里面的第一句话。最后释放ma_values
数组。