线性读取混洗写入总是比洗牌读取线性写入更快吗？(是:为什么花哨的作业比花哨的查找慢？)

Question

我目前正在努力更好地了解与内存相关的性能问题.我读到某处内存局部性对于读取比写入更重要,因为在前一种情况下,CPU必须实际等待数据,而在后一种情况下,它可以将它们运出并忘记它们.

考虑到这一点,我做了以下快速和肮脏的测试:

更新3(非python/numpy用户解释):

我在python/numpy中编写了一个脚本,它创建了一个N个随机浮点数和一个置换数组,即一个包含随机顺序的数字0到N-1的数组.然后重复(1)线性地读取数据阵列并将其写回由置换给出的随机访问模式中的新阵列,或者(2)以置换顺序读取数据阵列并线性地将其写入新阵列.

令我惊讶的是(2)似乎始终比(1)快.但是,我的脚本存在问题

• python/numpy是相当高级别的,不清楚读/写是如何实现的.
• 我可能没有正确平衡这两个案例.

此外,下面的一些答案/评论表明我原来的期望并不总是正确的,根据cpu缓存的细节,这两种情况可能会更快.

我现在放置的赏金适用于以下内容:

更新2:

鉴于迄今为止的评论和答案,我希望得到澄清

• 是@ BM的numba实验结论？
• 或者它可以采取任何方式取决于缓存细节？

请以初学者友好的方式解释可能与此相关的各种缓存概念(参见@Trilarion的评论,@ Yann Vernier的回答).支持代码可能在C/cython/numpy/numba或python中.

或者,解释我明显不足的python实验的行为.

原文:

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

现在,结果与我预期的结果相反:Linux-4.12.14-lp150.11-default-x86_64-with-glibc2.3.4随机读取和连续写入的速度始终快于d = np.arange(N)连续读取和随机写入.

我怀疑我错过了一些相当明显的东西,但无论如何,这里有:

为什么会这样？

虽然我们在这里,为什么整个事情如此非线性？他们的数字不是很大吗？

更新:正如@Trilarion和@Yann Vernier指出的那样,我的片段没有得到适当的平衡,所以我用

def fwd():
    c[d] = b[a]
    b[d] = c[a]

def inv():
    c[a] = b[d]
    b[a] = c[d]

在哪里timeit(我将两种方式混合在一起,希望减少试验缓存效果).我也用10代替repeat了Linux-4.12.14-lp150.11-default-x86_64-with-glibc2.3.4并减少了重复次数.

然后我明白了

