如何计算内存访问时间？

Question

我创建了一个大型布尔二维数组（5000X5000，总共 250 亿个元素，大小为 23MB）。然后我循环遍历并用随机的 true 或 false 实例化每个元素。然后我循环并读取每个元素。所有 2500 万个元素的读取时间约为 100 毫秒。

23MB 太大，无法放入 CPU 缓存，而且我认为我的程序太简单，无法从任何类型的编译器优化中受益，所以我得出的结论是否正确，即该程序在大约 100 毫秒内从 RAM 读取 2500 万个元素？

    #include "stdafx.h"
    #include <iostream>
    #include <chrono>
    using namespace std;

    int _tmain(int argc, _TCHAR* argv[])
    {
        bool **locs;
        locs = new bool*[5000];
        for(int i = 0; i < 5000; i++)
            locs[i] = new bool[5000];
        for(int i = 0; i < 5000; i++)
            for(int i2 = 0; i2 < 5000; i2++)
                locs[i][i2] = rand() % 2 == 0 ? true : false;
        int *idx = new int [5000*5000];
        for(int i = 0; i < 5000*5000; i++)
            *(idx + i) = rand() % 4999;

        bool val;
        int memAccesses = 0;
        auto start = std::chrono::high_resolution_clock::now();
        for(int i = 0; i < 5000*5000; i++) {
            val = locs[*(idx + i)][*(idx + ++i)];
            memAccesses += 2;
        }
        auto finish = std::chrono::high_resolution_clock::now();

        std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count() << " ns\n";
        std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(finish-start).count() << " ms\n";
        cout << "TOTAL MEMORY ACCESSES: " << memAccesses << endl;
        cout << "The size of the array in memory is " << ((sizeof(bool)*5000*5000)/1048576) << "MB";

        int exit; cin >> exit;
        return 0;
    }

    /*
    OUTPUT IS:

        137013700 ns
        137 ms
        TOTAL MEMORY ACCESSES: 25000000
        The size of the array in memory is 23MB
    */

Answer 1

正如其他答案所提到的，您看到的“速度”（即使 CPU 正在执行您的代码并且它没有被编译器剥离）约为 250 MBps，这对于现代系统来说是非常非常低的数字。

然而，你的方法对我来说似乎有缺陷（诚然，我不是基准测试专家。）以下是我看到的问题：

1. 对于诸如此类的任何基准测试，即使是最简单的形式，您也需要区分随机访问和顺序访问。内存不是随机访问设备（尽管它的名字如此）并且在这里表现得很差。您的代码似乎是随机访问内存，因此您将其作为限定符添加到您的结论中：您“在大约 100 毫秒内从 RAM 的随机位置读取 2500 万个元素”。
2. 此类基准测试的另一个方面是延迟与吞吐量的概念。再说一次，如果你想从你的数字和时间中得出任何结论，你需要知道你到底在测量什么。

3. 您对内存访问的计数不正确。根据编译器生成的具体代码，此行：

   val = locs[*(idx + i)][*(idx + ++i)];
   

   实际上可能会访问内存系统 4 到 9 次。

   • 最好的情况是，如果i、idx、locs和val都在寄存器中或者消除了对它们的访问，那么您需要 read *(idx + i)、 read locs[*(idx + i)]（记住这locs是指向数组的指针数组，而不是二维数组） read *(idx + ++i)，最后是 read locs[*(idx + i)][*(idx + ++i)]。其中一些可能会被缓存，但这不太可能，因为缓存抖动正在发生。
   • 在最坏的情况下，除了上述之外，您还需要两次访问++i（读取，然后写回），一次访问idx，一次访问locs，一次访问val。我不知道，您甚至可能需要对单个读取进行另一次读取i和/或对两次idx出现进行两次读取（由于指针别名等原因）。
4. 您需要注意，内存永远不会以单个字节甚至单词的形式进行访问。内存始终以高速缓存行为单位进行读写。尽管目前最常见的大小是 64 字节，但缓存行大小可能因系统而异。因此，每次读取不在缓存中的内存位置时，都会从 RAM 中加载 64 字节（或更多）。如果您正在读取的内存位置位于缓存行边界（一个缓存行中的一些字节和下一个缓存行中的一些字节），那么您正在从 RAM 加载两个缓存行。如果有一个健全的编译器和内存中正确对齐的变量，这种情况不会经常发生，但有可能发生。因此，您至少必须将计算出的使用带宽乘以缓存行的大小。
5. 但是，如果您正在访问缓存中已经存在的内存位置，则不会从 RAM 加载任何内容。您也需要在结论中考虑这一点。
6. 您还需要考虑高速缓存行逐出、高速缓存的关联性、级别数量、某些高速缓存级别在指令和数据之间共享而某些则不然、某些在内核之间共享而某些则不共享以及许多高速缓存级别评估缓存和内存性能时的其他事项。
7. DRAM 芯片还具有许多奇怪且复杂的行为和特征。某些内存位置在其他内存位置之后读取速度更快（由于行和列的排列），由于刷新周期，某些访问可能会延迟很长时间（以 CPU 速度），其他设备可能正在使用 RAM 或总线我对现代存储芯片的操作还很不熟悉，甚至我知道那是一团糟。
8. 您必须考虑编译器优化对代码的影响。这意味着您必须在编译器完成后以汇编形式查看代码。您需要查看生成的程序集才能知道您的代码实际上在做什么：是否优化了内存访问以及哪些内存访问被优化。

总而言之，我认为您不能从您的程序中得出很多有用的信息。抱歉，记忆是非常复杂的！