首页 » 漏洞 » Python内核阅读(五): Dict对象

Python内核阅读(五): Dict对象

 

起步

python中PyDictObject采用了散列表,平均状况是O(1)复杂度的搜索效率.

散列表是通过一定的函数将需搜索的键值映射为一个整数,将这个整数视为索引去访问某片连续的内存区域. 一般情况下,hash table会申请一块较大的连续内存通过映射函数f(n)得到所对应的索引.

在使用散列表过程中,随着需要存储的数据增多,hash冲突的概率就越高.会直接影响到hash的效率和性能.

在python中采用闭散列法来解决冲突,闭散列法也称为开放定址法.当产生冲突时,python会通过一个二次探测函数f,计算下一个候选索引, 如果索引不可用,就再次用f探测.直到找到一个可用的位置.

之所以叫做闭散列法,就是因为冲突的元素没有开辟额外的存储空间,还是在原先hash表的空间范围之内。

关联容器

假如我们将具有某种关系的两个数组成一组,例如(3, 6), (4, 8),他们具有2倍关系, 组成一组的好处就是找到3就能立马找到6.

因此关联容器常以(key, value)存在.Python中定义这样的关联容器Entry:

[dict-common.h] typedef struct {     Py_hash_t me_hash;     PyObject *me_key;     PyObject *me_value; } PyDictKeyEntry;

在PyDictKeyEntry中,me_hash表示me_key的散列值, 保存这个值是为了避免重复计算. 在PyDictObject对象发生变化时, 其中的entry也会在不同的状态间切换.关联容器存在3中状态:

  • Unused(未使用): index == DKIX_EMPTY
  • Active(活动): index >= 0, me_key != NULL and me_value != NULL
  • Dummy(删除状态): index == DKIX_DUMMY 之所以不能直接转成Unused状态是因为这要会导致冲突测链中断
#define DKIX_EMPTY (-1) #define DKIX_DUMMY (-2)  /* Used internally */ #define DKIX_ERROR (-3)

关联容器的实现

