c++ - 使用 `%` 与 `&` 时的时间差异/增加差异

Question

在尝试确定给定 CPU 的缓存大小时，我尝试对内存/缓存的内存访问进行计时，例如:

lengthMod = sizes[i]/sizeof(int)  - 1; // where sizes[i] is something like 1024, 2048 ... 
for (unsigned int k = 0; k < REPS; k++) {
    data[(k * 16) & lengthMod]++;
}

1, 0.52 
4, 0.52 
8, 0.52 
16, 0.52 
32, 0.52 
64, 1.11 // << note the jump in timing. L1 cache size is 32K
128, 1.12 
256, 1.19 

所以我认为如果 lengthMod 不是 2 的幂，我不能这样做。所以我试着做

lengthMod = sizes[i]/sizeof(int);
for (unsigned int k = 0; k < REPS; k++) {
    data[(k * 16) % lengthMod]++;
}

1, 2.67 
4, 2.57 
8, 2.55 
16, 2.51 
32, 2.42 
64, 2.42 // << no jump anymore ...
128, 2.42 
256, 2.42

然后我发现我预期的时间增加不再存在......我预计时间会增加但它应该适用于所有值？因此，如果在使用 & 时它的 x 秒，我期望 ~x+c 秒(其中 c 是近似恒定)，但事实并非如此，事实上，它将时间差异减少到不存在，这是为什么？

Answer 1

您看到的是瓶颈的权衡。

• 在第一个示例中，您遇到了缓存带宽瓶颈。
• 在第二个示例中，您遇到了整数除法的瓶颈。

在继续之前，让我们先看看这两个例子的区别:

• 在第一种情况下，您使用 &，这是一种快速的按位运算。
• 在第二种情况下，您使用 % 这是非常慢的除法。

split 非常缓慢。当除数/模数是编译时常量时，现代编译器将尝试优化它们。

但这里不是这种情况。 因此您支付硬件部门的全部成本。这就是为什么第二个示例中的时间比第一个慢得多。

---

使用&，代码的速度足以使缓存带宽达到最大。但是，使用 % 时，代码要慢得多 - 速度不足以跟上缓存。所以你一直看到相同的时间。