12

我一直想知道在更好地利用 CPU 缓存方面什么更有效（众所周知，这会受益于引用的局部性）——两个循环，每个循环都迭代相同的数学数字集，每个循环都有不同的主体语句（例如为集合的每个元素调用一个函数），或者有一个循环，其主体相当于两个（或多个）主体语句。在所有循环之后，我们假设相同的应用程序状态。

在我看来，有两个循环会引入更少的缓存未命中和驱逐，因为循环使用的更多指令和数据适合缓存。我对吗？

假设：

  1. 与循环的成本相比f，调用的成本可以忽略不计g

  2. f并g单独使用大部分缓存，因此当一个又一个被调用时缓存会溢出（单循环版本的情况）

  3. 英特尔酷睿双核 CPU

  4. C语言源代码

  5. GCC 编译器，“没有额外的开关”

如果可能的话，我想要“过早的优化是邪恶的”角色之外的答案。

我提倡的双循环版本的一个示例：

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
}

for(int i = 0; i < 1000000; i++)
{
    k += g(i);
}
4

7 回答 7

10

测量就是知道。

于 2010-07-23T20:51:26.370 回答
6

直观地说，一个循环更好：您i减少了一百万次，而所有其他操作计数保持不变。

另一方面，它完全取决于f和g。如果两者都足够大，以至于它们使用的每个代码或可缓存数据几乎填满了关键缓存，那么在它们之间进行交换f并g可能完全淹没任何单个循环的好处。

正如你所说：这取决于。

于 2010-07-23T21:15:49.973 回答
6

我可以看到三个变量（即使在看似简单的代码块中）：

  • 做什么f()和g()做什么？其中一个能否使所有指令缓存行无效（有效地将另一个推出）？L2指令缓存中也会发生这种情况吗（不太可能）？然后只保留其中一个可能是有益的。注意：倒数并不意味着“有一个循环”，因为：
  • 根据?对大量数据进行操作f()和操作 然后，很高兴知道它们是否对同一组数据进行操作 - 您必须再次考虑对两个不同的数据集进行操作是否会因缓存未命中而使您陷入困境。g()i
  • 如果f()并且g()确实是您第一次陈述的那种原始状态，并且我假设代码大小以及运行时间和代码复杂性，缓存位置问题不会出现在像这样的小块代码中 - 您最大的担忧是如果其他一些进程被安排有实际工作要做，并且在轮到你的进程运行之前使所有缓存无效。

最后的想法：考虑到像上面这样的过程在您的系统中可能很少发生（而且我非常随意地使用“稀有”），您可以考虑将您的两个函数都内联，并让编译器展开循环。那是因为对于指令缓存，故障返回到 L2 没什么大不了的，并且包含的​​单个缓存行在该i, j, k循环中失效的可能性看起来并不那么可怕。但是，如果不是这种情况，一些更多的细节会很有用。

于 2010-07-24T06:51:45.773 回答
2

将循环分成更小的块是个好主意。它可以大大提高缓存命中率，并且可以对性能产生很大影响...

从你的例子：

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
}

for(int i = 0; i < 1000000; i++)
{
    k += g(i);
}

我要么将两个循环融合为一个循环，如下所示：

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
    k += g(i);
}

如果这是不可能的，请执行称为 Loop-Tiling 的优化：

#define TILE_SIZE 1000 /* or whatever you like - pick a number that keeps   */
                       /* the working-set below your first level cache size */

int i=0; 
int elements = 100000;

do {
  int n = i+TILE_SIZE; 
  if (n > elements) n = elements;

  // perform loop A
  for (int a=i; a<n; a++)
  {
    j += f(i);
  }

  // perform loop B
  for (int a=i; a<n; a++)
  {
    k += g(i);
  }

  i += n
} while (i != elements)

循环平铺的技巧是，如果循环共享访问模式，则第二个循环体有机会重用第一个循环体已经读入缓存的数据。如果您执行循环 A 一百万次，则不会发生这种情况，因为缓存不足以容纳所有这些数据。

将循环分成更小的块并一个接一个地执行它们将有很大帮助。诀窍是将内存的工作集限制在一级缓存的大小以下。我的目标是缓存大小的一半，因此在中间执行的其他线程不会把我的缓存弄得那么乱。

于 2010-07-25T22:07:32.073 回答
2

您的问题不够清楚，无法给出远程准确的答案，但我想我了解您的目标。您正在迭代的数据足够大，以至于在您到达终点之前，您将开始驱逐数据，以便第二次（第二次循环）您迭代它，如果不是全部，则必须再次读取。

如果两个循环连接在一起，以便为第一个操作获取每个元素/块，然后在第二个操作中已经在缓存中，那么无论数据相对于缓存有多大，如果不是所有第二个操作，大多数（如果不是全部）将从缓存中获取他们的数据。

诸如缓存的性质，循环被数据驱逐然后被获取驱逐数据等各种事情可能会导致第二次操作的一些失误。在带有操作系统的电脑上，随着其他程序获得时间片，会发生很多驱逐。但是假设一个理想的世界，对数据索引 i 的第一个操作将从内存中获取它，第二个操作将从缓存中获取它。

调整缓存充其量是困难的。我经常证明，即使是嵌入式系统，也没有中断、单一任务、相同的源代码。执行时间/性能可以通过简单地改变编译器优化选项、改变编译器、编译器品牌或编译器版本、gcc 2.x vs 3.x vs 4.x（顺便说一句，gcc 不一定能产生更快的代码）而发生巨大变化)（并且在很多目标上都非常擅长的编译器在任何特定目标上都不是很擅长）。相同的代码不同的编译器或选项可以将执行时间改变几倍、快 3 倍、快 10 倍等。一旦您开始使用或不使用缓存进行测试，它会变得更加有趣。在您的启动代码中添加一个 nop，以便您的整个程序在内存中移动一条指令，并且您的缓存行现在在不同的位置命中。相同的编译器相同的代码。用两个 nop、三个 nop 等重复此操作。相同的编译器，相同的代码，你可以看到百分之几十（对于我那天用那个编译器在那个目标上运行的测试）差异越来越大。这并不意味着你不能调整缓存，它只是意味着试图弄清楚你的调整是帮助还是伤害可能很困难。正常的答案只是“计时并查看”，但这不再起作用了，那天你可能会在你的计算机上使用那个编译器的程序获得很好的结果。但是明天在您的计算机上或在其他人的计算机上的任何一天，您可能会让事情变得更慢而不是更快。

假设我正确理解了您的问题，我认为单循环通常可能更快。

于 2010-07-24T05:55:59.433 回答
1

如果我在代码中遇到双循环版本，没有解释性注释，我会想知道程序员为什么这样做，并且可能认为该技术质量可疑，而单循环版本不会令人惊讶，评论与否。

但是，如果我遇到双循环版本以及诸如“我正在使用两个循环，因为它在 CPU Y 上的缓存中运行速度快 X%”之类的评论，至少我不会再对代码感到困惑，尽管我仍然会质疑它是否真实并适用于其他机器。

于 2010-07-24T06:22:58.387 回答
-1

这似乎是编译器可以为您优化的东西，因此与其试图自己弄清楚并使其快速运行，不如使用任何方法使您的代码更清晰易读。如果您真的必须知道，请为您的应用程序使用的输入大小和计算类型两种方法计时（尝试您现在拥有的代码，但多次重复您的计算并禁用优化）。

于 2010-07-23T20:38:06.073 回答