为什么使用reversed(mylist)会很慢？

Question

为什么使用reversed(mylist)会很慢？

19

（更新：可能仅限于Windows 32位的CPython 3.8，所以如果您在其他版本中无法复制，请不要感到惊讶。请参见更新部分中的表格。）

iter 和 reversed 都会为列表产生专用迭代器：

>>> iter([1, 2, 3])
<list_iterator object at 0x031495C8>

>>> reversed([1, 2, 3])
<list_reverseiterator object at 0x03168310>

但是 reversed 的速度要慢得多：

> python -m timeit -s "a = list(range(1000))" "list(iter(a))"
50000 loops, best of 5: 5.76 usec per loop

> python -m timeit -s "a = list(range(1000))" "list(reversed(a))"
20000 loops, best of 5: 14.2 usec per loop

我能够稳定地重现此问题。后来我尝试了 iter 还有五次，并分别为 5.98、5.84、5.85、5.87 和 5.86。然后又试了五次 reversed，分别为 14.3、14.4、14.4、14.5 和 14.3。

我认为也许 iter 可以从增加列表元素的内存位置中获益，所以在此之前我尝试了对列表进行反向操作。结果一样：

> python -m timeit -s "a = list(range(1000)); a.reverse()" "list(iter(a))"
50000 loops, best of 5: 5.73 usec per loop

> python -m timeit -s "a = list(range(1000)); a.reverse()" "list(reversed(a))"
20000 loops, best of 5: 14.1 usec per loop

同样的图片，也有带有 sum 的:

> python -m timeit -s "a = list(range(1000))" "sum(iter(a))"
20000 loops, best of 5: 10.7 usec per loop

> python -m timeit -s "a = list(range(1000))" "sum(reversed(a))"
10000 loops, best of 5: 20.9 usec per loop

同样还包括相同的元素：

> python -m timeit -s "a = [None] * 1000" "list(iter(a))"
50000 loops, best of 5: 6.35 usec per loop

> python -m timeit -s "a = [None] * 1000" "list(reversed(a))"
20000 loops, best of 5: 14.5 usec per loop

为什么反向迭代器速度要慢得多？

我正在使用CPython 3.8.1 32位版本，在Windows 10 Pro 64位版本1903上，配有Intel i5-7200U（这是一款华为MateBook X笔记本电脑）。没有特别的配置，只是在普通的Windows安装上进行了普通的Python安装。

更新：我在另一台机器上（Pentium N3700，Windows 10 Pro 64位1903），使用八个不同的Python版本（均使用默认设置）运行了一个更大的自动化测试。每次循环的时间以微秒为单位。

                32-bit              64-bit
CPython     iter   reversed     iter   reversed
 3.5.4      16.6     17.0       15.2     16.2
 3.6.8      16.8     17.2       14.9     15.8
 3.7.6      16.5     16.9       14.8     15.5
 3.8.1      16.3     22.1       14.6     15.5

需要注意两点：

Python 3.8.1 32位的reversed速度较慢，这可能解释了为什么几乎没有人能够复现它。
在其他七个版本中，reversed比iter稍微慢一些，32位约为0.4微秒，64位约为0.9微秒。

我以循环赛的方式进行了16项测试，每一轮测试都是10次的，上面显示的结果是其十个源时间中最好的。每个源时间的测试方法如下：

python.exe -m timeit -r 5 -s "a = list(range(1000))" "list(iter(a))"
or
python.exe -m timeit -r 5 -s "a = list(range(1000))" "list(reversed(a))"

每个测试的时间都很稳定。完整表格（请注意，轮换是指我按列运行这些测试，而不是按行）：