[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

所以似乎仍然存在差异,但它更加微妙,现在可以根据问题的大小进行.

Answer 1

这是一个复杂的问题,与现代处理器的架构特征密切相关,您的直觉是随机读取比随机写入慢,因为CPU必须等待读取数据 未经验证(大部分时间).有几个原因我会详细说明.

1. 现代处理器非常有效地隐藏读取延迟

2. 而内存写入比内存读取更昂贵

3. 特别是在多核环境中

理由#1现代处理器可以有效地隐藏读取延迟.

现代超标量可以同时执行多个指令,并改变指令执行顺序(乱序执行).虽然这些功能的第一个原因是增加指令输出,但最有趣的结果之一是处理器隐藏存储器写入(或复杂的运算符,分支等)的延迟的能力.

为了解释这一点,让我们考虑一个将数组复制到另一个数组的简单代码.

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没有完成就不能执行.这种约束称为依赖,我们可以说1b依赖于1a.依赖关系是现代处理器的一个主要概念.依赖关系表达了​​算法(例如,我将b写入c),必须绝对尊重.但是,如果指令之间没有依赖关系,处理器将尝试执行其他待处理指令,以保持操作管道始终处于活动状态.只要遵守依赖关系(类似于as-if规则),这可能导致无序执行.

对于所考虑的代码,高级指令2和1之间没有依赖性(或者在asm指令2a和2b与先前的指令之间).实际上,最终结果甚至是相同的是2.在1.之前执行,并且处理器将尝试在1a和1b完成之前执行2a和2b.2a和2b之间仍然存在依赖关系,但两者都可以发布.同样适用于3a.和3b.等等.这是隐藏内存延迟的有力手段.如果由于某种原因,2,3和4.可以在1.加载其数据之前终止,您甚至可能根本不会注意到任何减速.

该指令级并行性由处理器中的一组"队列"管理.

• 保留站RS中的待处理指令队列(最近的pentiums中类型为128μs).只要指令所需的资源可用(例如指令1b的寄存器c1的值),就可以执行该指令.

• L1高速缓存之前的内存顺序缓冲区MOB中的挂起存储器访问队列.这是处理内存别名和确保内存写入或同一地址加载的顺序性所必需的(典型的是64个加载,32个存储)

• 由于类似的原因,在将结果写回寄存器(重新排序缓冲区或168个条目的ROB)时强制执行顺序性的队列.

• 指令获取时的一些其他队列,用于μops生成,缓存中的写入和未命中缓冲区等

在先前程序的执行的一个点处,RS中将存在许多未决存储指令,MOB中的若干加载以及等待在ROB中退出的指令.

一旦数据变得可用(例如读取终止),取决于指令可以执行并释放队列中的位置.但是如果没有发生终止,并且这些队列中的一个已满,则与该队列相关联的功能单元停止(如果处理器缺少寄存器名称,这也可能在指令发生时发生).停顿是造成性能损失的原因,为了避免这种情况,必须限制队列填充.

这解释了线性和随机存储器访问之间的区别.
在线性访问中,由于更好的空间局部性,1 /未命中数将更小,并且因为高速缓存可以使用常规模式预取访问以进一步减少它,并且每当读取终止时,它将涉及完整的高速缓存行和可以释放几个挂起的加载指令,限制指令队列的填充.这种方式使处理器永久忙,并且隐藏了内存延迟.
对于随机访问,未命中数将更高,并且在数据到达时只能提供单个负载.因此,指令队列将快速饱和,处理器停止并且执行其他指令不再能够隐藏存储器延迟.

处理器架构必须在吞吐量方面进行平衡,以避免队列饱和和停顿.实际上,在处理器的某个执行阶段通常存在数十条指令,并且全局吞吐量(即,由存储器(或功能单元)提供指令请求的能力)将是决定性能的主要因素.事实上,这些待处理指令中的一些等待内存值会产生轻微影响......

...除非你有很长的依赖链.

当指令必须等待前一个指令完成时,存在依赖关系.使用读取的结果是依赖性.当涉及依赖链时,依赖关系可能是一个问题.

例如,考虑代码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:内存写入(尤其是随机写入)比内存读取更昂贵

这与缓存的行为方式有关.高速缓存是快速存储器,用于存储处理器的一部分存储器(称为线路).高速缓存行目前是64字节,允许利用内存引用的空间局部性:一旦存储了一行,该行中的所有数据都立即可用.这里的重要方面是缓存和内存之间的所有传输都是行.

当处理器对数据执行读取时,高速缓存检查数据所属的行是否在高速缓存中.如果不是,则从存储器中取出行,存储在高速缓存中,并将所需数据发送回处理器.

当处理器将数据写入内存时,缓存还会检查线路是否存在.如果该行不存在,则缓存无法将其数据发送到内存(因为所有传输都是基于行的)并执行以下步骤:

1. cache从内存中获取该行并将其写入缓存行.
2. 数据写入缓存,整行标记为已修改(脏)
3. 当一行从缓存中被抑制时,它会检查修改后的标志,如果该行被修改,它会将其写回内存(写回缓存)

因此,每次内存写入之前必须有一个内存读取以获取缓存中的行.这增加了额外的操作,但对于线性写入来说并不是非常昂贵.对于第一个写入的字,将存在高速缓存未命中和存储器读取,但是连续写入将仅涉及高速缓存并且被命中.

但是随机写入的情况非常不同.如果未命中的数量很重要,则每个高速缓存未命中意味着在从高速缓存中弹出行之前只读取少量写入,这会显着增加写入成本.如果在单次写入后弹出一行,我们甚至可以认为写入是读取的时间成本的两倍.

值得注意的是,增加内存访问次数(读取或写入)往往会使内存访问路径饱和,并导致处理器和内存之间的所有传输速度降低.

在任何一种情况下,写入总是比读取更昂贵.而且多核增强了这个方面.

原因#3:随机写入会在多核中创建缓存未命中

不确定这是否真的适用于问题的情况.numpy BLAS例程是多线程的,我不认为基本的数组副本.但它密切相关,是写作更昂贵的另一个原因.

多核的问题是确保适当的高速缓存一致性,使得几个处理器共享的数据在每个核的高速缓存中得到适当更新.这是通过诸如MESI之类的协议来完成的,该协议在写入之前更新高速缓存行,并使其他高速缓存副本无效(读取所有权).

虽然问题中的核心(或其并行版本)之间没有实际共享数据,但请注意该协议适用于缓存行.每当要修改缓存行时,它都会从保存最新副本的缓存中复制,本地更新,所有其他副本都将失效.即使核心正在访问缓存行的不同部分.这种情况称为错误共享,这是多核编程的一个重要问题.

关于随机写入的问题,高速缓存行是64字节并且可以容纳8个int64,并且如果计算机具有8个核心,则每个核心将平均处理2个值.因此,存在一个重要的错误共享会减慢写入速度.

我们做了一些绩效评估.它是在C中执行的,以包括对并行化影响的评估.我们比较了5个处理大小为N的int64数组的函数.

1. 只是b到c(c[i] = b[i])的副本(由编译器实现memcpy())

2. 使用线性索引复制c[i] = b[d[i]]where d[i]==i(read_linear)

3. 使用随机索引c[i] = b[a[i]]进行复制,其中a随机排列为0..N-1(read_random相当于fwd原始问题)

4. 写线性c[d[i]] = b[i]在哪里d[i]==i(write_linear)

5. 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次读取和直接复制写入.索引增加了一些依赖性.最低值为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):L2缓存为256k,可容纳32k int64阵列.之后,我们需要转到L3缓存(12Mo).随着尺寸增加,L1和L2中的未命中数量增加,并且计算时间也相应增加.两种算法都有相似数量的未命中,主要是由于随机读取或写入(其他访问是线性的,并且可以通过高速缓存非常有效地预取).我们在BM回答中已经记录的随机读取和写入之间检索因子2.这可以部分解释为写入的双倍成本.

