为什么比list()更快?

我最近比较了[]list()的处理速度,并惊讶地发现[]list()运行速度快三倍以上。 我用{}dict()进行了相同的testing,结果几乎相同: []{}都花费了大约0.128秒/百万个周期,而list()dict()花费了大约0.428秒/百万个周期。

为什么是这样? list()dict()tuple()str() )的时候, []{} (也许是()'' )会立即传回一些空的库存文字的副本。完全去创造一个对象,不pipe他们是否真的有元素?

我不知道这两种方法有什么不同,但我很想知道。 我无法在文档或SO上find答案,而search空括号的结果却比我预期的更成问题。

我通过调用timeit.timeit("[]")timeit.timeit("list()")timeit.timeit("{}")timeit.timeit("dict()")比较列表和字典,分别。 我正在运行Python 2.7.9。

我最近发现“ 为什么如果True比1更慢? ”,它比较了if Trueif 1的性能,似乎涉及类似的文字与全局情景; 也许这也值得考虑。

因为[]{}字面语法 。 Python可以创build字节码来创build列表或字典对象:

 >>> import dis >>> dis.dis(compile('[]', '', 'eval')) 1 0 BUILD_LIST 0 3 RETURN_VALUE >>> dis.dis(compile('{}', '', 'eval')) 1 0 BUILD_MAP 0 3 RETURN_VALUE 

list()dict()是独立的对象。 他们的名字需要解决,堆栈必须参与推送参数,框架必须被存储以便稍后检索,并且必须进行调用。 这一切都需要更多的时间。

对于空白的情况,这意味着至less有一个LOAD_NAME (它必须search全局名称空间以及__builtin__模块 ),然后是CALL_FUNCTION ,它必须保留当前帧:

 >>> dis.dis(compile('list()', '', 'eval')) 1 0 LOAD_NAME 0 (list) 3 CALL_FUNCTION 0 6 RETURN_VALUE >>> dis.dis(compile('dict()', '', 'eval')) 1 0 LOAD_NAME 0 (dict) 3 CALL_FUNCTION 0 6 RETURN_VALUE 

您可以使用timeit分别计时查找名称:

 >>> import timeit >>> timeit.timeit('list', number=10**7) 0.30749011039733887 >>> timeit.timeit('dict', number=10**7) 0.4215109348297119 

时间差异可能是字典散列冲突。 从调用这些对象的时间中减去这些时间,并将结果与​​使用文字的时间进行比较:

 >>> timeit.timeit('[]', number=10**7) 0.30478692054748535 >>> timeit.timeit('{}', number=10**7) 0.31482696533203125 >>> timeit.timeit('list()', number=10**7) 0.9991960525512695 >>> timeit.timeit('dict()', number=10**7) 1.0200958251953125 

因此,不得不调用该对象每1000万次呼叫需要额外的1.00 - 0.31 - 0.30 == 0.39秒。

您可以通过将全局名称别名为本地名称来避免全局查找成本(使用timeit设置,绑定到名称的所有内容都是本地的):

 >>> timeit.timeit('_list', '_list = list', number=10**7) 0.1866450309753418 >>> timeit.timeit('_dict', '_dict = dict', number=10**7) 0.19016098976135254 >>> timeit.timeit('_list()', '_list = list', number=10**7) 0.841480016708374 >>> timeit.timeit('_dict()', '_dict = dict', number=10**7) 0.7233691215515137 

但是你永远无法克服CALL_FUNCTION成本。

list()需要全局查找和函数调用,但[]编译为单个指令。 看到:

 Python 2.7.3 >>> import dis >>> print dis.dis(lambda: list()) 1 0 LOAD_GLOBAL 0 (list) 3 CALL_FUNCTION 0 6 RETURN_VALUE None >>> print dis.dis(lambda: []) 1 0 BUILD_LIST 0 3 RETURN_VALUE None 

