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

Question

我一直想知道更好地利用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);
}

Answer 1

衡量就是知道.

Answer 2

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

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

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

Answer 3

直观地说,一个循环更好:你增加i了一百万次,所有其他操作数保持不变.

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

正如你所说:这取决于.