[dictobject.h] typedef struct {     PyObject_HEAD      // Active元素个数     Py_ssize_t ma_used;      // 全局唯一, 值会随着dict的修改而改变     uint64_t ma_version_tag;      PyDictKeysObject *ma_keys;      // 如果ma_values == NULL 表示哈希表是结合的, 如果ma_values != NULL 则表被拆分     PyObject **ma_values; } PyDictObject;

PyDictKeysObject是这样定义的:

[dict-common.h] struct _dictkeysobject {     Py_ssize_t dk_refcnt;      // hash表允许容纳元素的个数 必定是2的指数     Py_ssize_t dk_size;      // 与hash table有关的函数     dict_lookup_func dk_lookup;      // 元素个数 Active + Dummy     Py_ssize_t dk_usable;      // 元素个数 Active     Py_ssize_t dk_nentries;      union {         int8_t as_1[8];         int16_t as_2[4];         int32_t as_4[2];     } dk_indices; };

“PyDictKeyEntry dk_entries [dk_usable];” 数组如下,参阅DK_ENTRIES()宏:

#define DK_ENTRIES(dk) /     ((PyDictKeyEntry*)(&(dk)->dk_indices.as_1[DK_SIZE(dk) * DK_IXSIZE(dk)]))

从python3.6开始,借鉴 PyPy 字典设计,采用更紧凑的存储结构.内存效率更高, 更多信息可以查看 https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html

key可以分布如下:

+---------------+ | dk_refcnt     | | dk_size       | | dk_lookup     | | dk_usable     | | dk_nentries   | +---------------+ | dk_indices    | |               | +---------------+ | dk_entries    | |               | +---------------+

dk_indices 是实际的哈希表。它在条目中保存索引,或 KIX_EMPTY (-1)或 DKIX_DUMMY (-2)。哈希表能容纳元素的个数 dk_size . dk_entries 是一个PyDictKeyEntr的数组。它的大小是USABLE_FRACTION(dk_size)。 可以使用DK_ENTRIES(dk)来获取指向条目的指针。注意:由于负值用于DKIX_EMPTY和DKIX_DUMMY,所以键入 dk_indices条目是有符号整数,int16用于表大小dk_size == 256。

为什么说更省空间呢?

比如需要一个字典 d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'} ,那其结构在旧模式下是:

entries = [['--', '--', '--'],            [-8522787127447073495, 'barry', 'green'],            ['--', '--', '--'],            ['--', '--', '--'],            ['--', '--', '--'],            [-9092791511155847987, 'timmy', 'red'],            ['--', '--', '--'],            [-6480567542315338377, 'guido', 'blue']]

而使用新的为:

indices =  [None, 1, None, None, None, 0, None, 2] entries =  [[-9092791511155847987, 'timmy', 'red'],             [-8522787127447073495, 'barry', 'green'],             [-6480567542315338377, 'guido', 'blue']]

indices就是哈希表,改变的只是布局, 哈希表算法将不变.例子中节省了得58%的内存。据说能节省30%~95~的空间(取决表的完整程度). 除了节省空间, 新的布局迭代更快, keys() values() items() ,直接在关联容器 entries 获取, 无需判断 ['--', '--', '--'] 空关联容器. 移动或者复制hash表,只需操作indices即可.

请注意,sizeof(index)可以小到单个小字节的字节,大字节的两个字节直到sizeof(Py_ssize_t)为巨大的dict。因此可以看到 PyDictKeyObject 中的 dk_indices 是个联合体.为了是更省内存. 作者很抠内存的, 巴不得一个字节当两个字节用.

PyDictObject 对象的创建

python内部通过PyDict_New来创建一个新的dict对象:

[dictobject.h] PyObject * PyDict_New(void) {     PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);     if (keys == NULL)         return NULL;     return new_dict(keys, NULL); }

PyDict_MINSIZE 值为8, 默认情况下, PyDict_New会创建8个entry

static PyDictKeysObject *new_keys_object(Py_ssize_t size) {     PyDictKeysObject *dk;     Py_ssize_t es, usable;      usable = USABLE_FRACTION(size);     es = 4;      if (size == PyDict_MINSIZE && numfreekeys > 0) {         // 使用缓冲池         dk = keys_free_list[--numfreekeys];     }     else {         dk = PyObject_MALLOC(sizeof(PyDictKeysObject)                              - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)                              + es * size                              + sizeof(PyDictKeyEntry) * usable);     }     DK_DEBUG_INCREF dk->dk_refcnt = 1;     dk->dk_size = size;     dk->dk_usable = usable;     dk->dk_lookup = lookdict_unicode_nodummy;     dk->dk_nentries = 0;     // hash table 初始化     memset(&dk->dk_indices.as_1[0], 0xff, es * size);     memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);     return dk; }

keys.entries 和 values 用数组按添加顺序存储主键和值引用。实际哈希表由 keys.indices 数组承担,通过计算主键哈希值找到合适位置,然后在此存储主键在 keys.entries 的实际索引。如此,只要通过 indices 获取实际索引后,就可读取主键和值信息。

dk = PyObject_MALLOC(sizeof(PyDictKeysObject)                              - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)                              + es * size    // hash索引表                              + sizeof(PyDictKeyEntry) * usable);    // PyDictKeyEntry 的数组, 申请大小为表size的2/3

也就是说 PyDictKeysObject 中成员 dk_indices 有两个重要的成分, 一个是前半部分的hash table索引. 另一个是后半部分的关联容器数组

元素搜索

无论是字典的设置 d["aaa"] = 3 还是获取 a = d["aaa"] 都需要对hash table进行搜索. python位hash表搜索提供了多种函数, 通用的 lookdict , 针对字符串类型的 lookdict_unicode , 针对数字的 lookdict_index . 但他们的算法是相同的. lookdict 是获取字典

static Py_ssize_t _Py_HOT_FUNCTION lookdict(PyDictObject *mp, PyObject *key,          Py_hash_t hash, PyObject **value_addr) {     size_t i, mask, perturb;     PyDictKeysObject *dk;     PyDictKeyEntry *ep0;  top:     dk = mp->ma_keys;     ep0 = DK_ENTRIES(dk);     mask = DK_MASK(dk);     perturb = hash;     i = (size_t)hash & mask;    // mask是2的指数-1, 因此相当于取模      for (;;) {         Py_ssize_t ix = dk_get_index(dk, i);// dk->indecs[i]         if (ix == DKIX_EMPTY) {             *value_addr = NULL;             return ix;         }         if (ix >= 0) {             PyDictKeyEntry *ep = &ep0[ix];             assert(ep->me_key != NULL);             if (ep->me_key == key) { // 同一个引用                 *value_addr = ep->me_value;                 return ix;             }             if (ep->me_hash == hash) {  // 因为不同值的hash结果可能相同                 PyObject *startkey = ep->me_key;                 Py_INCREF(startkey);                 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);// 进行完整的比较                 Py_DECREF(startkey);                 if (cmp < 0) {                     *value_addr = NULL;                     return DKIX_ERROR;                 }                 if (dk == mp->ma_keys && ep->me_key == startkey) {                     if (cmp > 0) {                         *value_addr = ep->me_value;                         return ix;                     }                 }                 else {                     /* The dict was mutated, restart */                     goto top;                 }             }         }         perturb >>= PERTURB_SHIFT;         i = (i*5 + perturb + 1) & mask; // 哈希探测函数     }     assert(0);          /* NOT REACHED */     return 0; }

dk_get_index(dk, i) 简单理解为 ->dk_indices.as_1[i] 即可, 对于不同规模的hash表, 用as_1或as_2有所不同而已. 对于lookdict来说, 永远不会返回NULL, 如果搜索不到待查找的key, 同样会返回一个空的关联容器的索引.

在python的字典中,"相同"这个概念包含了两个含义:

  1. 引用相同
  2. 值相同 在 lookdictep->me_key == key 就意味着他们的值相同, 在其判断体内加 printf("key is same/n"); 可以看到:
>>> a = {} >>> a[2] = "python" >>> a[2] key is same 'python' >>> a[999] = "php" >>> a[999] 'php' >>>

小整数对象是共享的, 因此他们key都是指向同一个地址. 大整数对象并不是共享, 但是999明明在key中是存在的,因此"值相同"规则就有存在的意义.

总结搜索过程入下:

  1. 根据 PyObject *key 的哈希值获得entry索引, 这是冲突探测链上第一个entry索引.
  2. 两种情况下,搜索结束:
    • entry处于Unuse状态,表示冲突弹窗搜索结束, 搜索失败
    • ep->me_key == key 表示entry的key与待搜索key是同一个PyObject对象, 搜索成功
  3. 若当前的entry处于Dummy态, 设置为freeslot
  4. 检查Active态中的entry中的key是否与待查找的key"值相同", 若找到, 搜索成功. 若不匹配, 则沿着探测链查找.探测链检测到DUMMY状态是,设置freeslot

当entry中的key与待查找的key不匹配时, 拦着探测链顺藤摸瓜.

探测链上的过程与前面的过程基本一致, 总之, lookdict 如果搜索成功, 返回一定是有效的entry索引.如果搜索失败,则返回一个Unused状态的entry索引.因为dummy状态的entry实际也是一个空闲的entry, 当遍历到Dummy状态的entry,便会设置freeslot,freeslot是下一个被inserted的索引.

其他搜索策略都差不多. 哦对了, 默认的搜索策略是 lookdict_unicode_nodummy 介绍说比lookdict_unicode快,不清楚为什么搜索出来的entry不含dummy的.

python内部也大量使用的PyDictObject对象, 如维护一个名字空间的变量名与值的关系, 函数传递参数时参数名与参数值的关系.

hash冲突时采用 i = ((i << 2) + i + perturb + 1) & mask;i = (i * 5 + i) % dk_size; 因为dk_size是2的指数, 所以这个探测正好能遍历所有元素.

插入

关于dict的操作基本都是建立在搜索的基础上的.

static int insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) {     PyObject *old_value;     PyDictKeyEntry *ep;      Py_INCREF(key);     Py_INCREF(value);     if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {         if (insertion_resize(mp) < 0)             goto Fail;     }      Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);     if (ix == DKIX_ERROR)         goto Fail;      // 检查...      // 检查共享key, 必要时进行hash表扩容     if (_PyDict_HasSplitTable(mp) &&         ((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||          (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {         if (insertion_resize(mp) < 0)             goto Fail;         ix = DKIX_EMPTY;     }      // 搜索成功     if (ix == DKIX_EMPTY) {         /* Insert into new slot. */         assert(old_value == NULL);         if (mp->ma_keys->dk_usable <= 0) {             /* Need to resize. */             if (insertion_resize(mp) < 0)                 goto Fail;         }         Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);         ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];         dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);         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++;  // 使用数+1         mp->ma_version_tag = DICT_NEXT_VERSION();// 版本号+1         mp->ma_keys->dk_usable--;       // 可用数-1         mp->ma_keys->dk_nentries++;     // 关联容器数量+1         assert(mp->ma_keys->dk_usable >= 0);         assert(_PyDict_CheckConsistency(mp));         return 0;     }     // ...     DK_ENTRIES(mp->ma_keys)[ix].me_value = value;      mp->ma_version_tag = DICT_NEXT_VERSION();// 版本号+1     Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */     assert(_PyDict_CheckConsistency(mp));     Py_DECREF(key);     return 0;  Fail:     Py_DECREF(value);     Py_DECREF(key);     return -1; }

在搜索的 lookup 函数中, 返回的关联容器状态有两个结果:搜索成功是,返回的是Active的entry,这种情况下直接替换即可 *value_addr = value; . 搜索不成功是, 返回的是Unuse或Dummy状态的关联容器,需要完整设置 me_key,me_hash,me_value . python代码中 d["aaa"] = 4 其实是调用 PyDict_SetItem 的:

int PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value) {     PyDictObject *mp;     Py_hash_t hash;      mp = (PyDictObject *)op;     if (!PyUnicode_CheckExact(key) ||         (hash = ((PyASCIIObject *) key)->hash) == -1)     {         hash = PyObject_Hash(key);         if (hash == -1)             return -1;     }      /* insertdict() handles any resizing that might be necessary */     return insertdict(mp, key, hash, value); }

如果key只是替换现有的值,也就是当搜索成功时. 是不改变hash table大小的. 这就意味着 PyDict_Next() 循环使用字典是安全的了.

insertdict中会重新resize哈希表:

// 增长率 #define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))  static int insertion_resize(PyDictObject *mp) {     return dictresize(mp, GROWTH_RATE(mp)); }

改变table的大小交到了 dictresize 身上.

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. */     for (newsize = PyDict_MINSIZE;          newsize < minsize && newsize > 0;          newsize <<= 1)         ;      oldkeys = mp->ma_keys;     oldvalues = mp->ma_values;     // 申请新空间     mp->ma_keys = new_keys_object(newsize);      if (oldkeys->dk_lookup == lookdict)         mp->ma_keys->dk_lookup = lookdict;     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) {         // 搬迁list         for (i = 0; i < oldkeys->dk_nentries; i++) {             if (oldvalues[i] != NULL) {                 Py_INCREF(ep0[i].me_key);                 ep0[i].me_value = oldvalues[i];             }         }     }     // 旧hash表到新hash表搬迁, hash值不会重新计算, 但关联容器索引会重新计算     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);         }     }     ...     return 0; }

resize将hash表容量扩大两倍, 然后搬迁数据, 表hash索引不需要重新计算.

原文链接:Python内核阅读(五): Dict对象,转载请注明来源!

0