为什么 python 从元组列表创建字典比从 kwargs 慢 3 倍

Question

在python中有几种构造字典的方法，例如：

keyvals = [('foo', 1), ('bar', 'bar'), ('baz', 100)]

dict(keyvals)

和

dkwargs = {'foo': 1, 'bar': 'bar', 'baz': 100}

dict(**dkwargs)

当您对这些进行基准测试时

In [0]: %timeit dict(keyvals)
667 ns ± 38 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [1]: %timeit dict(**dkwargs)
225 ns ± 7.09 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

你看到第一种方法比第二种方法慢了将近 3 倍。这是为什么？

Answer 1

dict(**kwargs)传入一个现成的字典，所以Python可以只复制一个已经存在的内部结构。

另一方面，元组列表需要迭代、验证、散列并将结果插入一个新的空 table。那几乎没有那么快。

Python 字典作为 hash table 实现，并且随着时间的推移 动态地 增长；它们从小开始，随着需要的出现，一个新的、更大的散列 table 被构建，数据（键、值和散列）被复制。这在 Python 代码中是不可见的，但调整大小需要时间。但是，当您使用 dict(**kwargs)（或 dict(other_dict) CPython（您用于测试的默认 Python 实现）时，可以使用快捷方式：start with a hash table 马上就足够大了。你不能对元组序列做同样的把戏，因为你无法预先知道序列中是否会有重复的键。

详细见dict类型的C源码，具体为dict_update_common implementation (which is called from dict_init());这会为元组序列调用 PyDict_MergeFromSeq2()，或者在传入关键字参数时调用 PyDict_Merge()。

PyDict_MergeFromSeq2() function 遍历序列，测试每个结果以确保有两个元素，然后实质上在字典上调用 .__setitem__(key, value)。这可能需要在某些时候调整字典的大小！

PyDict_Merge()函数（通过dict_merge()）专门检测是否传入了正则字典，然后executes a fast path调整内部结构一次，然后直接使用 insertdict() 调用从原始字典复制散列和结构（遵循 override == 1 路径，因为 override 已设置为 1 当目标字典为空，dict(**kwargs) 总是如此）。只需调整一次大小并直接使用内部数据，速度快得多，需要做的工作少得多！

所有这些都是特定于 CPython 的实现细节。其他 Python 实现，如 Jython、IronPython 和 PyPy 可以自行决定 dict 类型的内部工作方式，并且会针对相同的操作显示不同的性能差异。

Answer 2

dkwargs 已经是一本字典，因此您基本上可以复制它。这就是为什么它要快得多的原因。

Answer 3

简答（长话短说）

这是因为在第一个测试中，dict 的 CPython 实现将从列表中创建一个新字典，但第二个测试仅复制字典。复制比解析列表花费的时间更少。

附加信息

考虑这段代码：

import dis
dis.dis("dict([('foo', 1), ('bar', 'bar'), ('baz', 100)])", depth=10)
print("------------")
dis.dis("dict({'foo': 1, 'bar': 'bar', 'baz': 100})", depth=10)

哪里

The dis module supports the analysis of CPython bytecode by disassembling it.

这让我们可以看到执行的字节码操作。输出显示

  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (('foo', 1))
              4 LOAD_CONST               1 (('bar', 'bar'))
              6 LOAD_CONST               2 (('baz', 100))
              8 BUILD_LIST               3
             10 CALL_FUNCTION            1
             12 RETURN_VALUE
------------
  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (1)
              4 LOAD_CONST               1 ('bar')
              6 LOAD_CONST               2 (100)
              8 LOAD_CONST               3 (('foo', 'bar', 'baz'))
             10 BUILD_CONST_KEY_MAP      3
             12 CALL_FUNCTION            1
             14 RETURN_VALUE

从输出中可以看到：

两次调用都需要加载将要调用的 dict 名称。
之后，第一个方法将列表加载到内存 (BUILD_LIST)，而第二个方法构建字典 (BUILD_CONST_KEY_MAP)（参见 here）
因此，当调用 dict 函数时（CALL_FUNCTION 步骤（参见 here）），在第二种情况下花费的时间要短得多，因为已经创建了字典，所以它只是制作一个副本，而不必遍历列表来创建哈希 [=82=].

注意：使用字节码你不能最终决定 CALL_FUNCTION 这样做，因为它的实现是用 C 编写的，只有通过阅读它你才能真正知道这一点（有关这部分工作原理的准确解释，请参阅 Martijn Pieters 的回答）。但是，它有助于了解字典对象是如何创建的 outside dict()（在示例中是逐步创建的，而不是语法上创建的），而对于列表，这是不是这样的。

编辑

明确地说，当你说

There are a couple of ways to construct a dictionary in python

确实是这样：

dkwargs = {'foo': 1, 'bar': 'bar', 'baz': 100}

从解释器将表达式转换为存储在内存中的字典对象，并使变量 dkwargs 指向它的意义上来说，您正在创建字典。但是，通过执行以下操作：dict(**kwargs) 或者如果您更喜欢 dict(kwargs)，您并不是真正地 创建字典 ，而只是复制一个已经存在的对象（强调复制很重要）：

>>> dict(dkwargs) is dkwargs
False

dict(kwargs) 强制 Python 创建一个新对象；然而，这并不意味着它必须重新构建 对象。事实上，该操作是无用的，因为实际上它们是相等的对象（虽然不是同一个对象）。

>>> id(dkwargs)
2787648914560
>>> new_dict = dict(dkwargs)
>>> id(new_dict)
2787652299584
>>> new_dict == dkwargs
True
>>> id(dkwargs) is id(new_dict)
False

哪里id:

Return the “identity” of an object. This is an integer which is guaranteed to be unique and constant for this object during its lifetime [...]

CPython implementation detail: This is the address of the object in memory.

当然，除非您想要专门复制对象以修改一个对象，这样编辑就不会链接到另一个引用。

为什么 python 从元组列表创建字典比从 kwargs 慢 3 倍

Why is python dict creation from list of tuples 3x slower than from kwargs

python

performance

benchmarking

python-3.x

python-internals

简答（长话短说）

附加信息

编辑