倒数比倒数快吗？
我们的计算机科学老师曾经说过，由于某种原因，倒计数比计数更有效率。 例如，如果你需要使用一个FOR循环，并且循环索引没有被用到某处（比如在屏幕上打印一行N *），我的意思是这样的代码：
for (i = N; i >= 0; i--) putchar('*'); 胜于：
for (i = 0; i < N; i++) putchar('*');
这是真的吗？ 如果是这样，有谁知道为什么？
这是真的吗？ 如果是的话，有谁知道为什么？
在古代，当计算机仍然用手工切割熔融石英时，当8位微控制器漫游地球时，当你的老师还年轻（或者你的老师的老师还年轻）时，有一个通用的机器指令称为递减和跳过如果为零 （DSZ）。 Hotshot程序员使用这个指令来实现循环。 后来的机器得到了更好的指示，但是仍然有相当多的处理器比较便宜，比较零与其他任何东西比较。 （即使在一些现代的RISC机器上，如PPC或SPARC也是如此，它们保留了整个寄存器始终为零）。
所以，如果你用循环来比较零而不是N ，会发生什么？
- 你可以保存一个registry
- 你可能会得到一个较小的二进制编码的比较指令
- 如果前面的指令碰巧设置了一个标志（可能只在x86系列机器上），那么甚至可能不需要明确的比较指令
这些差异是否会导致现代无序处理器上的实际程序有任何可衡量的改进 ？ 不大可能。 事实上，即使在微基准testing中，如果您能够显示出可衡量的改进，我也会留下深刻的印象。
总结： 我把你的老师打在头上！ 你不应该学习关于如何组织循环的过时伪事实。 你应该知道关于循环的最重要的事情是确保它们终止 ，产生正确的答案 ，并且易于阅读 。 我希望你的老师将重点放在重要的东西，而不是神话。
以下是某些硬件上可能发生的情况，具体取决于编译器可以推导出您使用的数字的范围：使用递增循环，您必须每次循环testingi<N 。 对于递减版本，进位标志（设置为减法的副作用）可以自动告诉你是否i>=0 。 这样可以节省每个循环的testing时间。
实际上，在现代stream水线处理器硬件上，这个东西几乎肯定是不相关的，因为从指令到时钟周期都没有简单的1-1映射。 （虽然我可以想象如果您正在从微控制器生成精确定时的video信号，但是您仍然可以使用汇编语言编写。）
在Intel x86指令集中，构build一个循环来倒计数到零通常可以用比指令到非零退出条件的循环更less的指令来完成。 具体来说，ECX寄存器传统上用作x86 asm中的循环计数器，而Intel指令集有一个特殊的jcxz跳转指令，根据testing结果testingECX寄存器为零和跳转。
但是，除非您的环路对时钟周期计数非常敏感，否则性能差异可以忽略不计。 计数到零可能会减less循环的每个迭代4或5个时钟周期，而不是一个有用的技术。
此外，一个好的优化编译器这些天应该能够转换你的计数循环源代码计数到零机器代码（取决于你如何使用循环索引variables），所以真的没有任何理由编写你的循环在奇怪的方法只是挤在一个或两个周期在这里和那里。
是..！！
从N到0的计数比从0到N的计数略快一些，硬件如何处理比较。
注意每个循环中的比较
i>=0 i<N
大多数处理器与零指令比较，所以第一个将被转换为机器码为：
- 加载我
- 如果小于或等于零，则进行比较和跳转
但第二个需要每次加载N格式的内存
- 加载我
- 加载N
- Sub i和N
- 如果小于或等于零，则进行比较和跳转
所以这不是因为倒计时或者倒计时。但是由于你的代码将被转换成机器代码。
因此，从10到100的计数与从100到10的计数相同
但是在大多数情况下，从i = 100到0的计数比从i = 0到100的计数要快
从i = N到0的计数比从i = 0到N快
- 请注意，现在的编译器可能会为你做这个优化（如果它足够聪明的话）
- 还要注意，pipe道会造成Belady的exception状效果（不知道会有什么更好的）
- 最后：请注意，你提出的2个循环是不相等的..第一次打印一个* ….
相关： 为什么n ++执行速度比n = n + 1快？
在C到psudo程序集：
for (i = 0; i < 10; i++) { foo(i); }
变成
clear i top_of_loop: call foo increment i compare 10, i jump_less top_of_loop
而：
for (i = 10; i >= 0; i--) { foo(i); }
变成
load i, 10 top_of_loop: call foo decrement i jump_not_neg top_of_loop
注意在第二个psudo程序集中缺less比较。 在许多体系结构中，都有通过算术运算（加，减，乘，除，增，减）设置的标志，可用于跳转。 这些通常给你什么基本上是免费的操作结果与0的比较。 事实上在许多架构上
x = x - 0
在语义上是相同的
compare x, 0
另外，在我的例子中比较10可能会导致更糟糕的代码。 10可能必须住在寄存器中，所以如果它们的供应短缺，并且可能导致额外的代码来移动或者每次都重新加载循环。
编译器有时可以重新安排代码来利用这个优势，但是这往往是困难的，因为它们通常不能确定在循环中颠倒方向在语义上是等价的。
在这样的情况下更快地倒数：
for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}
因为someObject.getAllObjects.size()在开头执行一次。
当然，类似的行为可以通过调用size()来实现，正如Peter所说：
size = someObject.getAllObjects.size(); for (i = 0; i < size; i++) {…}
倒数比倒数快吗？
也许。 但是，99％以上的时间无关紧要，所以你应该用最明智的testing来终止循环，而且我的意思是读者最less花费的思考循环在做什么（包括什么使其停止）。 让你的代码与代码所做的精神（或logging）模型相匹配。
如果循环正在工作，通过一个数组（或列表，或其他），一个递增的计数器通常会更好地与读者如何考虑循环在做什么相匹配 – 用这种方式编写循环。
但是，如果你正在通过一个有N物品的容器，并且随时去除这些物品，那么让这个计数器工作起来可能更有意义。
在答案中的'也许'更详细一点：
确实，在大多数体系结构中，testing结果为零（或从零到负）的testing不需要明确的testing指令 – 可以直接检查结果。 如果你想testing一个计算结果是否是其他数字，那么指令stream通常必须有明确的指令来testing这个值。 但是，特别是对于现代CPU，这个testing通常会增加一个循环构造的噪声级附加时间。 特别是如果该循环正在执行I / O。
另一方面，如果从零开始倒数计数，并将计数器用作数组索引，则可能会发现代码与系统的内存架构相互作用 – 内存读取通常会导致caching“向前看”预期连续读取的数个存储位置超过当前存储位置。 如果通过内存向后工作，caching系统可能不会预期在较低的内存地址读取内存位置。 在这种情况下，循环“倒退”可能会损害性能。 然而，我仍然可能以这种方式编写循环（只要性能不成问题），因为正确性是至关重要的，并且使代码匹配模型是帮助确保正确性的好方法。 不正确的代码像你所能得到的那样未被优化。
所以我会倾向于忘记教授的build议（当然，不是在他的testing中 – 在课堂上，你应该仍然是务实的），除非和直到代码的performance真正重要。
在一些较旧的CPU上有/像DJNZ ==“递减和跳转，如果不是零”的指令。 这允许在初始计数值加载到寄存器的情况下实现高效循环，然后使用一条指令可以有效地pipe理递减循环。 我们在这里讨论的是1980年代的ISA，如果他认为这个“经验法则”仍然适用于现代的CPU，那么你的老师是非常失去联系的。
鲍勃，
直到你正在进行微型优化，在这一点上你将得到你的CPU手册。 而且，如果你正在做这样的事情，那么你可能不需要问这个问题。 :-)但是，你的老师显然不赞成这个想法….
在你的循环例子中有四件事情需要考虑：
for (i=N; i>=0; //thing 1 i--) //thing 2 { putchar('*'); //thing 3 }
- 对照
比较（正如其他人所指出的）与特定处理器架构相关。 处理器的种类比运行Windows的处理器的种类多。 特别是，可能有一个简化和加快与0进行比较的指令。
- 调整
在某些情况下，调高或调低速度会更快。 通常情况下，一个好的编译器会把它弄清楚，如果可以的话，重做循环。 不是所有的编译器都是好的。
- 循环体
您正在使用putchar访问系统调用。 这是非常缓慢的。 另外，你正在渲染到屏幕上（间接）。 这甚至更慢。 认为1000：1的比例或更多。 在这种情况下，环路体完全超过了环路调整/比较的成本。
- 高速caching
caching和内存布局可能会对性能产生很大的影响。 在这种情况下，没关系。 但是，如果你正在访问一个数组并且需要最佳的性能，那么你应该调查你的编译器和你的处理器如何布置内存访问，并调整你的软件以充分利用它。 股票的例子是关于matrix乘法给出的例子。
这是一个有趣的问题，但作为一个实际问题，我不认为这是重要的，不会使一个循环比另一个更好。
根据这个维基百科页面： 闰秒 ，“…太阳日每百年由于潮汐摩擦而变得更长1.7毫秒”。 但是，如果你计算的日子，直到你的生日，你真的关心这个微小的时间差异？
源代码易于阅读和理解更为重要。 这两个循环是一个很好的例子，为什么可读性是重要的 – 他们不循环相同的次数。
我敢打赌，大多数程序员阅读（我= 0;我<N;我++），并立即明白，这个循环N次。 对于我来说，（i = 1; i <= N; i ++）的循环有点不太清楚，而且（i = N; i> 0; i–）我必须考虑一下。 最好是代码的意图直接进入大脑，而不需要任何思考。
奇怪的是，这似乎是有区别的。 至less在PHP中。 考虑以下基准：
<?php print "<br>".PHP_VERSION; $iter = 100000000; $i=$t1=$t2=0; $t1 = microtime(true); for($i=0;$i<$iter;$i++){} $t2 = microtime(true); print '<br>$i++ : '.($t2-$t1); $t1 = microtime(true); for($i=$iter;$i>0;$i--){} $t2 = microtime(true); print '<br>$i-- : '.($t2-$t1); $t1 = microtime(true); for($i=0;$i<$iter;++$i){} $t2 = microtime(true); print '<br>++$i : '.($t2-$t1); $t1 = microtime(true); for($i=$iter;$i>0;--$i){} $t2 = microtime(true); print '<br>--$i : '.($t2-$t1);
结果很有意思：
PHP 5.2.13 $i++ : 8.8842368125916 $i-- : 8.1797409057617 ++$i : 8.0271911621094 --$i : 7.1027431488037 PHP 5.3.1 $i++ : 8.9625310897827 $i-- : 8.5790238380432 ++$i : 5.9647901058197 --$i : 5.4021768569946
如果有人知道为什么，这将是很高兴知道:)
编辑 ：结果是相同的，即使你不是从0开始计算，而是其他任意值。 那么可能不仅仅是比较零才会有所作为？
它可以更快。
在我目前正在使用的NIOS II处理器上，传统的for循环
for(i=0;i<100;i++)
产生组件：
ldw r2,-3340(fp) %load i to r2 addi r2,r2,1 %increase i by 1 stw r2,-3340(fp) %save value of i ldw r2,-3340(fp) %load value again (???) cmplti r2,r2,100 %compare if less than equal 100 bne r2,zero,0xa018 %jump
如果我们倒数
for(i=100;i--;)
我们得到一个需要2个指令的程序集。
ldw r2,-3340(fp) addi r3,r2,-1 stw r3,-3340(fp) bne r2,zero,0xa01c
如果我们有嵌套循环，内部循环执行很多，我们可以有一个可衡量的差异：
int i,j,a=0; for(i=100;i--;){ for(j=10000;j--;){ a = j+1; } }
如果内部循环如上所述，则执行时间为：0.12199999999999999734秒。 如果内部循环是用传统方式写的，则执行时间为：0.17199999999999998623秒。 所以循环倒计时大约快30％ 。
但是：这个testing是在所有GCC优化closures的情况下进行的。 如果我们把它们打开，编译器实际上比这个手工优化更聪明，甚至在整个循环期间保持在寄存器中的值，我们会得到一个像
addi r2,r2,-1 bne r2,zero,0xa01c
在这个特定的例子中，编译器甚至注意到，循环执行后variablesa将总是1，并且一起跳过循环。
不过，如果循环体足够复杂，编译器无法进行这种优化，所以有时会遇到这种情况，所以总是得到快速循环执行的最安全方法是编写：
register int i; for(i=10000;i--;) { ... }
当然这只有在循环执行顺序无关紧要时才有效，就像Betamoo所说的那样， 只有当你倒数到零时。
不，这不是真的。 有一种情况可能会更快，那就是当你在循环的每一次迭代中调用一个函数来检查边界时。
for(int i=myCollection.size(); i >= 0; i--) { ... }
但是如果这样做不那么清楚，那就不值得。 在现代语言中，无论如何，您应该尽可能使用foreach循环。 你特别提到你应该使用foreach循环的情况 – 当你不需要索引时。
不pipe方向总是使用前缀forms（++我而不是i ++）！
for (i=N; i>=0; --i)
要么
for (i=0; i<N; ++i)
解释： http : //www.eskimo.com/~scs/cclass/notes/sx7b.html
此外，你可以写
for (i=N; i; --i)
但我希望现代编译器能够完成这些优化。
重点是，倒计时你不需要单独检查i >= 0来减lessi 。 注意：
for (i = 5; i--;) { alert(i); // alert boxes showing 4, 3, 2, 1, 0 }
比较和递减i都可以在一个expression式中完成。
查看其他答案为什么这可以归结为更less的x86指令。
至于它是否会在你的应用程序中产生有意义的变化，那么我想这取决于你有多less个循环，以及它们的嵌套程度。 但对我来说，这样做是可读的，所以我无论如何做。
你的老师所说的是一些没有太多澄清的歪曲的陈述。 这并不是递减比递增更快，但是你可以创build比递增更快的循环。
没有必要详细介绍它，而不需要使用循环计数器等 – 以下重要的是速度和循环计数（非零）。
以下是大多数人如何实现循环10次迭代：
int i; for (i = 0; i < 10; i++) { //something here }
对于99％的情况是所有可能需要的，但是随着PHP，PYTHON，JavaScript，CPU蜱真正重要的时间关键软件（通常是embedded式，操作系统，游戏等）的全世界所以简要看一下汇编代码：
int i; for (i = 0; i < 10; i++) { //something here }
编译后（没有优化）编译版本可能看起来像这样（VS2015）：
-------- C7 45 B0 00 00 00 00 mov dword ptr [i],0 -------- EB 09 jmp labelB labelA 8B 45 B0 mov eax,dword ptr [i] -------- 83 C0 01 add eax,1 -------- 89 45 B0 mov dword ptr [i],eax labelB 83 7D B0 0A cmp dword ptr [i],0Ah -------- 7D 02 jge out1 -------- EB EF jmp labelA out1:
整个循环是8条指令（26字节）。 其中 – 实际上有6条指令（17字节）和2个分支。 是的，我知道这可以做得更好（只是一个例子）。
现在考虑一下您经常会发现的由embedded式开发人员编写的常用构造：
i = 10; do { //something here } while (--i);
它也迭代10次（是的，我知道我的价值是不同于循环显示，但我们关心迭代计数在这里）。 这可以编译成这样的：
00074EBC C7 45 B0 01 00 00 00 mov dword ptr [i],1 00074EC3 8B 45 B0 mov eax,dword ptr [i] 00074EC6 83 E8 01 sub eax,1 00074EC9 89 45 B0 mov dword ptr [i],eax 00074ECC 75 F5 jne main+0C3h (074EC3h)
5条指令（18个字节），只有一个分支。 实际上循环中有4条指令（11个字节）。
最好的情况是，一些CPU（包括x86 / x64兼容）具有可能递减寄存器的指令，稍后将结果与零进行比较，如果结果不为零，则执行分支。 几乎所有的PC cpus都执行这个指令。 使用它循环实际上只是一个（是的）2字节指令：
00144ECE B9 0A 00 00 00 mov ecx,0Ah label: // something here 00144ED3 E2 FE loop label (0144ED3h) // decrement ecx and jump to label if not zero
我必须解释哪一个更快？
现在，即使特定的CPU没有执行上述指令，只要前一个指令的结果为0，就要求模拟它是一个递减，然后是条件跳转。
所以不pipe你可能会指出为什么我错了等等的一些情况下，我强调 – 是的，如果你知道如何，为什么以及何时知道如何向下循环。
PS。 是的，我知道明智的编译器（具有适当的优化级别）将重写为循环（与递增循环计数器）做do..while等效于恒定循环迭代…（或展开它）…
不pipe你是增加还是减less你的柜台，关键在于你是在记忆还是在记忆中。 大多数高速caching都针对内存而不是内存的优化进行了优化。 由于内存访问时间是当今大多数程序所面临的瓶颈，这意味着即使需要将计数器与非零值进行比较，更改程序以使内存上升也可以提高性能。 在我的一些程序中，通过改变我的代码来增加内存而不是停下来，我看到了性能的显着提高。
持怀疑态度？ 这是我得到的输出：
Ave. Up Memory = 4839 mus Ave. Down Memory = 5552 mus Ave. Up Memory = 18638 mus Ave. Down Memory = 19053 mus
从运行这个程序：
#include <chrono> #include <iostream> #include <random> #include <vector> template<class Iterator, typename T> void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) { std::random_device rnd_device; std::mt19937 generator(rnd_device()); std::uniform_int_distribution<T> dist(a, b); for (auto it = start; it != one_past_end; it++) *it = dist(generator); return ; } template<class Iterator> void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) { std::random_device rnd_device; std::mt19937_64 generator(rnd_device()); std::uniform_real_distribution<double> dist(a, b); for (auto it = start; it != one_past_end; it++) *it = dist(generator); return ; } template<class Iterator, class T> inline void sum_abs_up(Iterator first, Iterator one_past_last, T &total) { T sum = 0; auto it = first; do { sum += *it; it++; } while (it != one_past_last); total += sum; } template<class Iterator, class T> inline void sum_abs_down(Iterator first, Iterator one_past_last, T &total) { T sum = 0; auto it = one_past_last; do { it--; sum += *it; } while (it != first); total += sum; } template<class T> std::chrono::nanoseconds TimeDown(std::vector<T> &vec, const std::vector<T> &vec_original, std::size_t num_repititions, T &running_sum) { std::chrono::nanoseconds total{0}; for (std::size_t i = 0; i < num_repititions; i++) { auto start_time = std::chrono::high_resolution_clock::now(); sum_abs_down(vec.begin(), vec.end(), running_sum); total += std::chrono::high_resolution_clock::now() - start_time; vec = vec_original; } return total; } template<class T> std::chrono::nanoseconds TimeUp(std::vector<T> &vec, const std::vector<T> &vec_original, std::size_t num_repititions, T &running_sum) { std::chrono::nanoseconds total{0}; for (std::size_t i = 0; i < num_repititions; i++) { auto start_time = std::chrono::high_resolution_clock::now(); sum_abs_up(vec.begin(), vec.end(), running_sum); total += std::chrono::high_resolution_clock::now() - start_time; vec = vec_original; } return total; } template<class ValueType> void TimeFunctions(std::size_t num_repititions, std::size_t vec_size = (1u << 24)) { auto lower = std::numeric_limits<ValueType>::min(); auto upper = std::numeric_limits<ValueType>::max(); std::vector<ValueType> vec(vec_size); FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper); const auto vec_original = vec; ValueType sum_up = 0, sum_down = 0; auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count(); auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count(); std::cout << "Ave. Up Memory = " << time_up/(num_repititions * 1000) << " mus\n"; std::cout << "Ave. Down Memory = " << time_down/(num_repititions * 1000) << " mus" << std::endl; return ; } int main() { std::size_t num_repititions = 1 << 10; TimeFunctions<int>(num_repititions); std::cout << '\n'; TimeFunctions<double>(num_repititions); return 0; }
Both sum_abs_up and sum_abs_down do the same thing and are timed they same way with the only difference being that sum_abs_up goes up memory while sum_abs_down goes down memory. I even pass vec by reference so that both functions access the same memory locations. Nevertheless, sum_abs_up is consistently faster than sum_abs_down . Give it a run yourself (I compiled it with g++ -O3).
FYI vec_original is there for experimentation, to make it easy for me to change sum_abs_up and sum_abs_down in a way that makes them alter vec while not allowing these changes to affect future timings.
It's important to note how tight the loop that I'm timing is. If a loop's body is large then it likely won't matter whether its iterator goes up or down memory since the time it takes to execute the loop's body will likely completely dominate. Also, it's important to mention that with some rare loops, going down memory is sometimes faster than going up it. But even with such loops it's rarely ever the case that going up was always slower than going down (unlike small-bodied loops that go up memory, for which the opposite is frequently true; in fact, for a small handful of loops I've timed, the increase in performance by going up memory was 40+%).
The point is, as a rule of thumb, if you have the option, if the loop's body is small, and if there's little difference between having your loop go up memory instead of down it, then you should go up memory.
Now, I think you had enough assembly lectures:) I would like to present you another reason for top->down approach.
The reason to go from the top is very simple. In the body of the loop, you might accidentally change the boundary, which might end in incorrect behaviour or even non-terminating loop.
Look at this small portion of Java code (the language does not matter I guess for this reason):
System.out.println("top->down"); int n = 999; for (int i = n; i >= 0; i--) { n++; System.out.println("i = " + i + "\tn = " + n); } System.out.println("bottom->up"); n = 1; for (int i = 0; i < n; i++) { n++; System.out.println("i = " + i + "\tn = " + n); }
So my point is you should consider prefering going from the top down or having a constant as a boundary.
At an assembler level a loop that counts down to zero is generally slightly faster than one that counts up to a given value. If the result of a calculation is equal to zero most processors will set a zero flag. If subtracting one makes a calculation wrap around past zero this will normally change the carry flag (on some processors it will set it on others it will clear it), so the comparison with zero comes essentially for free.
This is even more true when the number of iterations is not a constant but a variable.
In trivial cases the compiler may be able to optimise the count direction of a loop automatically but in more complex cases it may be that the programmer knows that the direction of the loop is irrelevant to the overall behaviour but the compiler cannot prove that.
