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

Question

我需要用另一个数组（readArray）计算一个数组（writeArray），但问题是两个数组之间的索引映射不同（写入数组的索引x处的值必须使用读取数组的索引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%）。

为什么写入未命中比读取未命中要慢？ 为什么即使我们在之后不读取这些写入的数据，绕过缓存进行写入也比使用缓存更慢？

- Johnmph

---

我在这个领域不是专家，但我敢打赌它与流水线有关。 - Barmar

如果您的机器处于OOO状态，则读取未命中不会阻止其他不依赖于此数据的指令。在这种情况下，读取未命中非常密集，并以流水线方式服务。写入未命中则不同，通常必须先处理写入未命中，然后才能进行任何操作以防止写入之前读取。 - user3528438

@user3528438听起来像是一个设计决策。写操作必须刷新所有读取，然后执行写入并“完成”。读操作可以进行流水线处理。你也可以反过来（读操作刷新所有写入，然后立即读取，写操作进行流水线处理），但同时进行流水线处理很困难。而且阅读比写入更常见？或者感觉应该更快。 - Yakk - Adam Nevraumont

@Yakk 我认为你没有完全理解我为什么提到OOO。缓存未命中的读取和写入都是以相同的方式进行服务的。多个写入未命中不可能发生，因为现有的未命中会使机器停顿，因此没有任何内容可以进行流水线处理。但是当机器处于OOO状态时，读取未命中不会立即导致停顿，然后下一个读取未命中可能会在当前正在服务的情况下发生。 - user3528438

@user3528438，我将OOO视为“一般的乱序”，而不是“主导的乱序模式”。如果你让读取失误停顿，而写入失误不停顿，在OOO系统中，据我所知，你可以保持内存一致性？现在，那将是一台相当无用的机器，针对写入比读取更多的代码进行优化，这是一种奇怪的生物。 - Yakk - Adam Nevraumont

是的，存储缓冲区可能会使存储看起来很便宜。这也是处理器具有两个读取端口但只有一个存储端口的基本原因。问题在于，您只是用存储器压倒了它，因此它仍然会在填充的存储缓冲区上停顿。而且，由于它们分散得很糟糕，所以无法合并存储。 - Hans Passant

Answer 1

让我们从最后一个版本开始 - 你使用流式存储来处理非顺序（不是流）访问模式。你随机访问整数，这意味着你会将部分写入（int大小）到完整的缓存行中。在正常写入时，这并不重要，因为核心会将该行拉入缓存，并仅修改必要的块（稍后在需要存储其他内容时会写回），但由于你要求避免缓存，实际上你必须在内存中进行这种部分合并，这非常昂贵且阻塞。只有在保证修改整行（例如通过按顺序遍历数组）时，流式存储才有用。

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

现在，由于没有数据依赖性，这变成了一个带宽问题。一般来说，由于其乱序特性，负载对处理器来说要容易得多 - 你可以并行和乱序地启动它们，一旦知道地址（这仅取决于快速索引计算）。另一方面，存储需要按程序顺序观察（以保持内存一致性），这几乎使它们串行化（根据您的确切微体系结构可能有一些可能的CPU技巧，但这不会改变大局）。

编辑：版本2中添加的另一个限制（我认为更为关键）是内存消歧义。处理器必须计算负载和存储地址，以确定是否存在冲突（我们知道不存在，但处理器不知道……）。如果负载依赖于存储，则必须被阻止，以防新数据必须被转发。现在，由于负载在OOO机器中提前启动，因此尽早了解所有存储的地址变得至关重要，以避免冲突（或更糟糕的是，导致大规模刷新的失败推测）。

- Leeor

---

谢谢，如果我理解正确的话，在这种情况下，例如随机读取，预取可能无法进行优化，因为CPU不会等待除非缓存已满，是这样吗？如果我们知道写入不会影响我们正在读取的内存，那么是否可以通过指令避免写入停顿？ - Johnmph

我不确定我理解预取问题的意思，但是当你没有带宽限制时，预取可以减少延迟。在这种情况下，由于您有足够的迭代次数供OOO提前运行，我怀疑它不会有用。至于避免停顿，这取决于您的微架构，但也许为每个数组使用页面上的不同偏移量会有所帮助（这也将避免我们没有提到的缓存集冲突）。 - Leeor