3.5.4 32-bit iter     [16.7, 16.6, 17.3, 16.6, 16.7, 16.6, 16.6, 16.6, 16.6, 16.7]
3.5.4 32-bit reversed [17.1, 17.1, 17.1, 17.2, 17.1, 17.1, 17.0, 17.1, 17.1, 17.1]
3.5.4 64-bit iter     [15.2, 15.4, 15.4, 15.4, 15.4, 15.4, 15.4, 15.3, 15.4, 15.3]
3.5.4 64-bit reversed [16.8, 16.2, 16.3, 16.3, 16.2, 16.2, 16.2, 16.2, 16.2, 16.3]
3.6.8 32-bit iter     [17.3, 16.9, 16.8, 16.9, 16.9, 16.8, 16.9, 16.9, 16.8, 16.8]
3.6.8 32-bit reversed [17.2, 17.2, 17.2, 17.3, 17.3, 17.3, 17.3, 17.2, 17.2, 17.2]
3.6.8 64-bit iter     [15.0, 14.9, 15.9, 14.9, 14.9, 15.0, 14.9, 14.9, 14.9, 14.9]
3.6.8 64-bit reversed [15.8, 15.9, 16.4, 15.9, 15.9, 16.0, 15.8, 15.9, 15.9, 15.8]
3.7.6 32-bit iter     [16.6, 17.2, 16.6, 16.5, 16.7, 16.7, 16.5, 16.5, 16.5, 16.7]
3.7.6 32-bit reversed [17.2, 17.6, 17.0, 17.0, 16.9, 17.2, 17.3, 17.0, 17.5, 17.0]
3.7.6 64-bit iter     [14.8, 15.1, 14.9, 14.9, 14.8, 15.1, 14.9, 14.8, 15.0, 14.9]
3.7.6 64-bit reversed [16.0, 20.1, 15.7, 15.6, 15.6, 15.6, 15.7, 15.7, 15.8, 15.5]
3.8.1 32-bit iter     [16.4, 16.6, 16.3, 16.4, 16.5, 16.4, 16.5, 16.4, 16.8, 16.4]
3.8.1 32-bit reversed [22.3, 22.4, 22.2, 22.3, 22.3, 22.3, 22.5, 22.4, 22.3, 22.1]
3.8.1 64-bit iter     [14.6, 15.1, 14.6, 14.7, 14.7, 14.7, 14.7, 14.6, 14.6, 14.6]
3.8.1 64-bit reversed [15.5, 16.1, 15.5, 15.6, 15.5, 15.5, 15.5, 15.5, 15.5, 15.5]

对一个包含一百万个值的列表执行相同的测试 (list(range(250)) * 4000)，每次循环所需时间为毫秒：

                32-bit              64-bit
CPython     iter   reversed     iter   reversed
 3.5.4      19.8     19.9       22.4     22.7
 3.6.8      19.8     19.9       22.3     22.6
 3.7.6      19.9     19.9       22.3     22.5
 3.8.1      19.8     24.9       22.4     22.6

变化非常小，除了在32位的3.8.1上使用reversed会再次变得更慢。

还有一个问题，就是只使用CPython 3.8.0而不是3.8.1时也会出现这个问题。

                32-bit              64-bit
CPython     iter   reversed     iter   reversed
 3.5.4      19.5     19.6       21.9     22.2
 3.6.8      19.5     19.7       21.8     22.1
 3.7.6      19.5     19.6       21.7     22.0
 3.8.0      19.4     24.5       21.7     22.1

- Kelly Bundy

12

我无法再现这个问题。在两种情况下，我得到的每个循环时间都略低于3.5 微秒。在 Windows 10 上通过 Anaconda 使用 Python 3.7.4 时，在两种情况下我得到的每个循环时间都略低于4 微秒；在通过 WSL 在 Windows 10 上使用的 Ubuntu 上，我使用的是 Python 3.8.1。 - Chris

2

我在第一个例子中得到了相似的数字：3.55/3.63 ... 不过我是使用 Debian 操作系统。 - garglblarg

2

一样，我在所有设备上都得到了类似的数字，使用的是Windows 10。 - zamir

2