因为list是一个将string转换成列表对象的函数,而[]则用来创build一个关于bat的列表。 试试这个(对你来说可能更有意义):

 x = "wham bam" a = list(x) >>> a ["w", "h", "a", "m", ...] 

 y = ["wham bam"] >>> y ["wham bam"] 

给你一个实际的列表,包含你放入的任何东西。

这里的答案很好,就这一点而言,完全覆盖了这个问题。 对于那些感兴趣的人,我会再从字节码中再下一步。 我正在使用最近的CPython回购; 旧版本在这方面performance类似,但是可能会有轻微的变化。

下面是这些的执行BUILD_LISTBUILD_LIST用于[]CALL_FUNCTION用于list()


BUILD_LIST指令:

你应该只是看恐怖:

 PyObject *list = PyList_New(oparg); if (list == NULL) goto error; while (--oparg >= 0) { PyObject *item = POP(); PyList_SET_ITEM(list, oparg, item); } PUSH(list); DISPATCH(); 

非常令人费解,我知道。 这是多么简单:

  • PyList_New创build一个新的列表(这主要是为新的列表对象分配内存), oparg信号oparg栈上的参数个数。 开门见山。
  • 检查if (list==NULL)没有出错。
  • 使用PyList_SET_ITEM (macros)添加位于堆栈上的任何参数(在我们的例子中,这是不执行的)。

难怪它快! 这是定制创build新的列表,没有别的:-)

CALL_FUNCTION指令:

以下是查看代码处理CALL_FUNCTION时看到的第一件事情:

 PyObject **sp, *res; sp = stack_pointer; res = call_function(&sp, oparg, NULL); stack_pointer = sp; PUSH(res); if (res == NULL) { goto error; } DISPATCH(); 

看起来很无害,对吧? 那么,不,不幸的是, call_function并不是一个直接调用函数的简单的人,它不能。 相反,它从堆栈中抓取对象,抓取堆栈的所有参数,然后根据对象的types切换; 这是一个:

  • PyCFunction_Type ? 不,它是listlist不是types的PyCFunction
  • PyMethodType ? 不,看到以前。
  • PyFunctionType ? Nopee,见前。

我们正在调用listtypes,传递给call_function的参数是PyList_Type 。 CPython现在必须调用一个通用函数来处理任何名为_PyObject_FastCallKeywords可调用对象,更多的函数调用。

这个函数再次对某些函数types(我不明白为什么)进行检查,然后在需要的时候为kwargs创build一个字典后,继续调用_PyObject_FastCallDict

_PyObject_FastCallDict终于得到我们的地方! 执行更多的检查后,它会从我们传入的typetypetp_call槽 ,也就是抓取type.tp_call 。 然后继续使用_PyStack_AsTuple传入的参数创build一个元组,最后可以调用一个调用

tp_call ,匹配type.__call__接pipe并最终创build列表对象。 它调用与__new__相对应的列表__new__ ,并使用PyType_GenericAlloc分配内存: 这实际上是 PyType_GenericAlloc 到的部分 。 以前所有的都是以通用的方式处理对象所必需的。

最后, type_call调用list.__init__并用任何可用的参数初始化列表,然后我们继续返回到我们来的方式。 🙂

最后,记住LOAD_NAME ,这是另一个在这里做出贡献的人。


很容易看出,在处理我们的input时,Python通常需要跳过这个循环才能真正find合适的C函数来完成这项工作。 它没有立即调用它的风险,因为它是dynamic的,有人可能会屏蔽list而且男孩做的很多人 ),并且必须采取另一条path。

这是list()失去很多的地方:探索Python需要做的是找出它应该做什么。

字面语法恰恰意味着一件事; 它不能改变,总是以预定的方式行事。

脚注:所有function名称可能会从一个版本更改为另一个版本。 这个观点依然存在,很有可能会在未来的版本中出现,这是dynamic查找会减慢速度。