• 大值(> 100k):方法之间的差异逐渐减少.对于这些大小,大部分信息存储在L3缓存中.L3大小足以容纳1.5M的完整阵列,并且线路不太可能被弹出.因此,对于写入,在初始读取之后,可以在没有行弹出的情况下完成大量写入,并且降低了写入与读取的相对成本.对于这些大尺寸,还有许多其他因素需要考虑.例如,缓存只能用于有限数量的未命中(典型值16),并且当未命中数量很大时,这可能是限制因素.

关于并行omp版本的随机读写的一个词.除了小尺寸之外,将随机索引阵列分布在几个缓存上可能不是一个优点,它们系统地快〜两倍.对于大尺寸,我们清楚地看到随机读取和写入之间的差距由于错误共享而增加.

即使对于简单的代码,用现有计算机体系结构的复杂性进行定量预测几乎是不可能的,甚至对行为的定性解释也很困难,并且必须考虑许多因素.正如其他答案中所提到的,与python相关的软件方面也会产生影响.但是,虽然在某些情况下可能会发生,但大多数情况下,由于数据依赖性,人们不能认为读取更昂贵.

Answer 2

• 首先你的直觉的驳斥: fwd击败inv即使没有numpy的mecanism.

这个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 = 10 000的时间:

%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:详细花哨索引.特别是:

除非在项目获取期间只有一个索引数组,否则将事先检查索引的有效性.否则,它将在内部循环中进行处理以进行优化.

我们就是在这种情况下.我认为这可以解释差异,为什么设置比较慢.

它解释了为什么手工制作的numba通常更快:它不检查任何东西并且在不一致的索引上崩溃.

Answer 3

你的两个NumPy的片段b[a]和c[a] = b看起来像测量洗牌/线性读/写速度,因为我会尝试通过查看下面的第一部分中的底层代码NumPy的争论合理的启发.

关于哪个应该更快的问题,看起来似乎合理的是,混洗 - 读取 - 线性 - 写入通常可以获胜(如基准似乎显示的那样),但速度的差异可能受到混乱指数"洗牌"的影响. ,以及一个或多个:

• CPU缓存读取/更新策略(回写与直写等).
• CPU如何选择(重新)订购它需要执行的指令(流水线操作).
• CPU识别存储器访问模式和预取数据.
• 缓存逐出逻辑.

即使对哪些策略进行了假设,这些影响很难通过分析进行建模和推理,因此我不确定是否有可能适用于所有处理器的一般答案(尽管我不是硬件方面的专家).

然而,在下面的第二部分中,我将尝试推断为什么在给定一些假设的情况下,混洗 - 读取线性写入显然更快.

"琐碎"的花式索引

本节的目的是通过NumPy源代码来确定是否对时间有任何明显的解释,并尽可能清楚地了解在执行A[B]或A[B] = C执行时会发生什么.

在这个问题中支持getitem和setitem操作的花式索引的迭代例程是" 微不足道的 ":

• B 是一个具有单步幅的单索引数组
• A并B具有相同的内存顺序(C-contiguous或两者都是Fortran-contiguous)

此外,在我们的情况下,两个A和B是UINT对齐:

