为什么线性读取-随机写入不比随机读取-线性写入快？
Why is linear read-shuffled write not faster than shuffled read-linear write?
我目前正在努力更好地了解 memory/cache 相关的性能问题。我在某处读到内存局部性对于读取比写入更重要，因为在前一种情况下 CPU 必须实际等待数据，而在后一种情况下它可以将它们发送出去并忘记它们。
考虑到这一点，我进行了以下快速而简单的测试：我编写了一个脚本来创建一个包含 N 个随机浮点数和一个排列的数组，即随机包含数字 0 到 N-1 的数组命令。然后它重复（1）线性读取数据数组并将其以排列给出的随机访问模式写回新数组或（2）以排列顺序读取数据数组并将其线性写入新数组。
令我惊讶的是 (2) 似乎始终比 (1) 快。但是，我的脚本有问题
- 脚本是在python/numpy中编写的。这是一种相当高级的语言，尚不清楚 read/write 的实现有多精确。
- 我可能没有正确平衡这两种情况。
此外，下面的一些 answers/comments 表明我最初的期望是不正确的，并且根据 cpu 缓存的详细信息，这两种情况都可能更快。
我的问题是：
- 两者中哪一个（如果有的话）应该更快？
- 这里有哪些相关的缓存概念；他们如何影响结果
初学者友好的解释将不胜感激。任何支持代码都应该在 C / cython / numpy / numba 或 python.
中
可选：
- 解释为什么绝对持续时间在问题规模上是非线性的（参见下面的计时）。
- 解释我明显不充分的 python 实验的行为。
供参考，我的平台是Linux-4.12.14-lp150.11-default-x86_64-with-glibc2.3.4。 Python 版本是 3.6.5.
这是我写的代码：
import numpy as np
from timeit import timeit
def setup():
global a, b, c
a = np.random.permutation(N)
b = np.random.random(N)
c = np.empty_like(b)
def fwd():
c = b[a]
def inv():
c[a] = b
N = 10_000
setup()
timeit(fwd, number=100_000)
# 1.4942631321027875
timeit(inv, number=100_000)
# 2.531870319042355
N = 100_000
setup()
timeit(fwd, number=10_000)
# 2.4054739447310567
timeit(inv, number=10_000)
# 3.2365565397776663
N = 1_000_000
setup()
timeit(fwd, number=1_000)
# 11.131387163884938
timeit(inv, number=1_000)
# 14.19817715883255
正如@Trilarion 和@Yann Vernier 指出的那样，我的片段没有得到适当的平衡，因此我将它们替换为
def fwd():
c[d] = b[a]
b[d] = c[a]
def inv():
c[a] = b[d]
b[a] = c[d]
where d = np.arange(N)（我以两种方式随机播放所有内容以希望减少跨试验缓存效果）。我还将 timeit 替换为 repeat 并将重复次数减少了 10 倍。
然后我得到
[0.6757169323973358, 0.6705542299896479, 0.6702114241197705] #fwd
[0.8183442652225494, 0.8382121799513698, 0.8173762648366392] #inv
[1.0969422250054777, 1.0725746559910476, 1.0892365919426084] #fwd
[1.0284497970715165, 1.025063106790185, 1.0247828317806125] #inv
[3.073981977067888, 3.077839042060077, 3.072118630632758] #fwd
[3.2967213969677687, 3.2996009718626738, 3.2817375687882304] #inv
因此似乎仍然存在差异，但它更加微妙，现在可以根据问题的大小进行选择。
- 首先反驳您的直觉：即使没有 numpy 机制，
fwd 也胜过 inv。
这个numba版本就是这样：
import numba
@numba.njit
def fwd_numba(a,b,c):
for i in range(N):
c[a[i]]=b[i]
@numba.njit
def inv_numba(a,b,c):
for i in range(N):
c[i]=b[a[i]]
N=10000 的时间：
%timeit fwd()
%timeit inv()
%timeit fwd_numba(a,b,c)
%timeit inv_numba(a,b,c)
62.6 µs ± 3.84 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
144 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
16.6 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
34.9 µs ± 1.57 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
- 其次，Numpy 必须处理可怕的对齐和（缓存）局部性问题。
它本质上是对来自 BLAS/ATLAS/MKL 的低级别程序的包装器，为此进行了调整。
花哨的索引是一个很好的高级工具，但对于这些问题来说是异端；在低层次上没有直接翻译这个概念。
- 第三，numpy dev docs : 详细介绍花式索引。特别是：
Unless there is only a single indexing array during item getting, the
validity of the indices is checked beforehand. Otherwise it is handled
in the inner loop itself for optimization.
我们这里就是这种情况。我认为这可以解释差异，以及为什么 set 比 get 慢。
这也解释了为什么手工制作的 numba 通常更快：它不检查任何内容并在索引不一致时崩溃。
您的函数 fwd 没有触及全局变量 c。你没有告诉它global c（只在setup），所以它有自己的局部变量，在cpython中使用STORE_FAST：
>>> import dis
>>> def fwd():
... c = b[a]
...
>>> dis.dis(fwd)
2 0 LOAD_GLOBAL 0 (b)
3 LOAD_GLOBAL 1 (a)
6 BINARY_SUBSCR
7 STORE_FAST 0 (c)
10 LOAD_CONST 0 (None)
13 RETURN_VALUE
现在，让我们用全局试试：
>>> def fwd2():
... global c
... c = b[a]
...
>>> dis.dis(fwd2)
3 0 LOAD_GLOBAL 0 (b)
3 LOAD_GLOBAL 1 (a)
6 BINARY_SUBSCR
7 STORE_GLOBAL 2 (c)
10 LOAD_CONST 0 (None)
13 RETURN_VALUE
即便如此，与为全局调用 setitem 的 inv 函数相比，它在时间上可能有所不同。
无论哪种方式，如果你想让它把 写成 c，你需要像 c[:] = b[a] 或 c.fill(b[a]) 这样的东西。赋值将变量（名称）替换为右侧的对象，因此旧的 c 可能会被释放而不是新的 b[a]，并且这种内存改组可能代价高昂。
至于我认为您想衡量的效果，基本上是正向排列还是反向排列的成本更高，这将高度依赖于缓存。前向置换（从线性读取存储在随机排序的索引处）原则上可能更快，因为它可以使用写掩码并且永远不会获取新数组，假设缓存系统足够智能以在写缓冲区中保留字节掩码。如果数组足够大，则在执行随机读取时向后运行缓存冲突的风险很高。
这是我的初步印象；正如你所说，结果是相反的。这可能是缓存实现没有大写缓冲区或无法利用小写的结果。如果超出缓存的访问无论如何都需要相同的内存总线时间，则读取访问将有机会加载不会在需要之前从缓存中删除的数据。使用多路缓存，部分写入的行也将有机会不被选择驱逐；并且只有脏缓存行需要内存总线时间来丢弃。使用其他知识（例如，排列是完整的且不重叠的）编写的较低级别的程序可以使用非时间 SSE 写入等提示来改进行为。
以下实验证实了随机写入比随机读取更快。对于小数据（当它完全适合缓存时）随机写入代码比随机读取慢（可能是因为 numpy 中的某些实现特性），但随着数据大小的增长，最初的 1.7 倍执行时间的差异几乎完全消除（但是，在 numba 的情况下，最终趋势出现了奇怪的逆转）。
$ cat test.py
import numpy as np
from timeit import timeit
import numba
def fwd(a,b,c):
c = b[a]
def inv(a,b,c):
c[a] = b
@numba.njit
def fwd_numba(a,b,c):
for i,j in enumerate(a):
c[i] = b[j]
@numba.njit
def inv_numba(a,b,c):
for i,j in enumerate(a):
c[j] = b[i]
for p in range(4, 8):
N = 10**p
n = 10**(9-p)
a = np.random.permutation(N)
b = np.random.random(N)
c = np.empty_like(b)
print('---- N = %d ----' % N)
for f in 'fwd', 'fwd_numba', 'inv', 'inv_numba':
print(f, timeit(f+'(a,b,c)', number=n, globals=globals()))
$ python test.py
---- N = 10000 ----
fwd 1.1199337750003906
fwd_numba 0.9052993479999714
inv 1.929507338001713
inv_numba 1.5510062070025015
---- N = 100000 ----
fwd 1.8672701190007501
fwd_numba 1.5000483989970235
inv 2.509873716000584
inv_numba 2.0653326050014584
---- N = 1000000 ----
fwd 7.639554155000951
fwd_numba 5.673054756000056
inv 7.685382894000213
inv_numba 5.439735023999674
---- N = 10000000 ----
fwd 15.065879136000149
fwd_numba 12.68919651500255
inv 15.433822674000112
inv_numba 14.862108078999881
你的两个 NumPy 片段 b[a] 和 c[a] = b 似乎是测量 shuffled/linear read/write 速度的合理启发式方法，因为我将尝试通过查看底层来争论下面第一部分中的 NumPy 代码。
关于哪个应该更快的问题，随机读取线性写入通常会获胜似乎是合理的（正如基准似乎显示的那样），但速度差异可能受到 "shuffled" 打乱后的索引是，并且以下一项或多项：
- CPU 缓存 read/update 策略（write-back vs. write-through 等）。
- CPU 如何选择（重新）排序它需要执行的指令（流水线）。
- CPU 识别内存访问模式和预取数据。
- 缓存逐出逻辑。
即使假设哪些政策已经到位，这些影响也很难建模和推理分析，所以我不确定适用于所有处理器的一般答案是否可能（尽管我不是硬件专家).
尽管如此，在下面的第二部分中，我将尝试推理为什么随机读取线性写入明显更快，给出一些假设。
"Trivial" 花式索引
本节的目的是通过 NumPy 源代码来确定是否有任何明显的时间解释，并尽可能清楚地了解 A[B] 或 [= 时会发生什么15=] 被执行。
支持 getitem and setitem operations in this question is "trivial 花式索引的迭代例程":
B 是单步长的单索引数组A 和 B 具有相同的内存顺序（均为 C 连续或均为 Fortran 连续）
此外，在我们的例子中 A 和 B 都是 Uint Aligned:
Strided copy code: Here, "uint alignment" is used instead. If the itemsize [N] of an array is equal to 1, 2, 4, 8 or 16 bytes and the array is uint aligned then instead [of using buffering] numpy will do *(uintN*)dst) = *(uintN*)src) for appropriate N. Otherwise numpy copies by doing memcpy(dst, src, N).
这里的重点是避免使用内部缓冲区来确保对齐。使用 *(uintN*)dst) = *(uintN*)src) 实现的底层复制与 "put the X bytes from offset src into the X bytes at offset dst".
一样简单
编译器可能会将其非常简单地转换为 mov 指令（例如在 x86 上）或类似指令。
执行项目获取和设置的核心底层代码在函数mapiter_trivial_get和mapiter_trivial_set中。这些函数是在 lowlevel_strided_loops.c.src 中生成的，其中的模板和宏使其阅读起来有些困难（感谢高级语言）。
坚持不懈，终于可以看出getitem和setitem的差别不大。这是用于说明的主循环的简化版本。宏行确定是 运行 getitem 还是 setitem:
while (itersize--) {
char * self_ptr;
npy_intp indval = *((npy_intp*)ind_ptr);
#if @isget@
if (check_and_adjust_index(&indval, fancy_dim, 0, _save) < 0 ) {
return -1;
}
#else
if (indval < 0) {
indval += fancy_dim;
}
#endif
self_ptr = base_ptr + indval * self_stride; /* offset into array being indexed */
#if @isget@
*(npy_uint64 *)result_ptr = *(npy_uint64 *)self_ptr;
#else
*(npy_uint64 *)self_ptr = *(npy_uint64 *)result_ptr;
#endif
ind_ptr += ind_stride; /* move to next item of index array */
result_ptr += result_stride; /* move to next item of result array */
正如我们所料，这只是一些算术运算，以获得数组中的正确偏移量，然后将字节从一个内存位置复制到另一个内存位置。
setitem 的额外索引检查
值得一提的是，对于setitem，索引的有效性（是否都是目标数组的入站）是checked before copying begins (via check_and_adjust_index），这也将负索引替换为相应的正索引。
在上面的代码片段中，您可以看到 check_and_adjust_index 在主循环中调用了 getitem，而对 setitem 进行了更简单（可能是冗余）的负索引检查。
这个额外的初步检查可能会对 setitem (A[B] = C) 的速度产生很小但负面的影响。
缓存未命中
因为两个代码片段的代码非常相似，所以怀疑落在 CPU 以及它如何处理对底层内存数组的访问。
CPU 缓存最近访问过的小内存块（缓存行），预计它可能很快需要再次访问该内存区域。
对于上下文，缓存行一般为64字节。我老旧的笔记本电脑 CPU 上的 L1（最快）数据缓存是 32KB（足以容纳数组中的大约 500 个 int64 值，但请记住 CPU 将做其他需要其他内存的事情，同时NumPy 片段执行):
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K
您可能已经知道，对于 reading/writing 内存顺序缓存效果很好，因为 64 字节的内存块会根据需要获取并存储在更靠近 CPU 的位置。重复访问该内存块比从 RAM（或更慢的高级缓存）中获取更快。事实上，CPU 甚至可以在程序请求之前抢先获取下一个缓存行。
另一方面，随机访问内存很可能导致频繁的缓存未命中。这里，具有所需地址的内存区域不在 CPU 附近的快速缓存中，而是必须从更高级别的缓存（较慢）或实际内存（慢得多）访问。
那么 CPU 处理哪个更快：频繁的数据读取未命中，还是数据写入未命中？
让我们假设CPU的写策略是回写，这意味着修改的内存被写回缓存。缓存被标记为正在修改（或 "dirty"），只有当行从缓存中被逐出时，更改才会被写回主内存（CPU 仍然可以从脏缓存中读取线）。
如果我们写入一个大数组中的随机点，预计 CPU 缓存中的许多缓存行将变脏。需要写入主内存，因为每个内存都被逐出，如果缓存已满，这可能经常发生。
但是，当顺序写入数据并随机读取数据时，这种写通应该不会那么频繁地发生，因为我们希望更少的缓存行变脏，并且数据回写到主内存或更慢的缓存的频率更低。
如前所述，这是一个简化模型，可能还有许多其他因素会影响 CPU 的性能。比我更专业的人可能会改进这个模型。
这是一个复杂的问题，与现代处理器的架构特征和您的直觉密切相关 随机读取比随机写入慢，因为 CPU 必须等待读取数据
未经验证（大部分时间）。我将详细说明几个原因。
现代处理器可以非常有效地隐藏读取延迟
而内存写入比内存读取更昂贵
尤其是在多核环境下
原因 #1 现代处理器可以有效隐藏读取延迟。
现代 superscalar can execute several instructions simultaneously, and change instruction execution order (out of order execution)。
虽然这些功能的首要原因是增加指令吞吐量，
最有趣的结果之一是处理器隐藏内存写入（或复杂运算符、分支等）延迟的能力。
为了解释这一点，让我们考虑一个将数组复制到另一个数组的简单代码。
for i in a:
c[i] = b[i]
编译后，处理器执行的代码会有点像那样
#1. (iteration 1) c[0] = b[0]
1a. read memory at b[0] and store result in register c0
1b. write register c0 at memory address c[0]
#2. (iteration 2) c[1] = b[1]
2a. read memory at b[1] and store result in register c1
2b. write register c1 at memory address c[1]
#1. (iteration 2) c[2] = b[2]
3a. read memory at b[2] and store result in register c2
3b. write register c2 at memory address c[2]
# etc
（这太过简化了，实际代码更复杂，需要处理循环管理、地址计算等，但这种简单的模型目前已经足够了）。
如问题中所述，对于读取，处理器必须等待实际数据。的确，1b需要1a取来的数据，只要1a没有完成就不能执行。这样的约束称为 dependency，我们可以说 1b 依赖于 1a。依赖关系是现代处理器中的一个主要概念。依赖关系表示算法（例如，我将 b 写成 c）并且必须绝对遵守。但是，如果指令之间没有依赖关系，处理器将尝试执行其他挂起的指令，以保持可操作的流水线始终处于活动状态。这可以导致执行 out-of-order，只要遵守依赖关系（类似于 as-if 规则）。
对于所考虑的代码，高级指令 2. 和 1. 之间（或 asm 指令 2a 和 2b 与之前的指令之间）没有 依赖性。实际上，最终结果甚至是相同的，即 2. 在 1. 之前执行，处理器将在 1a 和 1b 完成之前尝试执行 2a 和 2b。 2a和2b之间还是有依赖关系，但是都可以下发。 3a 也类似。和 3b.，等等。这是隐藏内存延迟 的有力手段。如果由于某种原因 2.、3. 和 4. 可以在 1. 加载其数据之前终止，您甚至可能根本不会注意到任何减速。
此指令级并行性由处理器中的一组 "queues" 管理。
保留站RS中的待处理指令队列（在最近的奔腾中类型为128μ指令）。只要指令所需的资源可用（例如指令 1b 的寄存器 c1 的值），指令就可以执行。
L1 高速缓存之前的内存顺序缓冲区 MOB 中的待处理内存访问队列。这是处理内存别名和确保同一地址的内存写入或加载的顺序性所必需的（典型值 64 次加载，32 次存储）
出于类似原因，在寄存器（重新排序缓冲区或 168 个条目的 ROB）中写回结果时强制执行顺序的队列。
和指令获取时的一些其他队列，用于 μops 生成，缓存中的写入和未命中缓冲区等
在执行前一个程序的某一时刻，RS 中将有许多挂起的存储指令，MOB 中有多个加载指令，ROB 中有等待退出的指令。
一旦数据可用（例如读取终止），相关指令就可以执行并释放队列中的位置。但是，如果没有终止发生，并且这些队列之一已满，则与该队列关联的功能单元将停止（如果处理器缺少寄存器名称，这也可能发生在指令发出时）。停顿会造成性能损失，为避免这种情况，必须限制队列填充。
这解释了线性和随机内存访问之间的区别。
在线性访问中，1/ 由于空间局部性更好，并且缓存可以使用常规模式预取访问以进一步减少未命中数，因此 1/ 未命中数会更小，并且 2/ 每当读取终止时，它将涉及完整的缓存行和可以释放几个挂起的加载指令，限制指令队列的填充。这样处理器就会一直处于忙碌状态，并且内存延迟会被隐藏。
对于随机访问，未命中数会更高，数据到达时只能服务单次负载。因此，指令队列将迅速饱和，处理器停顿和内存延迟无法再通过执行其他指令来隐藏。
处理器架构必须在吞吐量方面保持平衡，以避免队列饱和和停顿。事实上，在处理器的某个执行阶段通常有数十条指令，全局吞吐量（即内存（或功能单元）处理指令请求的能力）是决定性能的主要因素。事实上，这些未决指令中的一些正在等待内存值的影响很小...
...除非你有很长的依赖链。
当一条指令必须等待前一条指令完成时，存在依赖关系。使用读取的结果是一种依赖。当涉及依赖链时，依赖关系可能会成为问题。
例如，考虑代码 for i in range(1,100000): s += a[i]。所有的内存读取都是独立的，但是在s中的积累有一个依赖链。在前一个终止之前，不会发生任何添加。这些依赖性将使保留站迅速填满并在管道中造成停顿。
但是读取很少涉及依赖链。仍然可以想象所有读取都依赖于前一个读取的病态代码（例如 for i in range(1,100000): s = a[s]），但它们在实际代码中并不常见。而且问题出在依赖链上，而不是因为它是一个读；这种情况与 for i in range(1,100000): x = 1.0/x+1.0.
等计算绑定相关代码类似（甚至可能更糟）
因此，除了在某些情况下，计算时间与吞吐量的相关性比与读取依赖性的相关性更高，这要归功于超标量输出或订单执行隐藏了延迟这一事实。就吞吐量而言，写入比读取更差。
原因 #2：内存写入（尤其是随机写入）比内存读取更昂贵
这与 caches 的行为方式有关。缓存是快速内存，由处理器存储一部分内存（称为行）。缓存行目前为 64 字节，并允许利用内存引用的空间局部性：一旦存储了一行，该行中的所有数据都立即可用。这里的重要方面是缓存和内存之间的所有传输都是行。
当处理器对数据执行读取时，缓存会检查数据所属的行是否在缓存中。如果不是，则从内存中获取该行，将其存储在缓存中，并将所需数据发送回处理器。
当处理器将数据写入内存时，缓存也会检查行是否存在。如果该行不存在，则缓存无法将其数据发送到内存（因为所有 传输都是基于行的）并执行以下步骤：
- 缓存从内存中获取行并将其写入缓存行。
- 数据写入缓存，整行标记为已修改（脏）
- 当一行从缓存中被抑制时，它会检查修改标志，如果该行已被修改，它会将其写回内存（回写缓存）
因此，每次内存写入都必须先进行内存读取，才能获取缓存中的行。这增加了一个额外的操作，但对于线性写入来说并不是很昂贵。第一个写入的字会出现缓存未命中和内存读取，但连续的写入只会涉及缓存并被命中。
但是随机写的情况就大不相同了。如果未命中数很重要，则每次缓存未命中都意味着在行从缓存中弹出之前先进行一次读取，然后仅进行少量写入，这会显着增加写入成本。如果单次写入后弹出一行，我们甚至可以认为写入的时间成本是读取的两倍。
请务必注意，增加内存访问（读取或写入）的次数往往会使内存访问路径饱和，并全局减慢处理器和内存之间的所有传输。
在任何一种情况下，写入总是比读取更昂贵。多核增强了这方面。
原因 #3：随机写入会在多核中造成缓存未命中
不确定这是否真的适用于问题的情况。虽然 numpy BLAS 例程是多线程的，但我认为基本数组复制不是。但它是密切相关的，也是写入更昂贵的另一个原因。
多核的问题是确保适当 cache coherence in such a way that a data shared by several processors is properly updated in the cache of every core. This is done by mean of a protocol such as MESI 在写入之前更新缓存行，并使其他缓存副本无效（读取所有权）。
虽然 none 数据实际上在问题（或其并行版本）之间共享，但请注意该协议适用于 缓存行 。每当要修改缓存行时，都会从保存最新副本的缓存中复制它，本地更新和所有其他副本无效。即使核心正在访问缓存行的不同部分。这种情况称为false sharing，是多核编程的重要问题。
关于随机写的问题，cache line是64字节，可以容纳8个int64，如果电脑是8核，平均每个核会处理2个值。因此有一个重要的错误共享会减慢写入速度。
我们做了一些性能评估。它是在 C 中执行的，以便包括对并行化影响的评估。我们比较了 5
处理大小为 N.
的 int64 数组的函数
只是 b 到 c 的一个副本 (c[i] = b[i])（由编译器用 memcpy() 实现）
用线性索引复制 c[i] = b[d[i]] 其中 d[i]==i (read_linear)
用随机索引复制 c[i] = b[a[i]] 其中 a 是随机的
0..N-1的排列（read_random等同于原题中的fwd）
写线性 c[d[i]] = b[i] 其中 d[i]==i (write_linear)
写随机c[a[i]] = b[i]用a随机
0..N-1 的排列（write_random 相当于问题中的 inv）
代码已在 gcc -O3 -funroll-loops -march=native -malign-double 上编译
Skylake 处理器。性能是用 _rdtsc() 衡量的
以每次迭代的周期数给出。该函数被执行了几次（1000-20000 取决于数组大小），进行了 10 次实验并保留了最小的时间。
数组大小范围从 4000 到 1200000。所有代码均使用 openmp 使用顺序和并行版本进行测量。
这是结果图。函数有不同的颜色，粗线为顺序版本，细线为并行版本。
直接复制（显然）是最快的，由 gcc 实现
高度优化的 memcpy()。这是一种使用内存估算数据吞吐量的方法。它的范围从小矩阵的每次迭代 0.8 周期 (CPI) 到大矩阵的 2.0 CPI。
读取线性性能大约是 memcpy 的两倍，但有 2 次读取和 1 次写入，vs 1
读取和写入直接副本。更多的索引增加了一些依赖性。最小值为 1.56 CPI，最大值为 3.8 CPI。写线性略长（5-10%）。
随机索引读取和写入是原始问题的目的，值得更长的评论。这是结果。
size 4000 6000 9000 13496 20240 30360 45536 68304 102456 153680 230520 345776 518664 777992 1166984
rd-rand 1.86821 2.52813 2.90533 3.50055 4.69627 5.10521 5.07396 5.57629 6.13607 7.02747 7.80836 10.9471 15.2258 18.5524 21.3811
wr-rand 7.07295 7.21101 7.92307 7.40394 8.92114 9.55323 9.14714 8.94196 8.94335 9.37448 9.60265 11.7665 15.8043 19.1617 22.6785
小值（<10k）：L1缓存为32k，可以容纳一个4k的uint64数组。请注意，由于索引的随机性，在大约 1/8 次迭代后，L1 缓存将被随机索引数组的值完全填充（因为缓存行为 64 字节并且可以容纳 8 个数组元素）。访问其他线性数组我们将快速生成许多 L1 未命中，我们必须使用 L2 缓存。 L1 缓存访问是 5 个周期，但它是流水线的，每个周期可以提供几个值。 L2 访问时间更长，需要 12 个周期。随机读取和写入的未命中数量相似，但我们看到，当数组较小时，我们完全支付了写入所需的双重访问。
中值（10k-100k）：二级缓存为256k，可容纳32k的int64数组。之后，我们需要进入 L3 缓存（12Mo）。随着大小的增加，L1 和 L2 中的未命中数增加，计算时间也相应增加。两种算法都有相似数量的未命中，主要是由于随机读取或写入（其他访问是线性的，可以非常有效地由缓存预取）。我们检索已在 B.M 中记录的随机读取和写入之间的因子二。回答。这可以部分地用写入的双倍成本来解释。
large values (>100k): 方法之间的差异逐渐减小。对于这些大小，很大一部分信息存储在 L3 缓存中。 L3 大小足以容纳 1.5M 的完整阵列，并且行不太可能被弹出。因此，对于写入，在初始读取之后，可以在没有行弹出的情况下完成更多的写入，并且写入与读取的相对成本降低了。对于这些大尺寸，还需要考虑许多其他因素。例如，缓存只能处理有限数量的未命中（典型值 16），当未命中数量很大时，这可能是限制因素。
关于随机读写的并行omp版本的一句话。除了小尺寸，将随机索引数组分布在多个缓存中可能不是一个优势，它们系统地快两倍。对于大尺寸，我们清楚地看到随机读取和写入之间的差距由于错误共享而增加。
以目前复杂的计算机体系结构进行定量预测几乎是不可能的，即使对于简单的代码，甚至对行为的定性解释也很困难它必须考虑到许多因素。正如其他答案中提到的，与 python 相关的软件方面也会产生影响。但是，虽然在某些情况下可能会发生这种情况，但在大多数情况下，人们不能认为读取由于数据依赖性而变得更加昂贵。
我目前正在努力更好地了解 memory/cache 相关的性能问题。我在某处读到内存局部性对于读取比写入更重要，因为在前一种情况下 CPU 必须实际等待数据，而在后一种情况下它可以将它们发送出去并忘记它们。
考虑到这一点，我进行了以下快速而简单的测试：我编写了一个脚本来创建一个包含 N 个随机浮点数和一个排列的数组，即随机包含数字 0 到 N-1 的数组命令。然后它重复（1）线性读取数据数组并将其以排列给出的随机访问模式写回新数组或（2）以排列顺序读取数据数组并将其线性写入新数组。
令我惊讶的是 (2) 似乎始终比 (1) 快。但是，我的脚本有问题
- 脚本是在python/numpy中编写的。这是一种相当高级的语言，尚不清楚 read/write 的实现有多精确。
- 我可能没有正确平衡这两种情况。
此外，下面的一些 answers/comments 表明我最初的期望是不正确的，并且根据 cpu 缓存的详细信息，这两种情况都可能更快。
我的问题是：
- 两者中哪一个（如果有的话）应该更快？
- 这里有哪些相关的缓存概念；他们如何影响结果
初学者友好的解释将不胜感激。任何支持代码都应该在 C / cython / numpy / numba 或 python.
中可选：
- 解释为什么绝对持续时间在问题规模上是非线性的（参见下面的计时）。
- 解释我明显不充分的 python 实验的行为。
供参考，我的平台是Linux-4.12.14-lp150.11-default-x86_64-with-glibc2.3.4。 Python 版本是 3.6.5.
这是我写的代码：
import numpy as np
from timeit import timeit
def setup():
global a, b, c
a = np.random.permutation(N)
b = np.random.random(N)
c = np.empty_like(b)
def fwd():
c = b[a]
def inv():
c[a] = b
N = 10_000
setup()
timeit(fwd, number=100_000)
# 1.4942631321027875
timeit(inv, number=100_000)
# 2.531870319042355
N = 100_000
setup()
timeit(fwd, number=10_000)
# 2.4054739447310567
timeit(inv, number=10_000)
# 3.2365565397776663
N = 1_000_000
setup()
timeit(fwd, number=1_000)
# 11.131387163884938
timeit(inv, number=1_000)
# 14.19817715883255
正如@Trilarion 和@Yann Vernier 指出的那样，我的片段没有得到适当的平衡，因此我将它们替换为
def fwd():
c[d] = b[a]
b[d] = c[a]
def inv():
c[a] = b[d]
b[a] = c[d]
where d = np.arange(N)（我以两种方式随机播放所有内容以希望减少跨试验缓存效果）。我还将 timeit 替换为 repeat 并将重复次数减少了 10 倍。
然后我得到
[0.6757169323973358, 0.6705542299896479, 0.6702114241197705] #fwd
[0.8183442652225494, 0.8382121799513698, 0.8173762648366392] #inv
[1.0969422250054777, 1.0725746559910476, 1.0892365919426084] #fwd
[1.0284497970715165, 1.025063106790185, 1.0247828317806125] #inv
[3.073981977067888, 3.077839042060077, 3.072118630632758] #fwd
[3.2967213969677687, 3.2996009718626738, 3.2817375687882304] #inv
因此似乎仍然存在差异，但它更加微妙，现在可以根据问题的大小进行选择。
- 首先反驳您的直觉：即使没有 numpy 机制，
fwd也胜过inv。
这个numba版本就是这样：
import numba
@numba.njit
def fwd_numba(a,b,c):
for i in range(N):
c[a[i]]=b[i]
@numba.njit
def inv_numba(a,b,c):
for i in range(N):
c[i]=b[a[i]]
N=10000 的时间：
%timeit fwd()
%timeit inv()
%timeit fwd_numba(a,b,c)
%timeit inv_numba(a,b,c)
62.6 µs ± 3.84 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
144 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
16.6 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
34.9 µs ± 1.57 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
- 其次，Numpy 必须处理可怕的对齐和（缓存）局部性问题。
它本质上是对来自 BLAS/ATLAS/MKL 的低级别程序的包装器，为此进行了调整。 花哨的索引是一个很好的高级工具，但对于这些问题来说是异端；在低层次上没有直接翻译这个概念。
- 第三，numpy dev docs : 详细介绍花式索引。特别是：
Unless there is only a single indexing array during item getting, the validity of the indices is checked beforehand. Otherwise it is handled in the inner loop itself for optimization.
我们这里就是这种情况。我认为这可以解释差异，以及为什么 set 比 get 慢。
这也解释了为什么手工制作的 numba 通常更快：它不检查任何内容并在索引不一致时崩溃。
您的函数 fwd 没有触及全局变量 c。你没有告诉它global c（只在setup），所以它有自己的局部变量，在cpython中使用STORE_FAST：
>>> import dis
>>> def fwd():
... c = b[a]
...
>>> dis.dis(fwd)
2 0 LOAD_GLOBAL 0 (b)
3 LOAD_GLOBAL 1 (a)
6 BINARY_SUBSCR
7 STORE_FAST 0 (c)
10 LOAD_CONST 0 (None)
13 RETURN_VALUE
现在，让我们用全局试试：
>>> def fwd2():
... global c
... c = b[a]
...
>>> dis.dis(fwd2)
3 0 LOAD_GLOBAL 0 (b)
3 LOAD_GLOBAL 1 (a)
6 BINARY_SUBSCR
7 STORE_GLOBAL 2 (c)
10 LOAD_CONST 0 (None)
13 RETURN_VALUE
即便如此，与为全局调用 setitem 的 inv 函数相比，它在时间上可能有所不同。
无论哪种方式，如果你想让它把 写成 c，你需要像 c[:] = b[a] 或 c.fill(b[a]) 这样的东西。赋值将变量（名称）替换为右侧的对象，因此旧的 c 可能会被释放而不是新的 b[a]，并且这种内存改组可能代价高昂。
至于我认为您想衡量的效果，基本上是正向排列还是反向排列的成本更高，这将高度依赖于缓存。前向置换（从线性读取存储在随机排序的索引处）原则上可能更快，因为它可以使用写掩码并且永远不会获取新数组，假设缓存系统足够智能以在写缓冲区中保留字节掩码。如果数组足够大，则在执行随机读取时向后运行缓存冲突的风险很高。
这是我的初步印象；正如你所说，结果是相反的。这可能是缓存实现没有大写缓冲区或无法利用小写的结果。如果超出缓存的访问无论如何都需要相同的内存总线时间，则读取访问将有机会加载不会在需要之前从缓存中删除的数据。使用多路缓存，部分写入的行也将有机会不被选择驱逐；并且只有脏缓存行需要内存总线时间来丢弃。使用其他知识（例如，排列是完整的且不重叠的）编写的较低级别的程序可以使用非时间 SSE 写入等提示来改进行为。
以下实验证实了随机写入比随机读取更快。对于小数据（当它完全适合缓存时）随机写入代码比随机读取慢（可能是因为 numpy 中的某些实现特性），但随着数据大小的增长，最初的 1.7 倍执行时间的差异几乎完全消除（但是，在 numba 的情况下，最终趋势出现了奇怪的逆转）。
$ cat test.py
import numpy as np
from timeit import timeit
import numba
def fwd(a,b,c):
c = b[a]
def inv(a,b,c):
c[a] = b
@numba.njit
def fwd_numba(a,b,c):
for i,j in enumerate(a):
c[i] = b[j]
@numba.njit
def inv_numba(a,b,c):
for i,j in enumerate(a):
c[j] = b[i]
for p in range(4, 8):
N = 10**p
n = 10**(9-p)
a = np.random.permutation(N)
b = np.random.random(N)
c = np.empty_like(b)
print('---- N = %d ----' % N)
for f in 'fwd', 'fwd_numba', 'inv', 'inv_numba':
print(f, timeit(f+'(a,b,c)', number=n, globals=globals()))
$ python test.py
---- N = 10000 ----
fwd 1.1199337750003906
fwd_numba 0.9052993479999714
inv 1.929507338001713
inv_numba 1.5510062070025015
---- N = 100000 ----
fwd 1.8672701190007501
fwd_numba 1.5000483989970235
inv 2.509873716000584
inv_numba 2.0653326050014584
---- N = 1000000 ----
fwd 7.639554155000951
fwd_numba 5.673054756000056
inv 7.685382894000213
inv_numba 5.439735023999674
---- N = 10000000 ----
fwd 15.065879136000149
fwd_numba 12.68919651500255
inv 15.433822674000112
inv_numba 14.862108078999881
你的两个 NumPy 片段 b[a] 和 c[a] = b 似乎是测量 shuffled/linear read/write 速度的合理启发式方法，因为我将尝试通过查看底层来争论下面第一部分中的 NumPy 代码。
关于哪个应该更快的问题，随机读取线性写入通常会获胜似乎是合理的（正如基准似乎显示的那样），但速度差异可能受到 "shuffled" 打乱后的索引是，并且以下一项或多项：
- CPU 缓存 read/update 策略（write-back vs. write-through 等）。
- CPU 如何选择（重新）排序它需要执行的指令（流水线）。
- CPU 识别内存访问模式和预取数据。
- 缓存逐出逻辑。
即使假设哪些政策已经到位，这些影响也很难建模和推理分析，所以我不确定适用于所有处理器的一般答案是否可能（尽管我不是硬件专家).
尽管如此，在下面的第二部分中，我将尝试推理为什么随机读取线性写入明显更快，给出一些假设。
"Trivial" 花式索引
本节的目的是通过 NumPy 源代码来确定是否有任何明显的时间解释，并尽可能清楚地了解 A[B] 或 [= 时会发生什么15=] 被执行。
支持 getitem and setitem operations in this question is "trivial 花式索引的迭代例程":
B是单步长的单索引数组A和B具有相同的内存顺序（均为 C 连续或均为 Fortran 连续）
此外，在我们的例子中 A 和 B 都是 Uint Aligned:
Strided copy code: Here, "uint alignment" is used instead. If the itemsize [N] of an array is equal to 1, 2, 4, 8 or 16 bytes and the array is uint aligned then instead [of using buffering] numpy will do
*(uintN*)dst) = *(uintN*)src)for appropriate N. Otherwise numpy copies by doingmemcpy(dst, src, N).
这里的重点是避免使用内部缓冲区来确保对齐。使用 *(uintN*)dst) = *(uintN*)src) 实现的底层复制与 "put the X bytes from offset src into the X bytes at offset dst".
编译器可能会将其非常简单地转换为 mov 指令（例如在 x86 上）或类似指令。
执行项目获取和设置的核心底层代码在函数mapiter_trivial_get和mapiter_trivial_set中。这些函数是在 lowlevel_strided_loops.c.src 中生成的，其中的模板和宏使其阅读起来有些困难（感谢高级语言）。
坚持不懈，终于可以看出getitem和setitem的差别不大。这是用于说明的主循环的简化版本。宏行确定是 运行 getitem 还是 setitem:
while (itersize--) {
char * self_ptr;
npy_intp indval = *((npy_intp*)ind_ptr);
#if @isget@
if (check_and_adjust_index(&indval, fancy_dim, 0, _save) < 0 ) {
return -1;
}
#else
if (indval < 0) {
indval += fancy_dim;
}
#endif
self_ptr = base_ptr + indval * self_stride; /* offset into array being indexed */
#if @isget@
*(npy_uint64 *)result_ptr = *(npy_uint64 *)self_ptr;
#else
*(npy_uint64 *)self_ptr = *(npy_uint64 *)result_ptr;
#endif
ind_ptr += ind_stride; /* move to next item of index array */
result_ptr += result_stride; /* move to next item of result array */
正如我们所料，这只是一些算术运算，以获得数组中的正确偏移量，然后将字节从一个内存位置复制到另一个内存位置。
setitem 的额外索引检查
值得一提的是，对于setitem，索引的有效性（是否都是目标数组的入站）是checked before copying begins (via check_and_adjust_index），这也将负索引替换为相应的正索引。
在上面的代码片段中，您可以看到 check_and_adjust_index 在主循环中调用了 getitem，而对 setitem 进行了更简单（可能是冗余）的负索引检查。
这个额外的初步检查可能会对 setitem (A[B] = C) 的速度产生很小但负面的影响。
缓存未命中
因为两个代码片段的代码非常相似，所以怀疑落在 CPU 以及它如何处理对底层内存数组的访问。
CPU 缓存最近访问过的小内存块（缓存行），预计它可能很快需要再次访问该内存区域。
对于上下文，缓存行一般为64字节。我老旧的笔记本电脑 CPU 上的 L1（最快）数据缓存是 32KB（足以容纳数组中的大约 500 个 int64 值，但请记住 CPU 将做其他需要其他内存的事情，同时NumPy 片段执行):
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K
您可能已经知道，对于 reading/writing 内存顺序缓存效果很好，因为 64 字节的内存块会根据需要获取并存储在更靠近 CPU 的位置。重复访问该内存块比从 RAM（或更慢的高级缓存）中获取更快。事实上，CPU 甚至可以在程序请求之前抢先获取下一个缓存行。
另一方面，随机访问内存很可能导致频繁的缓存未命中。这里，具有所需地址的内存区域不在 CPU 附近的快速缓存中，而是必须从更高级别的缓存（较慢）或实际内存（慢得多）访问。
那么 CPU 处理哪个更快：频繁的数据读取未命中，还是数据写入未命中？
让我们假设CPU的写策略是回写，这意味着修改的内存被写回缓存。缓存被标记为正在修改（或 "dirty"），只有当行从缓存中被逐出时，更改才会被写回主内存（CPU 仍然可以从脏缓存中读取线）。
如果我们写入一个大数组中的随机点，预计 CPU 缓存中的许多缓存行将变脏。需要写入主内存，因为每个内存都被逐出，如果缓存已满，这可能经常发生。
但是，当顺序写入数据并随机读取数据时，这种写通应该不会那么频繁地发生，因为我们希望更少的缓存行变脏，并且数据回写到主内存或更慢的缓存的频率更低。
如前所述，这是一个简化模型，可能还有许多其他因素会影响 CPU 的性能。比我更专业的人可能会改进这个模型。
这是一个复杂的问题，与现代处理器的架构特征和您的直觉密切相关 随机读取比随机写入慢，因为 CPU 必须等待读取数据 未经验证（大部分时间）。我将详细说明几个原因。
现代处理器可以非常有效地隐藏读取延迟
而内存写入比内存读取更昂贵
尤其是在多核环境下
原因 #1 现代处理器可以有效隐藏读取延迟。
现代 superscalar can execute several instructions simultaneously, and change instruction execution order (out of order execution)。 虽然这些功能的首要原因是增加指令吞吐量， 最有趣的结果之一是处理器隐藏内存写入（或复杂运算符、分支等）延迟的能力。
为了解释这一点，让我们考虑一个将数组复制到另一个数组的简单代码。
for i in a:
c[i] = b[i]
编译后，处理器执行的代码会有点像那样
#1. (iteration 1) c[0] = b[0]
1a. read memory at b[0] and store result in register c0
1b. write register c0 at memory address c[0]
#2. (iteration 2) c[1] = b[1]
2a. read memory at b[1] and store result in register c1
2b. write register c1 at memory address c[1]
#1. (iteration 2) c[2] = b[2]
3a. read memory at b[2] and store result in register c2
3b. write register c2 at memory address c[2]
# etc
（这太过简化了，实际代码更复杂，需要处理循环管理、地址计算等，但这种简单的模型目前已经足够了）。
如问题中所述，对于读取，处理器必须等待实际数据。的确，1b需要1a取来的数据，只要1a没有完成就不能执行。这样的约束称为 dependency，我们可以说 1b 依赖于 1a。依赖关系是现代处理器中的一个主要概念。依赖关系表示算法（例如，我将 b 写成 c）并且必须绝对遵守。但是，如果指令之间没有依赖关系，处理器将尝试执行其他挂起的指令，以保持可操作的流水线始终处于活动状态。这可以导致执行 out-of-order，只要遵守依赖关系（类似于 as-if 规则）。
对于所考虑的代码，高级指令 2. 和 1. 之间（或 asm 指令 2a 和 2b 与之前的指令之间）没有 依赖性。实际上，最终结果甚至是相同的，即 2. 在 1. 之前执行，处理器将在 1a 和 1b 完成之前尝试执行 2a 和 2b。 2a和2b之间还是有依赖关系，但是都可以下发。 3a 也类似。和 3b.，等等。这是隐藏内存延迟 的有力手段。如果由于某种原因 2.、3. 和 4. 可以在 1. 加载其数据之前终止，您甚至可能根本不会注意到任何减速。
此指令级并行性由处理器中的一组 "queues" 管理。
保留站RS中的待处理指令队列（在最近的奔腾中类型为128μ指令）。只要指令所需的资源可用（例如指令 1b 的寄存器 c1 的值），指令就可以执行。
L1 高速缓存之前的内存顺序缓冲区 MOB 中的待处理内存访问队列。这是处理内存别名和确保同一地址的内存写入或加载的顺序性所必需的（典型值 64 次加载，32 次存储）
出于类似原因，在寄存器（重新排序缓冲区或 168 个条目的 ROB）中写回结果时强制执行顺序的队列。
和指令获取时的一些其他队列，用于 μops 生成，缓存中的写入和未命中缓冲区等
在执行前一个程序的某一时刻，RS 中将有许多挂起的存储指令，MOB 中有多个加载指令，ROB 中有等待退出的指令。
一旦数据可用（例如读取终止），相关指令就可以执行并释放队列中的位置。但是，如果没有终止发生，并且这些队列之一已满，则与该队列关联的功能单元将停止（如果处理器缺少寄存器名称，这也可能发生在指令发出时）。停顿会造成性能损失，为避免这种情况，必须限制队列填充。
这解释了线性和随机内存访问之间的区别。
在线性访问中，1/ 由于空间局部性更好，并且缓存可以使用常规模式预取访问以进一步减少未命中数，因此 1/ 未命中数会更小，并且 2/ 每当读取终止时，它将涉及完整的缓存行和可以释放几个挂起的加载指令，限制指令队列的填充。这样处理器就会一直处于忙碌状态，并且内存延迟会被隐藏。
对于随机访问，未命中数会更高，数据到达时只能服务单次负载。因此，指令队列将迅速饱和，处理器停顿和内存延迟无法再通过执行其他指令来隐藏。
处理器架构必须在吞吐量方面保持平衡，以避免队列饱和和停顿。事实上，在处理器的某个执行阶段通常有数十条指令，全局吞吐量（即内存（或功能单元）处理指令请求的能力）是决定性能的主要因素。事实上，这些未决指令中的一些正在等待内存值的影响很小...
...除非你有很长的依赖链。
当一条指令必须等待前一条指令完成时，存在依赖关系。使用读取的结果是一种依赖。当涉及依赖链时，依赖关系可能会成为问题。
例如，考虑代码 for i in range(1,100000): s += a[i]。所有的内存读取都是独立的，但是在s中的积累有一个依赖链。在前一个终止之前，不会发生任何添加。这些依赖性将使保留站迅速填满并在管道中造成停顿。
但是读取很少涉及依赖链。仍然可以想象所有读取都依赖于前一个读取的病态代码（例如 for i in range(1,100000): s = a[s]），但它们在实际代码中并不常见。而且问题出在依赖链上，而不是因为它是一个读；这种情况与 for i in range(1,100000): x = 1.0/x+1.0.
因此，除了在某些情况下，计算时间与吞吐量的相关性比与读取依赖性的相关性更高，这要归功于超标量输出或订单执行隐藏了延迟这一事实。就吞吐量而言，写入比读取更差。
原因 #2：内存写入（尤其是随机写入）比内存读取更昂贵
这与 caches 的行为方式有关。缓存是快速内存，由处理器存储一部分内存（称为行）。缓存行目前为 64 字节，并允许利用内存引用的空间局部性：一旦存储了一行，该行中的所有数据都立即可用。这里的重要方面是缓存和内存之间的所有传输都是行。
当处理器对数据执行读取时，缓存会检查数据所属的行是否在缓存中。如果不是，则从内存中获取该行，将其存储在缓存中，并将所需数据发送回处理器。
当处理器将数据写入内存时，缓存也会检查行是否存在。如果该行不存在，则缓存无法将其数据发送到内存（因为所有 传输都是基于行的）并执行以下步骤：
- 缓存从内存中获取行并将其写入缓存行。
- 数据写入缓存，整行标记为已修改（脏）
- 当一行从缓存中被抑制时，它会检查修改标志，如果该行已被修改，它会将其写回内存（回写缓存）
因此，每次内存写入都必须先进行内存读取，才能获取缓存中的行。这增加了一个额外的操作，但对于线性写入来说并不是很昂贵。第一个写入的字会出现缓存未命中和内存读取，但连续的写入只会涉及缓存并被命中。
但是随机写的情况就大不相同了。如果未命中数很重要，则每次缓存未命中都意味着在行从缓存中弹出之前先进行一次读取，然后仅进行少量写入，这会显着增加写入成本。如果单次写入后弹出一行，我们甚至可以认为写入的时间成本是读取的两倍。
请务必注意，增加内存访问（读取或写入）的次数往往会使内存访问路径饱和，并全局减慢处理器和内存之间的所有传输。
在任何一种情况下，写入总是比读取更昂贵。多核增强了这方面。
原因 #3：随机写入会在多核中造成缓存未命中
不确定这是否真的适用于问题的情况。虽然 numpy BLAS 例程是多线程的，但我认为基本数组复制不是。但它是密切相关的，也是写入更昂贵的另一个原因。
多核的问题是确保适当 cache coherence in such a way that a data shared by several processors is properly updated in the cache of every core. This is done by mean of a protocol such as MESI 在写入之前更新缓存行，并使其他缓存副本无效（读取所有权）。
虽然 none 数据实际上在问题（或其并行版本）之间共享，但请注意该协议适用于 缓存行 。每当要修改缓存行时，都会从保存最新副本的缓存中复制它，本地更新和所有其他副本无效。即使核心正在访问缓存行的不同部分。这种情况称为false sharing，是多核编程的重要问题。
关于随机写的问题，cache line是64字节，可以容纳8个int64，如果电脑是8核，平均每个核会处理2个值。因此有一个重要的错误共享会减慢写入速度。
我们做了一些性能评估。它是在 C 中执行的，以便包括对并行化影响的评估。我们比较了 5 处理大小为 N.
的 int64 数组的函数只是 b 到 c 的一个副本 (
c[i] = b[i])（由编译器用memcpy()实现）用线性索引复制
c[i] = b[d[i]]其中d[i]==i(read_linear)用随机索引复制
c[i] = b[a[i]]其中a是随机的 0..N-1的排列（read_random等同于原题中的fwd）写线性
c[d[i]] = b[i]其中d[i]==i(write_linear)写随机
c[a[i]] = b[i]用a随机 0..N-1 的排列（write_random相当于问题中的inv）
代码已在 gcc -O3 -funroll-loops -march=native -malign-double 上编译
Skylake 处理器。性能是用 _rdtsc() 衡量的
以每次迭代的周期数给出。该函数被执行了几次（1000-20000 取决于数组大小），进行了 10 次实验并保留了最小的时间。
数组大小范围从 4000 到 1200000。所有代码均使用 openmp 使用顺序和并行版本进行测量。
这是结果图。函数有不同的颜色，粗线为顺序版本，细线为并行版本。
直接复制（显然）是最快的，由 gcc 实现
高度优化的 memcpy()。这是一种使用内存估算数据吞吐量的方法。它的范围从小矩阵的每次迭代 0.8 周期 (CPI) 到大矩阵的 2.0 CPI。
读取线性性能大约是 memcpy 的两倍，但有 2 次读取和 1 次写入，vs 1 读取和写入直接副本。更多的索引增加了一些依赖性。最小值为 1.56 CPI，最大值为 3.8 CPI。写线性略长（5-10%）。
随机索引读取和写入是原始问题的目的，值得更长的评论。这是结果。
size 4000 6000 9000 13496 20240 30360 45536 68304 102456 153680 230520 345776 518664 777992 1166984
rd-rand 1.86821 2.52813 2.90533 3.50055 4.69627 5.10521 5.07396 5.57629 6.13607 7.02747 7.80836 10.9471 15.2258 18.5524 21.3811
wr-rand 7.07295 7.21101 7.92307 7.40394 8.92114 9.55323 9.14714 8.94196 8.94335 9.37448 9.60265 11.7665 15.8043 19.1617 22.6785
小值（<10k）：L1缓存为32k，可以容纳一个4k的uint64数组。请注意，由于索引的随机性，在大约 1/8 次迭代后，L1 缓存将被随机索引数组的值完全填充（因为缓存行为 64 字节并且可以容纳 8 个数组元素）。访问其他线性数组我们将快速生成许多 L1 未命中，我们必须使用 L2 缓存。 L1 缓存访问是 5 个周期，但它是流水线的，每个周期可以提供几个值。 L2 访问时间更长，需要 12 个周期。随机读取和写入的未命中数量相似，但我们看到，当数组较小时，我们完全支付了写入所需的双重访问。
中值（10k-100k）：二级缓存为256k，可容纳32k的int64数组。之后，我们需要进入 L3 缓存（12Mo）。随着大小的增加，L1 和 L2 中的未命中数增加，计算时间也相应增加。两种算法都有相似数量的未命中，主要是由于随机读取或写入（其他访问是线性的，可以非常有效地由缓存预取）。我们检索已在 B.M 中记录的随机读取和写入之间的因子二。回答。这可以部分地用写入的双倍成本来解释。
large values (>100k): 方法之间的差异逐渐减小。对于这些大小，很大一部分信息存储在 L3 缓存中。 L3 大小足以容纳 1.5M 的完整阵列，并且行不太可能被弹出。因此，对于写入，在初始读取之后，可以在没有行弹出的情况下完成更多的写入，并且写入与读取的相对成本降低了。对于这些大尺寸，还需要考虑许多其他因素。例如，缓存只能处理有限数量的未命中（典型值 16），当未命中数量很大时，这可能是限制因素。
关于随机读写的并行omp版本的一句话。除了小尺寸，将随机索引数组分布在多个缓存中可能不是一个优势，它们系统地快两倍。对于大尺寸，我们清楚地看到随机读取和写入之间的差距由于错误共享而增加。
以目前复杂的计算机体系结构进行定量预测几乎是不可能的，即使对于简单的代码，甚至对行为的定性解释也很困难它必须考虑到许多因素。正如其他答案中提到的，与 python 相关的软件方面也会产生影响。但是，虽然在某些情况下可能会发生这种情况，但在大多数情况下，人们不能认为读取由于数据依赖性而变得更加昂贵。