为什么缓存读取未命中比写入未命中更快？

Question

我需要使用另一个数组(readArray)计算一个数组(writeArray),但问题是数组之间的索引映射是不一样的(writeArray的索引x处的值必须使用readArray的索引y处的值计算)所以它不是很缓存友好.

但是我可以选择循环浏览readArray还是顺序浏览writeArray.

所以这是一个简化的代码:

int *readArray = new int[ARRAY_SIZE];       // Array to read
int *writeArray = new int[ARRAY_SIZE];      // Array to write
int *refArray = new int[ARRAY_SIZE];        // Index mapping between read and write, could be also array of pointers instead indexes

// Code not showed here : Initialization of readArray with values, writeArray with zeroes and refArray with random indexes for mapping between readArray and writeArray (values of indexes between 0 and ARRAY_SIZE - 1)

// Version 1: Random read (browse writeArray/refArray sequentially)
for (int n = 0; n < ARRAY_SIZE; ++n) {
    writeArray[n] = readArray[refArray[n]];
}

// Version 2: Random write (browse readArray/refArray sequentially)
for (int n = 0; n < ARRAY_SIZE; ++n) {
    writeArray[refArray[n]] = readArray[n];
}

我认为高速缓存读取丢失比写入未命中要慢(因为如果下一条指令取决于读取数据,CPU需要在读取完成之前等待,但是为了写入它不需要等待处理下一条指令)但是要分析它似乎版本1比版本2快(版本2比版本1慢大约50%).

我也尝试了这个:

// Version 3: Same as version 2 but without polluting cache
for (int n = 0; n < ARRAY_SIZE; ++n) {
    _mm_stream_si32(&writeArray[refArray[n]], readArray[n]);
}

因为我不需要读取writeArray的值,所以没有理由用写入的值污染缓存,但是这个版本比其他版本慢得多(比版本1慢6700%).

为什么写错过比读错更慢？为什么绕过缓存进行写入比使用它更慢,即使我们之后没有读取这些写入的数据？

Answer 1

让我们从最后一个版本开始 - 您所做的是将流存储用于非顺序（不是流）访问模式。您正在随机访问整数，这意味着您正在对完整缓存行进行部分写入（整数大小）。在正常写入时，这应该无关紧要，因为核心将行拉入缓存，并简单地修改必要的块（稍后当您需要存储其他东西时将其写回），但是因为您要求它避免缓存，您实际上必须在内存中执行此部分合并，这非常昂贵且阻塞。仅当您保证修改整行（例如，通过按顺序遍历数组）时，流存储才有用。

至于第二个版本 - 您的假设是正确的，如果通过加载存在数据依赖性，您将不得不等待它们，但这里没有真正的依赖链。您只有一组具有 2 级依赖关系的加载，但它们之间没有相互依赖导致任何跨迭代序列化（即迭代 n==2 和 n==3 甚至可能在 n==1 完成第一次加载之前开始）。实际上，假设您的 CPU 可以维持 N 次未完成的访问（取决于所涉及的大小和缓存级别），您将refArray并行启动前 N 个引用（假设索引计算速度快），然后是前 N 个对 的引用readArray，以及然后下一批，依此类推。

现在，由于没有数据依赖性，这就变成了带宽问题。在这种情况下，一般来说，由于它们的乱序性质，加载对于处理器来说要容易得多 - 一旦知道地址（这仅取决于快速索引计算），您就可以并行和乱序启动它们. 另一方面，需要按程序顺序观察存储（以保持内存一致性），这几乎将它们序列化（那里有一些可能的 CPU 技巧，取决于您的确切微架构，但它不会改变大图片）。

编辑：第 2 版中添加的另一个约束（我认为更重要）是内存消歧。处理器必须计算加载和存储地址，以便知道是否有任何冲突（我们知道没有，但处理器没有......）。如果负载依赖于存储，则必须阻止它，以防必须转发新数据。现在，由于负载在 OOO 机器中提前启动，因此尽早了解所有存储的地址以避免冲突（或更糟 - 失败并导致大量刷新的推测）变得至关重要