硬件预取器是否有益于此内存访问模式？

Question

我有两个数组:A用N_A随机整数和B使用N_B之间的随机整数0和(N_A - 1).我在以下循环中使用数字B作为索引A:

for(i = 0; i < N_B; i++) {
    sum += A[B[i]];
}

在Intel i7-3770(N_A= 2.56亿,N_B= 6400万)上进行试验,此循环仅需0.62秒,这相当于大约9纳秒的内存访问延迟.

由于这个延迟太小,我想知道硬件预取器是否正在发挥作用.有人可以提供解释吗？

Answer 1

CPU 在指令流中提前运行，并同时处理多个未完成的负载。该流看起来像这样：

load b[0]
load a[b[0]]
add
loop code

load b[1]
load a[b[1]]
add
loop code

load b[1]
load a[b[1]]
add
loop code

...

迭代仅由运行速度很快的循环代码序列化。所有负载可以同时运行。并发性仅受 CPU 可以处理的负载数量的限制。

我怀疑您想要对随机的、不可预测的、序列化的内存负载进行基准测试。这对于现代 CPU 来说实际上是相当困难的。尝试引入牢不可破的依赖链：

int lastLoad = 0;
for(i = 0; i < N_B; i++) {
    var load = A[B[i] + (lastLoad & 1)]; //be sure to make A one element bigger
    sum += load;
    lastLoad = load;
}

这需要执行最后一次加载，直到可以计算出下一次加载的地址。