性能分崩离析一个循环分为两个循环

假设你有一个简单的像下面的循环......

for(int i=0;i<10;i++) 
{ 
    //statement 1 
    //statement 2 
}

假设语句1和语句2是O（1 ）。除了“启动”另一个循环的小开销之外，将循环分成两个循环（不是嵌套循环，而是顺序循环）的速度同样快吗？例如...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
} 
for(int i=0;i<10;i++) 
{ 
    //statement 2 
}

为什么我问这么愚蠢的问题是，我有过的所有对象必须环路碰撞检测系统（CDS）。我想“划分”我的CDS系统的功能，这样我就可以简单地调用

cds.update(objectlist);

，而不必打破我的CDS系统了。（不要太担心我的CDS实现......我想我知道我在做什么，我只是不知道如何解释它，我真正需要知道的是如果我在循环中获得巨大的性能打击通过我的所有对象再次。

来源

2012-03-09 Matthew

这取决于你的应用程序。

可能的缺点（分裂）：

你的数据不适合到L1数据缓存，因此你一旦加载它的第一循环，然后重新装入第二循环

可能的收益（分裂）：

你的循环续AINS许多变量，分裂有助于降低寄存器/堆栈压力和优化它变成更好的机器代码
功能使用垃圾L1指令缓存，以便缓存加载在每次迭代，而通过拆分可以管理到装载一次（只），在每个循环

的第一次迭代这些列表肯定不全面，但已经可以感觉到有代码和数据之间的紧张关系。所以当我们两个都不知道的时候，我们很难接受一个受过教育/猜测的猜测。

在有疑问：轮廓。使用callgrind，在每种情况下检查缓存未命中，检查执行的指令数量。测量花费的时间。

来源

2012-03-09 14:03:39

至于大O的复杂性而言，这不会有所作为，如果1环为O（n），就这样是2循环的解决方案。
作为就微观优化而言，很难说，循环的成本相当小，我们不知道访问对象的成本是多少（如果它们在一个向量中，那么它应该相当小），但有很多考虑给予有用的答案。

来源

2012-03-09 13:30:13 stefaanv

你在正确的指出通过创建第二个循环会有一些性能开销。因此，它不能“同样快”;因为这个开销虽然很小，但仍然是开销。

我不会尝试智能地谈论碰撞系统应该如何建立，但如果你想优化性能，最好避免不必要的建设控制结构，如果你可以不拉你的头发管理。

记住，过早的优化是你可以做的最糟糕的事情之一。在我看来，当你遇到性能问题时，担心优化。

来源

2012-03-09 13:30:21 patrickn

作为stefaanv指出，通过所有对象循环第二次的成本是不确定的你提供的信息。 – patrickn 2012-03-09 13:33:05

我还会注意到，您发布的两个控件结构解决了不同的问题，因此在性能上不易对比。 – patrickn 2012-03-09 13:41:24

不知道更多的细节和没有实际的测量，不可能说哪个版本更快。缓存，数据和指令，以及分支预测（和表）和推测执行都为当今的优化增加了很多复杂性。虽然过早优化的好点。先在现实世界中测量，然后进行优化。 – 2012-03-16 16:34:42

在算法复杂度分裂循环方面没有什么区别。

根据现实世界的性能分割循环可以提高性能，恶化性能或没有区别 - 它取决于操作系统，硬件和 - 当然 - 什么statement 1和statement 2是。

来源

2012-03-09 13:30:38

有了两个循环，你将支付：

增加生成码
2倍尽可能多的分支预测
取决于什么语句1和2的数据布局，你可以重新加载数据进入缓存。

最后一点可能在两个方向上产生巨大的影响。你应该测量任何性能优化。

来源

2012-03-09 13:31:23 Unknown1987

你的第三点可能是最重要的。这将决定你是否适合第一级CPU缓存。如果两者结合起来，所有的数据都适合缓存分裂将不会有所帮助，但如果缓存过大而分裂足够小，则收益可能会很大。 – 2012-03-09 13:39:51

如前所述，复杂性依然存在。

但在现实生活中，我们不可能预知哪个版本运行速度更快。以下是因素发挥作用，巨大的：

数据缓存
指令缓存
预测执行
分支预测
转移目标缓存对CPU
可用寄存器的数目
，缓存大小

（注意：在所有的人中，有达摩克利斯的预测错误之剑;全部都是可维护的和可搜索的）

尤其是最后一个因素使得它有时不可能编译其性能依赖于特定高速缓存大小的代码的一个真实代码。有些应用程序在CPU上运行速度较快，而在大型缓存上运行速度较慢，而在小型缓存上运行速度较慢，而对于其他一些应用程序则相反。

解决方案：

让你的编译器做循环改造的工作。现代g ++在这门学科中非常好。 g ++擅长的另一门学科是自动矢量化。请注意，编译器比几乎所有人都更了解计算机体系结构。
运送不同的二进制文件和调度程序。
使用cache-oblivious data structures/layouts and algorithms是适应目标缓存。

尝试适应目标的软件总是一个好主意，理想情况下不牺牲代码质量。在进行手动优化之前，无论是微观的还是宏观的，都要衡量真实世界的运行，然后才进行优化。

文学： * Agner Fog's Guides * Intel's Guides

来源

2012-03-16 16:49:21

性能分崩离析一个循环分为两个循环

回答

相关问题