众所周知,python3.6这个版本对dict的实现是做了较大优化的,特别是在内存使用率方面,因此我觉得有必要研究一下最新的dict的源码实现。
前后断断续续看了大概一周多一点,主要在研究dict和创建实例对象那部分的代码,在此将所得记录下来。
值得一提的事,新版的dict使用的算法还是一样的,比如说hash值计算、冲突解决策略(open addressing)等。因此这一部分也不是我关注的重点,我关注的主要是在新的dict如何降低内存使用这方面。
btw,本文的分析是基于python的3.6.1这个版本。
话不多说,先看 PyDictObject 结构的定义:
1 typedef struct _dictkeysobject PyDictKeysObject; 2 3 /* The ma_values pointer is NULL for a combined table 4 * or points to an array of PyObject* for a split table 5 */ 6 typedef struct { 7 PyObject_HEAD 8 9 /* Number of items in the dictionary */10 Py_ssize_t ma_used;11 12 /* Dictionary version: globally unique, value change each time13 the dictionary is modified */14 uint64_t ma_version_tag;15 16 PyDictKeysObject *ma_keys;17 18 /* If ma_values is NULL, the table is "combined": keys and values19 are stored in ma_keys.20 21 If ma_values is not NULL, the table is splitted:22 keys are stored in ma_keys and values are stored in ma_values */23 PyObject **ma_values;24 } PyDictObject;
说下新增的 PyDictKeysObject 这个对象,其定义如下:
1 /* See dictobject.c for actual layout of DictKeysObject */ 2 struct _dictkeysobject { 3 Py_ssize_t dk_refcnt; 4 5 /* Size of the hash table (dk_indices). It must be a power of 2. */ 6 Py_ssize_t dk_size; 7 8 /* Function to lookup in the hash table (dk_indices): 9 10 - lookdict(): general-purpose, and may return DKIX_ERROR if (and11 only if) a comparison raises an exception.12 13 - lookdict_unicode(): specialized to Unicode string keys, comparison of14 which can never raise an exception; that function can never return15 DKIX_ERROR.16 17 - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further18 specialized for Unicode string keys that cannot be thevalue.19 20 - lookdict_split(): Version of lookdict() for split tables. */21 dict_lookup_func dk_lookup;22 23 /* Number of usable entries in dk_entries. */24 Py_ssize_t dk_usable;25 26 /* Number of used entries in dk_entries. */27 Py_ssize_t dk_nentries;28 29 /* Actual hash table of dk_size entries. It holds indices in dk_entries,30 or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).31 32 Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).33 34 The size in bytes of an indice depends on dk_size:35 36 - 1 byte if dk_size <= 0xff (char*)37 - 2 bytes if dk_size <= 0xffff (int16_t*)38 - 4 bytes if dk_size <= 0xffffffff (int32_t*)39 - 8 bytes otherwise (int64_t*)40 41 Dynamically sized, 8 is minimum. */42 union {43 int8_t as_1[8];44 int16_t as_2[4];45 int32_t as_4[2];46 #if SIZEOF_VOID_P > 447 int64_t as_8[1];48 #endif49 } dk_indices;50 51 /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:52 see the DK_ENTRIES() macro */53 };
新版的dict在内存布局上和旧版有了很大的差异,其中一点就是分离存储了key和value。设计思路可以看看这个:
还有一点需要说明的是,新版的dict有两种形式,分别是 combined 和 split。其中后者主要用在优化对象存储属性的tp_dict上,这个在后面讨论。
对于旧版的hash table,其每个slot存储的是一个 PyDictKeyEntry 对象(PyDictKeyEntry是一个三元组,包含了hash、key、value),这样带来的问题就是,多占用了一些非必要的内存。对于状态为EMPTY的slot,实际可能存储为(0,NULL,NULL)这种形式,但其实这些数据都是冗余的。
因此新版的hash table对此作出了优化,slot(也即是 dk_indices) 存储的不再是一个 PyDictKeyEntry,而是一个数组的index,这个数组存储了具体且必要的 PyDictKeyEntry对象 。对于那些EMPTY、DUMMY状态的这类slot,只需要用个负数(区分大于0的index)表示即可。
实际上,优化还不止于此。实际上还会根据需要索引 PyDictKeyEntry 对象的数量,动态的决定是用什么类型的变量来表示index。例如,如果所存储的 PyDictKeyEntry 数量不超过127,那么实际上用长度为一个字节的带符号整数(char)存储index即可。需要说明的是,index的值是有可能为负的(EMPTY、DUMMY、ERROR),因此需要用带符号的整数存储。具体可以看 new_keys_object 这个函数,这个函数在创建 dict 的时候会被调用:
1 PyObject * 2 PyDict_New(void) 3 { 4 PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE); 5 if (keys == NULL) 6 return NULL; 7 return new_dict(keys, NULL); 8 } 9 10 static PyDictKeysObject *new_keys_object(Py_ssize_t size)11 {12 PyDictKeysObject *dk;13 Py_ssize_t es, usable;14 15 assert(size >= PyDict_MINSIZE);16 assert(IS_POWER_OF_2(size));17 18 usable = USABLE_FRACTION(size);19 if (size <= 0xff) {20 es = 1;21 }22 else if (size <= 0xffff) {23 es = 2;24 }25 #if SIZEOF_VOID_P > 426 else if (size <= 0xffffffff) {27 es = 4;28 }29 #endif30 else {31 es = sizeof(Py_ssize_t);32 }33 34 if (size == PyDict_MINSIZE && numfreekeys > 0) {35 dk = keys_free_list[--numfreekeys];36 }37 else {38 dk = PyObject_MALLOC(sizeof(PyDictKeysObject)39 - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)40 + es * size41 + sizeof(PyDictKeyEntry) * usable);42 if (dk == NULL) {43 PyErr_NoMemory();44 return NULL;45 }46 }47 DK_DEBUG_INCREF dk->dk_refcnt = 1;48 dk->dk_size = size;49 dk->dk_usable = usable;50 dk->dk_lookup = lookdict_unicode_nodummy;51 dk->dk_nentries = 0;52 memset(&dk->dk_indices.as_1[0], 0xff, es * size);53 memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);54 return dk;55 }
有几点需要说明一下:
(1)受限于装填因子,因此给定一个hash table 的 size 就能确定出最多可容纳多少个有效对象(上图代码18行),因此存储的 PyDictKeyEntry 对象的数组的长度是可以在一开始便确定下来的。PyDictKeysObject 对象上的 dk_usable 表示hash table还能存储多少个对象,其值小于等于0的时候,再插入元素需要执行 rehash 操作。
(2)传入的size的值必须是2的幂,因此如果 size <= 0xff(255) 成立,则说明 size <= 128,因此用1个字节长度来表示index足矣。
(3)CPython的代码到处存在着缓存策略,keys_free_list 也是如此,目的是减少实际执行malloc的次数。
(4)当申请内存时,在计算一个 PyDictKeysObject 对象实际需要的内存时,需要减去 dk_indices 成员默认的大小,默认大小是8字节。这部分内存是根据size动态确定下来的。
现在来说说之前提及的split形式的dict。这种字典的key是共享的,有一个引用计数器 dk_refcnt 来维护当前被引用的个数。而之所以设计出split形式的字典,是因为观察到了python虚拟机中,会有大量key相同而value不同的字典的存在。而这个特定的情况就是实例对象上存储属性的 tp_dict 字典!
因此split形式的dict主要是出于对优化实例对象上存储属性这种情况考虑的。设计思路这里有所提及:
我们都知道,python使用dict来存储对象的属性。考虑一个这样的场景:
(1)一个类会创建出很多个对象。
(2)这些对象的属性,能在一开始就确定下来,并且后续不会增加删除。
如果能满足上述两个条件,那么其实我们可以使用一种更高效、更省内存的方式,来存储对象的属性。方法就是,属于一个类的所有对象共享同一份属性字典的key,而value以数组的方式存储在每个对象的身上。优化的好处是显而易见的,原来需要为每一个对象维持一份属性key,而现在只需为所有对象维持一份即可,并且属性的值(value)也以更加紧凑的方式组织在内存中。新版的dict的设计使得实现这种共享key的策略变得更简单!
看看具体的代码:
1 int 2 _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr, 3 PyObject *key, PyObject *value) 4 { 5 PyObject *dict; 6 int res; 7 PyDictKeysObject *cached; 8 9 assert(dictptr != NULL);10 if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && (cached = CACHED_KEYS(tp))) {11 assert(dictptr != NULL);12 dict = *dictptr;13 if (dict == NULL) {14 DK_INCREF(cached);15 dict = new_dict_with_shared_keys(cached); // importance!!!16 if (dict == NULL)17 return -1;18 *dictptr = dict;19 }20 if (value == NULL) {21 res = PyDict_DelItem(dict, key);22 // Since key sharing dict doesn't allow deletion, PyDict_DelItem()23 // always converts dict to combined form.24 if ((cached = CACHED_KEYS(tp)) != NULL) {25 CACHED_KEYS(tp) = NULL;26 DK_DECREF(cached);27 }28 }29 else {30 int was_shared = (cached == ((PyDictObject *)dict)->ma_keys);31 res = PyDict_SetItem(dict, key, value);32 if (was_shared &&33 (cached = CACHED_KEYS(tp)) != NULL &&34 cached != ((PyDictObject *)dict)->ma_keys) {35 /* PyDict_SetItem() may call dictresize and convert split table36 * into combined table. In such case, convert it to split37 * table again and update type's shared key only when this is38 * the only dict sharing key with the type.39 *40 * This is to allow using shared key in class like this:41 *42 * class C:43 * def __init__(self):44 * # one dict resize happens45 * self.a, self.b, self.c = 1, 2, 346 * self.d, self.e, self.f = 4, 5, 647 * a = C()48 */49 if (cached->dk_refcnt == 1) {50 CACHED_KEYS(tp) = make_keys_shared(dict);51 }52 else {53 CACHED_KEYS(tp) = NULL;54 }55 DK_DECREF(cached);56 if (CACHED_KEYS(tp) == NULL && PyErr_Occurred())57 return -1;58 }59 }60 } else {61 dict = *dictptr;62 if (dict == NULL) {63 dict = PyDict_New();64 if (dict == NULL)65 return -1;66 *dictptr = dict;67 }68 if (value == NULL) {69 res = PyDict_DelItem(dict, key);70 } else {71 res = PyDict_SetItem(dict, key, value);72 }73 }74 return res;75 }
当我们在类的 __init__ 方法中通过 self.a = v 初始化一个对象的属性时,最终会调用到函数_PyObjectDict_SetItem。此函数会初始化对象的tp_dict,也即是对象的属性字典。从上述的第15行代码可以看出,在特定情况下,会将对象的属性字典初始化为共享key的split式字典。因此也验证了之前的分析。