@HeapOverflow，我不确定。我知道这很令人沮丧；对我来说也是如此。我很想告诉你“运行命令x并向我展示输出”……你能在其他机器上重现吗？使用其他版本的Python？你尝试过在干净的虚拟环境中吗？ - Chris

6

如果您是唯一能够重现此问题的人，但又不想付出努力，就不要指望别人为您解决。虽然您可能不想为此安装其他软件。 - Acorn

显示剩余28条评论

2个回答

-1

我一直在查看Python文档，发现了这段内容：

如果未提供__reversed__（）方法，则内置的reversed（）将回退到使用序列协议（__len__（）和__getitem__（））。支持序列协议的对象只应提供__reversed__（）如果它们可以提供比reversed（）提供的更高效的实现。

很可能是因为这个原因。

虽然我不是专家，但我看到这个问题已经7个月没有答案，所以根据Python文档尝试给出了一个答案。

这些是我使用的资源：

https://docs.python.org/3/library/functions.html#reversed https://docs.python.org/3/reference/datamodel.html#object

- David Garcia Ricou

3

不太确定您的意思。列表确实提供了一个__reversed__方法。正如我所说并展示的那样，iter和reversed都会为列表生成专用迭代器。 - Kelly Bundy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Raymond Hettinger · Accepted Answer

无法重现显著差异

我已经在使用从python.org下载的Python 3.9和Python 3.11的标准macOS构建版上尝试了这个问题。计时显示正向和反向迭代的运行速度接近：

% python3.11 -m timeit -s "a = list(range(1000))" "list(iter(a))"
100000 loops, best of 5: 2.84 usec per loop
% python3.11 -m timeit -s "a = list(range(1000))" "list(reversed(a))"
100000 loops, best of 5: 2.85 usec per loop

% python3.9 -m timeit -s "a = list(range(1000))" "list(iter(a))"
100000 loops, best of 5: 2.87 usec per loop
% python3.9 -m timeit -s "a = list(range(1000))" "list(reversed(a))"
100000 loops, best of 5: 2.91 usec per loop

源代码

检查C语言源代码可以发现，list_iterator和list_reverseiterator的代码几乎完全相同。

预期反向迭代器会稍微慢一些，原因如下：

反向迭代的循环终止逻辑有两个条件 index>=0 && index < PyList_GET_SIZE(seq)，而正向迭代只有一个条件 it->it_index < PyList_GET_SIZE(seq)。
某些CPU上的内存访问控制器在正向遍历数组时会自动发出预取操作，但在反向遍历时不会。详见Agner Fog的《汇编优化子例程》第12.1节“优化缓存”。

变异来源

由于源代码几乎相同，变异的原因可能是编译和构建过程。

也许Windows编译器可以更好地优化正向迭代，因为它有更简单的循环终止条件。
更可能的原因是Windows版本正在使用Profile Guided Optimization (PGO)来通知代码生成步骤。这对profile的构建方式非常敏感。如果profiled code几乎没有使用反向迭代器，那么它将无法从PGO中受益。

通常的建议是重新运行PGO，使用你关心的代码而不仅仅是测试套件。这将调整构建以满足您的特定需求。

更好的基准测试

range()创建的连续整数往往是小对象，并且在连续的内存位置上布置。

此外，少量迭代的时间往往还包括对list、iter和reversed的调用开销。

为了进行更好的基准测试，我会使用一个更大、打乱顺序的数据集，由更有趣的对象组成。此外，我会跳过在循环中包含list()，这样计时就可以专注于迭代而不是列表构建。

from timeit import repeat

setup = '''
from random import randrange
from random import randrange, shuffle
data = [str(randrange(100_000)) for i in range(10_000)]
shuffle(data)
'''

forward = 'for x in iter(data): pass'

backward = 'for x in reversed(data): pass'

以下是两个运行：

>>> min(repeat(forward, setup, repeat=7, number=100_000))
4.0327267500106245

>>> min(repeat(backward, setup, repeat=7, number=100_000))
4.094246666994877