1

是的，这是一个家庭作业问题，我只需要朝着正确的方向前进

哪个 C++ 代码块更快，为什么？我认为它是最重要的，因为 [i] 数组是按顺序使用的，还是我在这里错了？

    double A[100][100];
    ...
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            A[i][j] = i * j;
        }
     }


    double A[100][100];
    ...
    for (int j = 0; j < 100; j++) {
    for (int i = 0; i < 100; i++) {
        A[i][j] = i * j;
    }
 }
4

2 回答 2

8

如果不运行和分析您的代码，就无法知道哪段代码更快。

我们可以猜测局部性和缓存行为将如何影响该时间（您的猜测很好），但猜测不能替代分析。（请参阅：如何分析在 Linux 中运行的 C++ 代码？）

第一个版本可能更快的一个原因：

为什么可能没有区别：

  • 整个 10000 个元素都可以放入缓存中，从而使上述优化变得毫无意义。

我想不出第二个会更快的任何原因，但我之前一直很惊讶。

于 2013-10-19T00:43:38.860 回答
5

最普遍的答案是：您需要分析两个块并凭经验查看结果。

但是，我可以为您提供大多数现代 x86、x64、PPC 和 ARM 处理器的答案，这些处理器具有分层缓存。在这些平台上，由于更好的数据局部性，顶部的会更快：它按顺序访问内存地址，因此您将更频繁地访问数据缓存。智能 x86 和 x64 实现甚至会注意到您正在以这种方式顺序读取内存，并在需要之前预取下一个缓存行。底部模式跨远程地址不按顺序访问内存，这意味着您可能会在每次读取时错过缓存。

Ulrich Drepper 对此有一篇很好的论文。他在那篇论文中的一个例子准确地展示了这两个代码块的不同之处。

作为此处的数学示例，假设您正在编程具有 64 字节高速缓存行大小和 32kb L1 数据高速缓存的 Intel Corei7。这意味着每次获取地址时，处理器还将获取该 64 字节对齐块中的所有其他数据。在那个平台上，一个 double 是 8 个字节，所以每个缓存行可以容纳 8 个。因此，上面的示例平均会在八次迭代中失败一次：每次失败后，接下来的 56 个字节也将被获取，因此接下来的七次 double* 读取将在缓存中。

下面的示例可能i同时将 100 行数据（每行一个）放入缓存：100 * 64 = 6400 字节，完全在缓存大小范围内。但也有可能超过关联缓存，这意味着两条线将映射到 L1 中的同一个 SRAM，这意味着一条将驱逐另一条。

于 2013-10-19T01:07:27.783 回答