c++ - Forwards vs Backwards 数组行走

Question

首先让我以我知道这类微优化很少具有成本效益这一事实作为开头。我很好奇东西是如何工作的。对于所有高速缓存线编号等，我考虑的是 x86-64 i5 Intel CPU。对于不同的 CPU，这些数字显然会有所不同。

我经常认为向前移动数组比向后移动更快。我相信这是因为拉入大量数据是以面向前的方式完成的——也就是说，如果我读取字节 0x128，那么缓存线(假设长度为 64 字节)将以字节 0x128 读取—— 0x191 包括在内。因此，如果我要访问的下一个字节位于 0x129，那么它已经在缓存中。

但是，读了一点之后，我现在的印象是这实际上并不重要？因为缓存行对齐将在最近的 64 可分边界处选择起点，所以如果我选择字节 0x127 开始，我将加载 0x64-0x127 (含)，因此缓存中的数据将用于我的向后走。当从 0x128 转换到 0x127 时，我会遇到缓存缺失，但这是我为这个示例选择地址的位置的结果，而不是任何现实世界的考虑。

我知道缓存线是作为 8 字节 block 读入的，因此如果我们向后走，则必须在第一个操作开始之前加载完整的缓存线，但我怀疑这会产生巨大的影响区别。

如果我就在这里，有人可以澄清一下吗？老我错了？我已经搜索了一整天，但仍然无法得到最终答案。

tl;dr:我们在数组中行走的方向真的那么重要吗？它真的有区别吗？过去有什么不同吗？ (到 15 年前左右)

我用下面的基本代码测试过，前后看到的结果是一样的:

#include <windows.h>
#include <iostream>
// Size of dataset
#define SIZE_OF_ARRAY 1024*1024*256
// Are we walking forwards or backwards?
#define FORWARDS 1

int main()
{
    // Timer setup
   LARGE_INTEGER StartingTime, EndingTime, ElapsedMicroseconds;
   LARGE_INTEGER Frequency;

   int* intArray = new int[SIZE_OF_ARRAY];
    // Memset - shouldn't affect the test because my cache isn't 256MB!
   memset(intArray, 0, SIZE_OF_ARRAY);

    // Arbitrary numbers for break points
   intArray[SIZE_OF_ARRAY - 1] = 55;
   intArray[0] = 15;

   int* backwardsPtr = &intArray[SIZE_OF_ARRAY - 1];

   QueryPerformanceFrequency(&Frequency); 
   QueryPerformanceCounter(&StartingTime);

    // Actual code
   if (FORWARDS)
   {
    while (true)
    {
        if (*(intArray++) == 55)
            break;
    }
   }
   else
   {
    while (true)
    {
        if (*(backwardsPtr--) == 15)
            break;
    }
   }

    // Cleanup
   QueryPerformanceCounter(&EndingTime);
   ElapsedMicroseconds.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;
   ElapsedMicroseconds.QuadPart *= 1000000;
   ElapsedMicroseconds.QuadPart /= Frequency.QuadPart;

   std::cout << ElapsedMicroseconds.QuadPart << std::endl;

    // So I can read the output
   char a;
   std::cin >> a;
   return 0;
}

对于 A) Windows 代码和 B) Hacky 实现，我深表歉意。它被放在一起来检验一个假设，但不能证明推理。

任何有关步行方向如何产生影响的信息，不仅是缓存，还有其他方面，将不胜感激!

Answer 1

正如您的实验所表明的那样，没有区别。与处理器和 L1 高速缓存之间的接口(interface)不同，内存系统处理完整的高速缓存行，而不是字节。正如@user657267 指出的那样，存在特定于处理器的预取器。这些可能偏好向前而不是向后，但我对此深表怀疑。所有现代预取器都检测方向而不是假设它们。此外，它们还检测步幅。它们涉及极其复杂的逻辑，而且像方向这样简单的东西不会成为它们的失败。

简短的回答:朝任何一个你想要的方向前进，并享受相同的性能!