CPU缓存关键步幅测试，根据访问类型给出意外结果

Question

最近这个关于SO的问题和给出的答案让我感到很无知，受此启发，我决定花点时间来学习更多关于CPU缓存的知识，并编写了一个小程序来验证我是否正确（恐怕很可能不正确）。我将首先写出我的预期所依据的假设，所以如果这些假设是错误的，你可以在这里阻止我。根据我读到的，总的来说：

null

我的第一个问题是：这些假设是否正确？

假设它们是，我尝试使用这些概念，这样我就可以看到它们对程序的具体影响。我编写了一个简单的测试，分配一个b字节的内存缓冲区，并从缓冲区开始以给定步长的固定增量重复访问该缓冲区的位置（这意味着，如果b是14，步长是3，我只重复访问位置0、3、6、9和12，如果b是13、14或15，情况也一样）：

int index = 0;
for (int i = 0; i < REPS; i++)
{
    index += STEP;
    if (index >= B) { index = 0; }
    buffer[index] = ...; // Do something here!
}

基于上述假设，我的预期是：

1. 当将step设置为临界跨距（即高速缓存行的大小乘以高速缓存中的集合数，或L*s)时，性能应该比将step设置为（例如，(L*s)+1时差得多，因为我们将只访问映射到同一集合中的内存位置，从而迫使高速缓存行更频繁地从该集合中被逐出，从而导致高速缓存丢失率更高；
2. 当step等于临界步长时，性能不应受到缓冲区的大小b的影响，只要该大小不太小（否则访问的位置太少，缓存未命中的次数也会更少）；否则，性能会受到b的影响，因为使用较大的缓冲区，我们更有可能访问映射到不同集合中的位置（特别是如果step不是2的倍数）；
3. 从每个缓冲区位置读取和写入时的性能损失应该比只写入这些位置时的性能损失更大：写入内存位置不需要等待提取相应行，因此访问映射到相同集的内存位置的事实（同样，通过使用关键步长作为步骤)应该会产生较小的影响。

