当列表包含多个重复项时，为什么复制简单对象列表会变慢？
Kar*_*tel 9 python performance list
这是我的环境：
$ python
Python 3.8.10 (default, Nov 14 2022, 12:59:47)
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> quit()
$ lscpu | grep "Model name"
Model name: Intel(R) Core(TM) i5-4430 CPU @ 3.00GHz
$ sudo dmidecode --type memory | grep -E "^\\s+(Speed|Type):" -
Type: DDR3
Speed: 1600 MT/s
Type: DDR3
Speed: 1600 MT/s
我在我的机器上始终得到如下计时结果：
$ python -m timeit -s "x = list(range(250)) * 4" "[*x]"
200000 loops, best of 5: 1.54 usec per loop
$ python -m timeit -s "x = [0, 1, 2, 3] * 250" "[*x]"
200000 loops, best of 5: 1.48 usec per loop
$ python -m timeit -s "x = [0, 1] * 500" "[*x]"
100000 loops, best of 5: 2 usec per loop
$ python -m timeit -s "x = [0] * 1000" "[*x]"
100000 loops, best of 5: 3.84 usec per loop
（这里我刻意避免使用大于255的整数，因为我了解小整数的缓存。
同样，对于单字符字符串：
$ python -m timeit -s "x = [chr(i) for i in range(250)] * 4" "[*x]"
200000 loops, best of 5: 1.81 usec per loop
$ python -m timeit -s "x = [chr(0), chr(1), chr(2), chr(3)] * 250" "[*x]"
200000 loops, best of 5: 1.5 usec per loop
$ python -m timeit -s "x = [chr(0), chr(1)] * 500" "[*x]"
100000 loops, best of 5: 2.03 usec per loop
$ python -m timeit -s "x = [chr(0)] * 1000" "[*x]"
100000 loops, best of 5: 3.83 usec per loop
（再次，我故意限制字符代码点，以便 Python灵活的字符串表示形式将选择一致的、每个字符单字节的表示形式。）
所有这些输入列表的长度都是 1000，并且使用相同的方法来复制它们，因此我预计时间上不会有显着差异。然而，我发现一遍又一遍地包含相同简单元素（单字符字符串或小整数）的列表，复制所需的时间几乎是其他列表的两倍；使用几个不同的值甚至比使用两个交替值更快；并且使用各种值又会稍微慢一些。
对于较慢的复制方法，差异仍然存在，但不那么明显：
$ python -m timeit -s "x = [chr(i) for i in range(250)] * 4" "[i for i in x]"
20000 loops, best of 5: 18.2 usec per loop
$ python -m timeit -s "x = [chr(0), chr(1), chr(2), chr(3)] * 250" "[i for i in x]"
20000 loops, best of 5: 17.3 usec per loop
$ python -m timeit -s "x = [chr(0), chr(1)] * 500" "[i for i in x]"
20000 loops, best of 5: 17.9 usec per loop
$ python -m timeit -s "x = [chr(0)] * 1000" "[i for i in x]"
20000 loops, best of 5: 19.1 usec per loop
为什么会出现这种情况？
Jér*_*ard 10
TL;DR：性能差距是由于与现代处理器执行指令的方式相关的复杂低级效应造成的。更准确地说，性能取决于与目标列表中的对象数量相关的可以并行执行的存储转发操作的数量：对象越多，独立的指令就越多，因此可以并行执行的指令就越多，并且待执行指令的依赖链的较小关键路径。
\n\n
要了解发生了什么，我们首先需要分析处理器执行的汇编代码是什么。我们还需要很好地了解现代处理器的工作原理。最后，深入分析可以帮助我们理清究竟发生了什么。
\n\n
配置和再现性
\n在我的机器上，我能够使用 CPython 3.8.1、i5-9600KF 处理器和两个 RAM DIMM @ 3200 MHz (CL16) 在 Windows 10 上重现该问题。以下是时间安排：
\n1.35 \xc2\xb5s \xc2\xb1 51.7 ns per loop (mean \xc2\xb1 std. dev. of 1000 runs, 2000 loops each)\n1.24 \xc2\xb5s \xc2\xb1 50.6 ns per loop (mean \xc2\xb1 std. dev. of 1000 runs, 2000 loops each)\n1.41 \xc2\xb5s \xc2\xb1 54 ns per loop (mean \xc2\xb1 std. dev. of 1000 runs, 2000 loops each)\n2.49 \xc2\xb5s \xc2\xb1 89.8 ns per loop (mean \xc2\xb1 std. dev. of 1000 runs, 1000 loops each)\n\n
高级分析和执行的汇编代码
\n在所有情况下，两个函数占用了大部分计算时间。这两个函数包含一个热循环，几乎占用了基准测试的所有执行时间。以下是最慢的汇编代码（约 53% 的时间）：
\n0x180053f50 Block 10:\n0x180053f50 mov rcx, qword ptr [rdx+rax*1]\n0x180053f54 lea rax, ptr [rax+0x8]\n0x180053f58 inc rbx\n0x180053f5b inc qword ptr [rcx]\n0x180053f5e mov qword ptr [rax-0x8], rcx\n0x180053f62 cmp rbx, rdi\n0x180053f65 jl 0x18053f50 <Block 10>\n对于那些不太熟悉汇编语言的人，这里有一个类似 C 的代码执行类似的操作：
\nuint64_t rdx = ...;\nuint64_t rax = ...;\n\nfor(uint64_t rbx=0 ; rbx<rdi ; ++rbx)\n{\n uint64_t* rcx = *(uint64_t*)(rdx+rax); // Read an array item (list reference?)\n rax += 8;\n (*rcx)++; // Increment the number of reference of the object?\n *(uint64_t*)(rax-8) = rcx; // Write the item in another array (list reference?)\n}\n这是速度最快的一个（约 37% 的时间）：
\n0x180058691 Block 11: \n0x180058691 mov rbx, qword ptr [rsi+0x18]\n0x180058695 mov rbx, qword ptr [rbx+rdi*8]\n0x180058699 test rbx, rbx\n0x18005869c jz 0x1800586a8 <Block 13>\n\n0x18005869e Block 12:\n0x18005869e sub qword ptr [rbx], 0x1\n0x1800586a2 jz 0x180058764 <Block 26> (almost no jump: block returning\n the result of the function)\n\n0x1800586a8 Block 13:\n0x1800586a8 sub rdi, 0x1\n0x1800586ac jns 0x180058691 <Block 11>\n [...]\n\n同样，这里有一个类似的类似 C 的代码，可以更好地理解热循环的实际作用：
\nfor(uint64_t rdi=... ; rdi>0 ; --rdi)\n{\n uint64_t* tmp = *(uint64_t*)(rsi + 0x18);\n uint64_t* rbx = tmp[rdi];\n\n if(rbx != NULL)\n {\n // rbx is certainly a pointer to an object and \n // *rbx is certainly the number of references.\n // If there is no reference on the object, \n // then we (temporary?) stop the loop \n // (very rare case in practice).\n if(--(*rbx) == 0)\n goto Block26;\n }\n}\n\nBlock26:\n // Make few checks and call a function which\n // certainly deallocates the object.\n // Can jump back in the loop or stop the functions\n // regarding a complex set of conditional branches.\n请注意，剩余的大部分时间 (~10%) 花费在CancelloExCPython 当然（间接）调用的函数中，以便跟踪计算中间的中断（以便 Ctrl+C 可以快速停止计算）。
当重复列表中的项目数量较小时，很少有指令会变得比其他指令明显慢，并且它们显然正在成为瓶颈。
\n\n
现代处理器工作原理概述
\n在尝试分析处理器执行此代码时发生的情况之前，我们需要了解有关现代主流处理器工作原理的一些知识。由于指令级并行性(ILP) 与乱序执行(OoO)相结合，现代 x86-64 处理器能够同时执行多个指令。可以独立于其他指令并行执行的指令非常便宜，而依赖链上的指令则要昂贵得多，特别是当它们与内存层次结构交互时（由于内存操作的延迟相对较高）。\n事实上，这有点复杂，因为指令不是直接执行的：它们被分成一个或多个微指令（uop）。某些指令可以进行宏融合，以便处理器将其作为唯一的大指令读取。一些微指令也可以融合。\n微指令被调度到多个可以并行计算的计算单元（端口）上。某些端口专门用于执行某些特定指令（例如，仅分支、仅内存读取）。\n处理器可以预测具有可预测行为的条件分支，因此在这种情况下跳转几乎是免费的，尤其是当它跳转到附近位置时（并且目标指令已经在指令缓存中）。
\n\n
低级分析
\n我们可以使用精确的硬件性能计数器与基于采样的分析器相结合，以便找出每种情况下哪个指令实际上是瓶颈（Windows 上的 VTune 和 Linux 上的 Perf 可以做到这一点）。
\n这是第一种情况的结果（快速）：
\n
这是最后一个的结果（慢）：
\n
我将两个循环中最慢的指令（远远超过）用蓝色表示。右侧提供了指导费用。绝对时间并不重要：主要重要的是一条指令相对于其他指令所花费的时间。
\n\n
低级分析结果分析
\n在最慢的函数中，我们可以看到两条指令是瓶颈，特别是在最后一个基准测试中：inc rbx和mov qword ptr [rax-0x8], rcx。inc rbx通常很便宜（1 个周期），但位于依赖链的关键路径上。因此，它可以限制与可用端口上的微指令调度有关的环路速度。话虽如此，这条指令没有理由在上一个基准测试中成为一个更大的问题。事实上，在上一次基准测试中，该指令所花费的相对时间更小，因为它更慢。然而，第二条指令变得相对慢得多：这是该函数的真正瓶颈。
人们应该记住，处理器与（非常大的）OoO 窗口并行执行指令。因此，实际上，一条指令可以被报告为处理器停顿的指令，而它实际上受到前一相关指令的限制。结果，inc qword ptr [rcx]可要为对方的慢负责。事实上，对于上面的逆向工程 C 代码，我们可以推断出这rcx是一个指向来自初始重复列表的对象之一的指针。问题是在同一个缓存行中将同一变量递增 4 次比递增 4 个不同变量要慢，特别是如果它们位于现代 x86-64 处理器（至少是 Intel 处理器）上的 4 个不同缓存行上。这是因为 L1 缓存的延迟通常为 3-4 个周期，并且必须付出延迟来读取值，然后写入、再次读取等等。
但请注意，现代 x86-64 处理器能够更快地从缓存中读取最近写入的变量。事实上，处理器可以检测依赖性，并且可以将值从寄存器传输到另一个寄存器，而不是从缓存重新加载数据，从而减少写入+读取的延迟。不过，这种称为存储转发的操作并不是免费的。AFAIK，在最新的 Intel 处理器上，此类操作的延迟通常为 4-5 个周期，因此它只是减轻了开销，但延迟足够大，足以成为主要瓶颈（对于此功能）。有关更多信息，请阅读这篇关于缓存和存储转发的文章，甚至这篇关于存储转发的精彩文章。
\n关于第二个函数，我们可以使用相同的逻辑并得出结论，这jz 0x180058764 <Block 26>肯定是主要瓶颈，因为由于sub qword ptr [rbx], 0x1相同的原因，它也很昂贵：存储转发操作的并行度限制了循环的速度。当初始列表中只有一个对象时，要执行的指令的依赖链的关键路径会更长。
请注意，5 个周期的循环迭代执行两次会产生一次结果2*5*1000/4.5e9 = 2.22 \xc2\xb5s。这与上一次基准测试（单个对象）的实验结果一致。请注意，其他指令大部分可以并行执行（即我们不能简单地添加计时）。对于两个对象，时间为 1.11 \xc2\xb5s，并且处理器可以更好地与许多指令重叠延迟（尽管它并不完美）。对于 4 个或更多对象，存储转发的延迟大部分应与其他指令重叠。这解释了为什么低级分析结果显示更多指令是处理器停止的指令。这些存储仍然相对昂贵，因为我的处理器每个周期只能执行 1 个存储，更不用说处理器跟踪循环中所有其他读取的依赖性（并使用推测来加快速度）。
| 归档时间： |
|
| 查看次数： |
269 次 |
| 最近记录： |