某些阵列大小的性能减损

Question

我遇到以下代码的问题,我无法理解问题出在哪里.然而问题是只有V2英特尔处理器而不是V3.考虑C++中的以下代码:

struct Tuple{
  size_t _a; 
  size_t _b; 
  size_t _c; 
  size_t _d; 
  size_t _e; 
  size_t _f; 
  size_t _g; 
  size_t _h; 
};

void
deref_A(Tuple& aTuple, const size_t& aIdx) {
  aTuple._a = A[aIdx];
}

void
deref_AB(Tuple& aTuple, const size_t& aIdx) {
  aTuple._a = A[aIdx];
  aTuple._b = B[aIdx];
}

void
deref_ABC(Tuple& aTuple, const size_t& aIdx) {
  aTuple._a = A[aIdx];
  aTuple._b = B[aIdx];
  aTuple._c = C[aIdx];
}

....

void
deref_ABCDEFG(Tuple& aTuple, const size_t& aIdx) {
  aTuple._a = A[aIdx];
  aTuple._b = B[aIdx];
  aTuple._c = C[aIdx];
  aTuple._d = D[aIdx];
  aTuple._e = E[aIdx];
  aTuple._f = F[aIdx];
  aTuple._g = G[aIdx];
}

注意,A,B,C,...,G是简单数组(全局声明).数组填充整数.

方法" deref_* ",只是将数组中的一些值(通过索引 - aIdx访问)分配给给定的struct参数" aTuple ".我首先将给定结构的单个字段指定为参数,然后一直继续到所有字段.也就是说,每个方法分配的字段比前一个字段多一个.使用从0开始的索引(aIdx)到数组的MAX大小来调用方法"deref_*"(顺序地,数组具有相同的大小).该索引用于访问数组元素,如代码所示 - 非常简单.

现在,考虑图形(http://docdro.id/AUSil1f),它描述了以2000万(size_t = 8字节)整数开始的数组大小的性能,最大为24 m(x轴表示数组大小).

对于具有2100万个整数(size_t)的数组,接触至少5个不同数组(即deref_ACDE ... G)的方法的性能会下降,因此您将在图中看到峰值.然后,对于具有22 m整数及其后的数组,性能会再次提高.我想知道为什么只有21米的阵列大小才会发生这种情况？只有当我在具有CPU的服务器上进行测试时才会发生这种情况:Intel(R)Xeon(R)CPU E5-2690 v2 @ 3.00GHz,但不是Haswell,即v3.显然,这是英特尔已知的问题并已得到解决,但我不知道它是什么,以及如何改进v2的代码.

我非常感谢你身边的任何暗示.

Answer 1

我怀疑您可能会看到缓存库冲突。Sandybridge/Ivybridge (Xeon Exxxx v1/v2) 有它们，Haswell (v3) 没有。

来自 OP 的更新：这是 DTLB 未命中。通常，只有当您的工作集适合缓存时，缓存库冲突才会成为问题。每个时钟读取 8B 次（而不是 2 次）的限制不应阻止 CPU 跟上主内存的速度，即使是单线程也是如此。（8B * 3GHz = 24GB/s，大约等于主存顺序读取带宽。）

我认为有一个性能计数器，您可以使用它perf或其他工具进行检查。

引用Agner Fog 的微架构文档（第 9.13 节）：

缓存库冲突

数据高速缓存中的每个连续 128 字节或两个高速缓存行被分为 8 个组，每个组 16 个字节。如果两个存储器地址具有相同的存储体编号，即如果两个地址中的位4-6相同，则不可能在同一时钟周期内进行两次存储器读取。

; Example 9.5. Sandy bridge cache
mov eax,  [rsi]         ; Use bank 0, assuming rsi is divisible by 40H
mov ebx,  [rsi+100H]    ; Use bank 0. Cache bank conflict
mov ecx,  [rsi+110H]    ; Use bank 1. No cache bank conflict

更改数组的总大小会更改具有相同索引的两个元素之间的距离（如果它们或多或少是从头到尾排列的）。

如果将每个数组对齐到不同的 16B 偏移量（模 128），这将对 SnB/IvB 有所帮助。对每个数组中相同索引的访问将位于不同的缓存组中，因此可以并行发生。实现这一点就像分配 128B 对齐的数组一样简单，并在每个数组的开头添加 16*n 个额外字节。（将最终释放的指针与取消引用的指针分开跟踪将很麻烦。）

如果写入结果的元组与读取的地址具有相同的地址（模 4096），那么您也会得到错误的依赖。（即从数组之一读取可能必须等待存储到元组。）有关详细信息，请参阅 Agner Fog 的文档。我没有引用该部分，因为我认为缓存库冲突是更可能的解释。Haswell仍然存在错误依赖问题，但缓存库冲突问题完全消失了。