c - 读写位置之间的距离对缓存性能有影响吗？

Question

我有一个大小为 n 的已满缓冲区，以及一个大小为 n 的后继缓冲区，该缓冲区为空。我想在位置 i 的第一个缓冲区中插入一个值，但是为了做到这一点，我需要向前移动一段内存，因为缓冲区已满(即顺序插入)。我在这里有两个选择:

更喜欢靠近阅读(相邻):

1. 将第一个缓冲区的最后一个值插入第二个。
2. 在第一个缓冲区中的 i 和 n - 1 之间移动。
3. 在 i 处插入。

喜欢更少的步骤:

1. 将范围 i 到 n - 1 从第一个缓冲区复制到第二个缓冲区。
2. 在 i 处插入。

我能找到的大部分内容都只讨论了读取上下文中的局部性，我想知道是否应该考虑读取和写入内存之间的距离。

Answer 1

Does the distance between read and write locations have an effect on cache performance?

是的。通常(不包括 CPU 可以用新数据写入整个缓存行的罕见情况)CPU 必须在执行写入之前将缓存行的最新版本提取到其缓存中。如果缓存行已经在缓存中(例如，由于先前读取的一些其他数据恰好在同一缓存行中)，则 CPU 将不需要在执行写入之前获取缓存行。

请注意，还有其他各种怪癖(缓存别名、TLB 未命中等)；所有这一切都取决于具体情况和哪个 CPU(例如，如果所有进程的数据都适合 CPU 的缓存，则不涉及共享内存，并且没有任务切换或其他进程使用 CPU；那么你可以假设无论如何，一切都将始终在缓存中。

I want to insert a value within the first buffer at position i, but I would need to move a range of memory forward in order to do that, since the buffer is full (ie. sequential insert).

没有更多信息(这种情况发生的频率、涉及的数据量等)，我真的无法提出任何建议。然而(乍一看，没有太多信息)，整个想法似乎很糟糕。更具体地说，听起来您正在添加一堆麻烦来使两个较小的数组的行为与一个较大的数组的行为完全相同(然后担心插入的成本，因为数组通常不适合插入)。