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

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%）。

为什么write miss比read miss慢？为什么绕过缓存写入比使用它更慢，即使我们在之后不读取这些写入数据？

Answer 1

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

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

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

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

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

Why cache read miss is faster than write miss?

c++

performance

caching

cpu-cache