两个循环体或一个(结果相同)

我可以看到三个变量(即使在一段看似简单的代码中):

• f() 和 g() 你知道吗?其中一个是否可以使所有指令缓存线失效(有效地将另一条缓存线推出)?二级指令缓存中是否也会发生这种情况(不太可能)?那么只保留其中一个可能是有益的。 相反并不意味着“有一个单循环”,因为:
• 做 和 g() i 同一套 同样,您必须考虑是否在两个不同的集合上操作会通过缓存未命中而使您出错。
• f() 和 g() 我假设在代码大小、运行时间和代码复杂度方面,缓存局部性问题不会出现在像这样的小块代码中—您最关心的是,是否安排了其他进程来执行实际工作,并使所有缓存失效,直到轮到进程运行为止。

i, j, k 在那个循环中无效看起来没那么可怕。然而,如果不是这样的话,更多的细节将是有用的。

测量就是知道。

i 减少了一百万次,所有其他操作计数保持不变。

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

正如你所说:这要看情况。

你的问题还不够清楚,不能给出一个稍微准确的答案,但我想我明白你的意思。您正在迭代的数据足够大,以至于在到达末尾之前,您将开始逐出数据,以便您在第二次(第二个循环)中对其进行迭代时,必须再次读取一些(如果不是全部的话)。

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

各种各样的事情,比如缓存的性质,循环被数据逐出,然后被提取,逐出数据可能会导致第二个操作的一些遗漏。在一台装有操作系统的pc机上,其他程序获取时间片时,会发生大量的逐出操作。但假设一个理想世界,对数据索引i的第一个操作将从内存中获取数据,第二个操作将从缓存中获取数据。

优化缓存充其量也很困难。我经常演示,即使使用嵌入式系统,也没有中断、单个任务、相同的源代码。通过简单地更改编译器优化选项、更改编译器(无论是编译器品牌还是编译器版本),执行时间/性能都会发生巨大变化,gcc2.x vs 3.x vs 4.x(顺便说一句,gcc不一定能用更新的版本生成更快的代码)(而且一个编译器在很多目标上都很好,但在任何一个特定目标上都不是很好)。相同的代码不同的编译器或选项可以改变执行时间几倍,3倍快,10倍快,等等。一旦你进入测试有或没有缓存,它变得更加有趣。在启动代码中添加一个nop,这样整个程序就可以在内存中移动一条指令,而缓存线现在会在不同的地方命中。相同的编译器相同的代码。用两个nop,三个nop,等等重复这个步骤。同样的编译器,同样的代码,你可以看到百分之十的差异(对于我那天用那个编译器在那个目标上运行的测试),好的和坏的。这并不意味着你不能调整缓存,它只是意味着试图找出你的调整是帮助还是伤害可能是困难的。正常的答案是“计时看”,但这已经不起作用了,你可能会在你的电脑上得到很好的结果,那一天与该程序的编译器。但是明天在你的电脑上或者任何一天在别人的电脑上你可能会让事情变慢而不是变快。你需要理解为什么这个或那个改变使它更快,也许它与你的代码无关,你的电子邮件程序可能在一个测试期间在后台下载了很多邮件,而不是在另一个测试期间。

假设我正确地理解了你的问题,我认为单循环通常更快。

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

从你的例子来看:

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);
}

当然,如果这是不可能的,请执行称为循环平铺的优化:

#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)

将循环分解成更小的块,然后一个接一个地执行它们,这将非常有帮助。诀窍是将工作内存集限制在一级缓存的大小以下。我的目标是缓存大小的一半,这样在这两者之间执行的其他线程就不会把我的缓存搞得一团糟。。

这看起来像是编译器可以为您优化的东西,所以不要试图自己去弄清楚它并使之快速,而是使用任何方法使您的代码更清晰易读。如果您真的必须知道,请计时应用程序使用的输入大小和计算类型的两种方法(尝试现在的代码,但要多次重复计算并禁用优化)。

如果我在代码中遇到两个循环的版本,没有解释性的注释,我会想为什么程序员会这样做,并且可能会认为该技术的质量可疑,而一个单循环的版本不会令人惊讶,注释或不注释。

但是,如果我遇到了双循环版本以及类似“我使用双循环是因为它在CPU Y上的缓存中运行速度快了X%”这样的注释,至少我不再对代码感到困惑,尽管我仍然怀疑它是否正确,是否适用于其他机器。