细说 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;后面的indicesentries对应 3.6.0 版本的dk_indicesdk_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_addrNULL

        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_size2/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_indicesdk_entries,程序并没有直接扩容这部分,因为

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

    • 清理旧值

      "combined"模式下,直接释放旧的PyDictKeysObject对象;

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

05-06 08:26