loops - 更深入地了解循环(for、while、do while、foreach、递归等)

标签 loops performance memory-management

如果给出一些情况,你可以对需要使用循环解决的某个事件或函数进行循环,你可以通过任何类型的循环来实现这些。我们如何根据速度、效率和内存使用情况来确定可以使用的每个循环之间的差异?例如,你有这些循环

for(int i=0;i<10;i++) {
    array[i] = i+1;
}

int i = 0;
while(i<10) {
    array[i] = i+1;
    i++;
}

上面的例子有相同的输出,当然你在执行时看不出它们之间的区别,因为这只是一个小过程,如果你正在处理一个消耗内存的巨大循环怎么办?哪个循环更好用?何时使用什么循环是否有适当的措施?

编辑:

对于 pakore 的回答,

根据您的回答,我可以肯定地说,如果我重新排序我的变量,其中大多数相关变量彼此远离(中间有其他行)可能会更有效率。比如说,

a=0;
b=1;
c=5;
d=1;
for(int i=0; i<10;i++)
{
    a=b*CalculateAge()+d;
    m=c+GetAvarage(a);
    d++;
}

a=0;
b=1;
c=5;
d=1;
for(int i=0; i<10;i++)
{
    a=b*CalculateAge()+d;
    d++;
    m=c+GetAvarage(a);
}

后者比第一个更有效,因为在后来我在第一行调用了一个外部方法,第二行独立于第一行的结果而不是第三行。

由于第一个示例在执行第二行和第三行之前会等待第一行的结果,而第二个示例在等待第一行的结果时已经执行了第二行。

结论:

优化的循环与您使用的循环类型无关。正如 pakore 和 polygenelubricants 所解释的那样,您在循环中可以考虑的主要事情是您的代码在其中的编写方式。优化代码是编译器的工作,如果您根据代码与每个变量的依赖关系优化代码也会有所帮助,正如 pakore 在下面解释的那样。

最佳答案

好吧,这里很难解释循环背后的所有逻辑。

为了优化循环,编译器会为你做一些令人惊奇的事情,所以你使用 while 并不重要。或 for因为无论如何编译器都会转换为汇编程序。

为了有更深入的理解,您应该学习一些汇编程序,然后学习基本处理器的工作原理、它如何读取指令以及如何处理指令。

为了改进流水线,最好将具有相同变量的语句彼此分开放置。这样,在计算一个语句时,如果下一个语句独立于第一个语句,则处理器可以获取下一个语句并开始计算它。

例如:

a=0;
b=3;
c=5;
m=8;
i=0;
while(i<10){
a=a+b*c;
b=b*10+a;
m=m*5;
i++;
}

我们在 a 之间有依赖关系和 b并且语句彼此相邻。但是我们看到mi独立于其余部分,因此我们可以:

a=0;
b=3;
c=5;
m=8;
i=0;
while(i<10){
a=a+b*c;
m=m*5;
i++;
b=b*10+a;

}

所以 a正在计算,我们可以开始计算mi .大多数时候,编译器会检测到这一点并自动执行(它是 calle 代码重新排序)。有时对于小循环,编译器会根据需要多次复制并粘贴循环中的代码,因为没有控制变量会更快。

我的建议是让编译器去关心这些事情并关注你正在使用的算法的成本,最好从O(n!)减少到O( logn) 而不是在循环内进行微优化。

根据修改后的问题更新

嗯,依赖关系必须是写/写或读/写依赖关系。如果它是读/读依赖就没有问题(因为值不会改变)。查看 [数据依赖性文章] ( http://en.wikipedia.org/wiki/Data_dependency )。

<罢工> 在您的示例中,两个代码之间没有区别,m取决于 cb但是这两个从未被写入,所以编译器在进入循环之前就知道它们的值。这称为读取/读取依赖项,它本身不是依赖项。

如果你写过:

...
m=c+GetAvarage(a);
...

然后我们会有一个写/读依赖(我们必须写入 a 然后从 a 读取,所以我们必须等到 a 被计算)和你做的优化会很好。

但是再一次,编译器会为您和许多其他事情做这件事。很难说高级代码中的微优化会对汇编代码产生真正的影响,因为编译器可能已经为你做了这些,或者正在为你重新排序代码,或者正在做一个数以千计的其他事物比我们乍一看所能想到的要好。

但不管怎样,了解事情在地毯下的运作方式是件好事 :)

更新以添加一些链接 查看这些链接以进一步了解编译器可以做什么来提高代码性能:

Loop unwinding

Dependency Analysis

Automatic parallelization

Vectorization

关于loops - 更深入地了解循环(for、while、do while、foreach、递归等),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3421836/

相关文章:

r - 在循环中收集未知数量的结果

python - 为什么在我的例子中 For 循环比 Map、Reduce 和 List 理解更快

c# - 通过 Equals 或 HashCode 进行比较。哪个更快?

cocoa - 你曾经使用过 NSZoneMalloc() 而不是 malloc() 吗?

c - 需要动态分配(初始化)的静态变量

mysql - 带循环的动态添加列

loops - 通过引用捕获循环中的闭包?

java - 在提高 Java 性能时我应该寻找什么?

c - 如何找出 valgrind 报告中出现 "Invalid Free()"错误的原因

c - 对字符串的每个数字进行排序