Strided copy code:这里使用"uint alignment"代替.如果数组的itemsize [N]等于1,2,4,8或16个字节,并且数组是uint对齐的,那么[使用缓冲] numpy将为*(uintN*)dst) = *(uintN*)src)适当的N做memcpy(dst, src, N).否则numpy副本通过执行.

这里的要点是避免使用内部缓冲区来确保对齐.实现的底层复制与*(uintN*)dst) = *(uintN*)src)"将偏移src中的X字节放入偏移dst的X字节"一样直接.

编译器可能会非常简单地将其转换为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,在复制开始(via check_and_adjust_index)之前检查索引的有效性(它们是否都是目标数组的所有入口),这也用相应的正索引替换负索引.

在上面的代码片段中,您可以check_and_adjust_index在主循环中看到调用getitem,而对setitem进行更简单(可能是冗余的)负指数检查.

这个额外的初步检查可能会对setitem(A[B] = C)的速度产生一些小但负面的影响.

缓存未命中

因为两个代码片段的代码非常相似,所以怀疑是CPU以及它如何处理对底层内存数组的访问.

CPU缓存最近访问过的小块内存(缓存行),期望它可能很快需要再次访问该内存区域.

对于上下文,缓存行通常为64字节.老化的笔记本电脑的CPU上的L1(最快)数据缓存是32KB(足以容纳来自阵列的大约500个int64值,但请记住,在执行NumPy代码段时,CPU将执行其他需要其他内存的事情):

$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K

您可能已经意识到,对于读/写内存顺序缓存很有效,因为64字节内存块根据需要提取并存储在更靠近CPU的位置.重复访问该内存块比从RAM(或更慢的更高级别缓存)中获取更快.实际上,CPU甚至可以在程序甚至请求之前抢先获取下一个高速缓存行.

另一方面,随机访问内存可能会导致频繁的缓存未命中.这里,具有所需地址的存储器区域不在CPU附近的快速高速缓存中,而是必须从更高级别的高速缓存(更慢)或实际存储器(更慢)访问.

那么CPU处理哪个更快:频繁的数据读取丢失或数据写入未命中？

假设CPU的写策略是回写,这意味着修改后的内存被写回缓存.缓存被标记为被修改(或"脏"),并且只有在从缓存中逐出该行(CPU仍然可以从脏缓存行读取)时,才会将更改写回主存储器.

如果我们写入大型数组中的随机点,则期望CPU缓存中的许多缓存行都会变脏.当每个被驱逐时,将需要写入主存储器,如果高速缓存已满,则可能经常发生这种情况.

但是,在顺序写入数据并随机读取数据时,这种写入应该不那么频繁地发生,因为我们期望更少的高速缓存行变脏并且数据写回主存储器或较慢的高速缓存不太经常.

如上所述,这是一个简化的模型,可能还有许多其他因素会影响CPU的性能.比我更专业的人可能能够改进这种模式.

Answer 4

您的函数fwd未触及全局变量c.你没有告诉它global c(仅在setup),所以它有自己的局部变量,并STORE_FAST在cpython中使用:

>>> 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

即便如此,与inv要求setitem全球化的功能相比,它可能在时间上有所不同.

无论哪种方式,如果你想它来编写成 c,你需要像c[:] = b[a]或c.fill(b[a]).赋值将变量(name)替换为右侧的对象,因此旧的c可能会被取消分配而不是new b[a],并且这种内存改组可能代价高昂.

至于我认为你想测量的效果,基本上是正向排列还是反向排列是否更昂贵,这将高度依赖于缓存.前向置换(从线性读取存储在随机排序的索引)原则上可以更快,因为它可以使用写掩码并且永远不会获取新阵列,假设缓存系统足够智能以保留写缓冲区中的字节掩码.如果阵列足够大,则在执行随机读取时向后运行高速缓存冲突的风险.

那是我最初的印象; 正如你所说,结果正好相反.这可能是缓存实现没有大写缓冲区或无法利用小写入的结果.如果高速缓存访​​问不需要相同的内存总线时间,则读访问将有可能加载在需要之前不会从高速缓存中清除的数据.使用多路缓存,部分写入的行也有可能不被选择驱逐; 并且只有脏缓存行需要内存总线时间下降.用其他知识编写的较低级程序(例如,排列完整且不重叠)可以使用诸如非时间SSE写入之类的提示来改善行为.

Answer 5

以下实验证实了随机写入比随机读取更快。对于小尺寸的数据（当它完全适合缓存时），随机写入代码的速度比随机读取代码的速度慢（可能是由于中的某些实现特性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