所以我使用了RightMark内存分析器来找出我的L1 CPU数据缓存的参数，调整了我的程序中的大小，并进行了试用。这就是我编写主周期的方式(onlywriteTocache是一个可以从命令行设置的标志）：

    ...
    for (int i = 0; i < REPS; i++)
    {
        ...
        if (onlyWriteToCache)
        {
            buffer[index] = (char)(index % 255);
        }
        else
        {
            buffer[index] = (char)(buffer[index] % 255);
        }
    }

结果简而言之：

• 预期1）和2）得到确认；
• 期望值%3）未确认。

这一事实使我震惊，使我觉得有些事情我做得不太对。当b为256 MB且step等于临界步幅时，测试（在GCC 4.7.1上用-o3编译）显示：

null

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;

// Auxiliary functions

constexpr int pow(int base, int exp)
{
    return ((exp == 0) ? 1 : base * pow(base, exp - 1));
}

int main(int argc, char* argv[])
{
    //======================================================================
    // Define behavior from command-line arguments
    //======================================================================

    bool useCriticalStep = false;
    bool onlyWriteToCache = true;
    size_t BUFFER_SIZE = pow(2, 28);
    size_t REPS = pow(2, 27);

    if (argc > 0)
    {
        for (int i = 1; i < argc; i++)
        {
            string option = argv[i];
            if (option == "-c")
            {
                useCriticalStep = true;
            }
            else if (option == "-r")
            {
                onlyWriteToCache = false;
            }
            else if (option[1] == 's')
            {
                string encodedSizeInMB = option.substr(2);
                size_t sizeInMB = atoi(encodedSizeInMB.c_str());
                BUFFER_SIZE = sizeInMB * pow(2, 20);
            }
            else if (option[1] == 'f')
            {
                string encodedNumOfReps = option.substr(2);
                size_t millionsOfReps = atoi(encodedNumOfReps.c_str());
                REPS = millionsOfReps * pow(10, 6);
            }
        }
    }

    //======================================================================
    // Machine parameters
    //======================================================================

    constexpr int CACHE_SIZE = pow(2, 15);
    constexpr int CACHE_LINE_SIZE = 64;
    constexpr int CACHE_LINES_PER_SET = 8;
    constexpr int SET_SIZE = CACHE_LINE_SIZE * CACHE_LINES_PER_SET;
    constexpr int NUM_OF_SETS = CACHE_SIZE / SET_SIZE;

    //======================================================================
    // Print out the machine parameters
    //======================================================================

    cout << "CACHE SIZE: " << CACHE_SIZE / 1024 << " KB" << endl;
    cout << "CACHE LINE SIZE: " << CACHE_LINE_SIZE << " bytes" << endl;
    cout << "CACHE LINES PER SET: " << CACHE_LINES_PER_SET << endl;
    cout << "SET SIZE: " << SET_SIZE << " bytes" << endl;
    cout << "NUMBER OF SETS: " << NUM_OF_SETS << endl;

    fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;

    //======================================================================
    // Test parameters
    //======================================================================

    const int STEP = NUM_OF_SETS * CACHE_LINE_SIZE + (useCriticalStep ? 0 : 1);

    //======================================================================
    // Print out the machine parameters
    //======================================================================

    cout << "BUFFER SIZE: " << BUFFER_SIZE / pow(2, 20) << " MB" << endl;
    cout << "STEP SIZE: " << STEP << " bytes" << endl;
    cout << "NUMBER OF REPS: " << REPS << endl;

    fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;

    //======================================================================
    // Start the test
    //======================================================================

    char* buffer = new char[BUFFER_SIZE];

    clock_t t1 = clock();

    int index = 0;
    for (size_t i = 0; i < REPS; i++)
    {
        index += STEP;
        if (index >= BUFFER_SIZE)
        {
            index = 0;
        }

        if (onlyWriteToCache)
        {
            buffer[index] = (char)(index % 255);
        }
        else
        {
            buffer[index] = (char)(buffer[index] % 255);
        }
    }

    clock_t t2 = clock();

    //======================================================================
    // Print the execution time (in clock ticks) and cleanup resources
    //======================================================================

    float executionTime = (float)(t2 - t1) / CLOCKS_PER_SEC;
    cout << "EXECUTION TIME: " << executionTime << "s" << endl;

    delete[] buffer;
}

如果你能读完这个长问题，请提前向你表示感谢。

Answer 1

关于你的第三个期望，你是对的。正如你所料。更多详情请查看“每个程序员都应该知道的关于内存的知识”。这是一个解释内存层次结构的优秀系列文章。

那么为什么第三个问题很难得到证实：有两个主要原因。一个是内存分配，另一个是虚-物理地址转换。

内存分配

以int数组的形式分配一组k大内存区域（类似于512MB)，并将它们全部对准4096b的页面边界。现在迭代内存区域中的所有元素，并将k的更多区域增量地添加到您的实验中。测量时间，并通过读取的元素数进行规格化。

代码可能如下所示：

#define N 10000000
for(size_t i=0; i < k; ++i) {

   size_t sum=0;
   clock_t t1= clock();
   for(size_t j=0; j < N; ++j) {
       for(size_t u=0; u<i; ++u) {
           sum += data[u][j];
       }
   }

   clock_t t2= clock();

}

那么会发生什么。所有大的内存区域对齐到4K，并且基于前面的假设，相同行的所有元素将映射到相同的高速缓存集。当循环中的投影内存区域数大于缓存的关联度时，所有的访问都会招致一次缓存未命中，每个元素的平均处理时间会增加。

如何处理写入取决于如何使用高速缓存行和CPU。现代CPU应用MESI协议来处理对高速缓存行的写入，以确保所有各方在内存上具有相同的视图（高速缓存一致性）。通常，在写入高速缓存行之前，必须先读高速缓存行，然后再写回高速缓存行。是否识别回写取决于您访问数据的方式。如果您再次重新读取高速缓存行，您很可能不会注意到差异。

然而，虽然程序员通常对数据如何存储在CPU缓存中没有影响，但与写入相比，有一点差别。可以执行所谓的流式写入，而不污染缓存，而是直接写入内存。这些写入也称为非时态写入。