倒数比倒数快吗？

小开

下面是一些硬件上可能发生的情况，这取决于编译器能够推断出您所使用的数字的范围: 使用递增循环，您必须在每次循环中测试 i<N。对于递减版本，进位标志(设置为减法的副作用)可以自动告诉您是否 i>=0。这样可以在循环中每次保存一个测试。

实际上，在现代流水线处理器硬件上，这种东西几乎肯定是无关紧要的，因为从指令到时钟周期没有简单的1-1映射。(虽然我可以想象，如果你正在做的事情，如生成精确定时的视频信号从微控制器。但不管怎样，你还是会用汇编语言写作。)

小开

不，不是这样的。有一种情况可能会更快，那就是在循环的每次迭代中调用函数来检查边界。

for(int i=myCollection.size(); i >= 0; i--)
{
...
}

但如果这样做不那么明显，那就不值得了。无论如何，在现代语言中，应该尽可能使用 foreach 循环。您特别提到了应该使用 foreach 循环的情况——当您不需要索引时。

小开

这种情况下，快点倒数:

for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}

因为 someObject.getAllObjects.size()在开始时执行一次。

当然，类似的行为可以通过在循环外调用 size()来实现，正如 Peter 提到的:

size = someObject.getAllObjects.size();
for (i = 0; i < size; i++) {…}

小开

无论方向如何，始终使用前缀格式(+ + i 而不是 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)

但是我希望现代编译器能够完全做到这些优化。

小开

是的！

从 N 到0的计数比从0到 N 的计数稍微快一些，这是硬件处理比较的方式。.

注意每个循环中的比较

i>=0
i<N

大多数处理器与零指令进行比较，所以第一个将被转换为机器代码:

上膛
如果小于或等于零，则比较和跳转

但是第二个每次都需要加载 N 个表单内存

装弹
加载 N
子 i 和子 N
如果小于或等于零，则比较和跳转

因此，这不是因为倒计时或向上。.而是因为您的代码将如何被翻译成机器码。.

所以从10数到100和从100数到10是一样的
但是在大多数情况下，从 i = 100到0的计数比从 i = 0到100的计数要快
从 i = N 到0的计数速度比从 i = 0到 N 的计数速度快

注意，现在的编译器可能会为您进行这种优化(如果它足够聪明的话)
还要注意的是，管道可能会导致类似贝拉迪异常点的效果(不能确定哪种效果会更好)
最后: 请注意您提供的2个 for 循环是不等价的。.第一印再印一张 * 。

相关阅读: 为什么 n + + 的执行速度比 n = n + 1快？

小开

在 Intel x86指令集中，构建一个从零开始倒计时的循环通常可以用比计数到非零退出条件的循环更少的指令来完成。具体来说，ECX 寄存器传统上用作 x86的环路计数器，Intel 指令集有一个特殊的 jcxz 跳转指令，该指令根据测试结果测试 ECX 寄存器的零和跳转。

然而，除非您的循环已经对时钟周期计数非常敏感，否则性能差异将是可以忽略不计的。与计数相比，倒数到零可能会在循环的每次迭代中减少4或5个时钟周期，所以与其说它是一种有用的技术，不如说它是一种新颖的技术。

而且，如今一个好的编译器最佳化应该能够把你的 count up 循环源代码转换成 count down 到0的机器码(取决于你如何使用 loop index 变量) ，所以真的没有任何理由用奇怪的方式写你的循环，只是为了在这里或那里挤出一两个循环。

小开

在一些较老的 CPU 上有/were 指令，如 DJNZ = = “如果不为零，则减少和跳转”。这允许有效的循环，其中您将初始计数值加载到寄存器中，然后您可以用一条指令有效地管理递减循环。我们在这里谈论的是20世纪80年代的 ISA ——如果你的老师认为这个“经验法则”仍然适用于现代 CPU，那么他就是严重脱节了。

小开

最佳答案

这是真的吗? 如果是真的，有人知道为什么吗？

在古代，当计算机还是用手工从熔融二氧化硅中取出芯片，当8位微控制器遍布地球，当你的老师年轻时(或者你老师的老师年轻时) ，有一种常见的指令称为 如果为零，则递减和跳过(DSZ)。Hotshot 汇编程序员使用此指令实现循环。后来的机器得到了更精致的指令，但是仍然有相当多的处理器，在这些处理器上比较零比较其他任何东西都要便宜。(即使在一些现代的 RISC 机器上也是如此，比如 PPC 或 SPARC，它们保留一个完整的寄存器总是为零。)

所以，如果你操纵你的循环来比较零而不是 N，会发生什么？

您可以保存一个注册表
您可能会得到一个使用较小二进制编码的比较指令
如果以前的指令碰巧设置了一个标志(可能只在 x86系列机器上) ，您甚至可能不需要显式的比较指令

这些差异是否可能导致 真正的程序上的 明显的进步在现代无序处理器上出现？不太可能。事实上，如果您能够在微基准测试中显示出可衡量的改进，我会印象深刻。

简介: 我打了你老师的头！你不应该学习关于如何组织循环的过时的伪事实。你应该学习的 关于循环，最重要的事情是确保它们 < em > end ，产生 < em > 正确答案，并且 < em > 易于阅读。我希望你的老师将重点放在重要的东西，而不是神话。

小开

倒计时比计时快吗？

也许吧。但是超过99% 的情况下，这并不重要，所以你应该使用最“合理”的测试来终止循环，我所说的合理，是指读者花最少的时间来弄清楚循环在做什么(包括什么使它停止)。使您的代码与代码正在执行的思维(或文档)模型相匹配。

如果循环是通过数组(或列表，或任何东西)向上运行的，一个递增计数器通常会更好地匹配读者对循环所做事情的想法——用这种方式编写循环代码。

但是，如果您正在使用一个包含 N项的容器，并且在使用时正在移除这些项，那么降低计数器的使用可能更有认知意义。

在回答“也许”这个问题时，我们需要更多的细节:

的确，在大多数体系结构中，对计算结果为零(或从零到负)的测试不需要显式的测试指令——结果可以直接检查。如果您想要测试某个计算是否导致其他数字，指令流通常必须有一个显式指令来测试该值。但是，特别是对于现代 CPU，这个测试通常会给循环结构增加少于噪声级别的额外时间。特别是当循环执行 I/O 时。

另一方面，如果你从零开始倒数，并使用计数器作为一个数组索引，例如，你可能会发现代码工作对系统的内存架构-内存读取通常会导致一个缓存“向前看”几个内存位置超过当前一个预期的顺序读取。如果您在内存中反向工作，那么缓存系统可能不会预期读取位于较低内存地址的内存位置。在这种情况下，循环“向后”可能会损害性能。然而，我仍然可能以这种方式编写循环代码(只要性能不成为问题) ，因为正确性是最重要的，并且使代码匹配模型是帮助确保正确性的一个很好的方法。不正确的代码是最不优化的。

因此，我倾向于忘记教授的建议(当然，不是在他的测试中——就课堂而言，你仍应该是务实的) ，除非代码的性能真的很重要。

小开

鲍勃,

直到您正在进行微优化时，您才会有手册可供您的 CPU 使用。此外，如果你正在做这样的事情，你可能无论如何都不需要问这个问题。但是，你的老师显然不同意这个观点... ..。

在你的循环例子中有4件事情需要考虑:

for (i=N;
i>=0;             //thing 1
i--)             //thing 2
{
putchar('*');   //thing 3
}

比较

比较(正如其他人所指出的)与特定的处理器建筑有关。比起运行 Windows 的处理器，有更多类型的处理器。特别是，可能有一条指令可以简化和加速与0的比较。

调整

在某些情况下，向上或向下调整更快。通常，很好编译器会找出它，并在可能的情况下重做循环。不过，并非所有的编译器都是好的。

环身

您正在使用 putchar 访问一个系统调用。太慢了。另外，您正在(间接地)在屏幕上呈现。那就更慢了。想想1000:1或更多的比例。在这种情况下，循环主体完全和完全超过了循环调整/比较的成本。

缓存

缓存和内存布局对性能有很大影响。在这种情况下，没关系。然而，如果您正在访问一个数组并且需要最佳性能，那么您就有必要研究一下编译器和处理器是如何设置内存访问的，并调优软件以最大限度地利用这一点。股票的例子就是一个与矩阵乘法有关的例子。

小开

从 C 到 psudo-Assembly:

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 程序集中没有比较。在许多体系结构中，有一些标志是通过算术运算(加、减、乘、除、增、减)设置的，可以用于跳转。这些函数通常会免费提供操作结果与0的比较。事实上，在许多建筑上

x = x - 0

在语义上和

compare x, 0

而且，与我的示例中的10进行比较可能会导致更糟糕的代码。10可能必须生活在一个寄存器中，所以如果他们是短缺的成本，并可能导致额外的代码来移动周围的东西或重新加载10每次通过循环。

编译器有时可以重新排列代码以利用这一点，但这通常很困难，因为它们通常无法确保通过循环逆转的方向在语义上是等价的。

小开

现在，我想你们已经听够了汇编课程:)我想给你们介绍一下自顶向下方法的另一个理由。

从高层做起的原因很简单。在循环体中，您可能意外地更改了边界，这可能导致不正确的行为，甚至导致循环没有终止。

看看这一小部分 Java 代码(因为这个原因，我猜语言并不重要) :

    System.out.println("top->down");
int n = 999;
for (int i = n; i >= 0; i--) {
n++;
System.out.println("i = " + i + "\t n = " + n);
}
System.out.println("bottom->up");
n = 1;
for (int i = 0; i < n; i++) {
n++;
System.out.println("i = " + i + "\t n = " + n);
}

所以我的观点是，你应该考虑自上而下，或者用一个常数作为边界。

小开

重点是，在倒计时时，你不需要分别检查 i >= 0和递减 i:

for (i = 5; i--;) {
alert(i);  // alert boxes showing 4, 3, 2, 1, 0
}

比较和递减 i都可以在一个表达式中完成。

关于为什么这个问题归结为较少的 x86指令，请参阅其他答案。

至于它是否会对您的应用程序产生有意义的影响，我想这取决于您有多少个循环以及它们的嵌套程度有多深。但对我来说，这样做也是可读的，所以我还是这么做了。

小开

这是一个有趣的问题，但作为一个实际问题，我并不认为它是重要的，也不会使一个循环比另一个循环更好。

根据这个维基百科页面: 闰秒，“ ... ... 太阳日每百年增长1.7毫米，主要是由于潮汐摩擦。”但是，如果你在数着日子过生日，你真的在乎这个时间上的细微差别吗？

更重要的是源代码易于阅读和理解。这两个循环很好地说明了可读性的重要性——它们的循环次数并不相同。

我敢打赌，大多数程序员阅读(i = 0; i < N; i + +)并立即理解这个循环 N 次。一个(i = 1; i < = N; i + +)的循环，对我来说，就不那么清晰了，而且对于(i = N; i > 0; i ——) ，我必须思考一会儿。如果代码的意图直接进入大脑而不需要任何思考，那是最好的。

小开

奇怪的是，看起来还是有区别的。至少在 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

如果有人知道原因，最好能知道:)

EDIT : 即使不从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.121999999999999734秒。如果内部循环是按照传统方式编写的，则执行时间为: 0.1719999999999998623秒。所以循环倒计时大约比 百分之三十快。

但是: 这个测试是在关闭所有 GCC 优化的情况下进行的。如果我们打开它们，编译器实际上比这种手工优化更聪明，甚至在整个循环期间将值保存在一个寄存器中，我们会得到一个类似

addi r2,r2,-1
bne r2,zero,0xa01c

在这个特殊的例子中，编译器甚至注意到，变量一在循环执行之后总是为1，并且会跳过所有的循环。

但是我经历过，有时候如果循环体足够复杂，编译器就不能进行这种优化，所以总是能够快速执行循环的最安全的方法是写:

register int i;
for(i=10000;i--;)
{ ... }

当然，这只能起作用，如果循环反向执行并不重要，就像 Betamoo 说的，除非倒计时为零。

小开

在汇编程序级别，倒数为零的循环通常比倒数到给定值的循环稍微快一些。如果计算结果等于零，大多数处理器将设置一个零标志。如果减去1使得计算环绕在过零点附近，这通常会改变进位标志(在一些处理器上，它会设置在其他处理器上，它会清除它) ，所以与0的比较基本上是免费的。

当迭代次数不是一个常数而是一个变量时，情况更是如此。

在简单的情况下，编译器可以自动优化循环的计数方向，但在更复杂的情况下，编译器可能知道循环的方向与整体行为无关，但编译器无法证明这一点。

小开

比你的计数器是增加还是减少更重要的是你是增加记忆还是减少记忆。大多数缓存都是针对上行内存而非下行内存进行优化的。由于内存访问时间是当今大多数程序面临的瓶颈，这意味着更改程序以提高内存 也许吧可以提高性能，即使这需要将计数器与非零值进行比较。在我的一些程序中，我发现通过改变我的代码使之增加内存而不是减少内存，性能得到了显著的提高。

怀疑? 只要写一个程序，让时间循环向上/向下记忆。下面是我得到的输出:

Average Up Memory   = 4839 mus
Average Down Memory = 5552 mus


Average Up Memory   = 18638 mus
Average Down Memory = 19053 mus

(其中“ mus”代表微秒)从运行这个程序:

#include <chrono>
#include <iostream>
#include <random>
#include <vector>
using namespace std;


//Sum all numbers going up memory.
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;
}


//Sum all numbers going down memory.
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;
}


//Time how long it takes to make num_repititions identical calls to sum_abs_down().
//We will divide this time by num_repitions to get the average time.
template<class T>
chrono::nanoseconds TimeDown(vector<T> &vec, const vector<T> &vec_original,
size_t num_repititions, T &running_sum) {
chrono::nanoseconds total{0};
for (size_t i = 0; i < num_repititions; i++) {
auto start_time = chrono::high_resolution_clock::now();
sum_abs_down(vec.begin(), vec.end(), running_sum);
total += chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}


template<class T>
chrono::nanoseconds TimeUp(vector<T> &vec, const vector<T> &vec_original,
size_t num_repititions, T &running_sum) {
chrono::nanoseconds total{0};
for (size_t i = 0; i < num_repititions; i++) {
auto start_time = chrono::high_resolution_clock::now();
sum_abs_up(vec.begin(), vec.end(), running_sum);
total += chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}


template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
random_device rnd_device;
mt19937 generator(rnd_device());
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) {
random_device rnd_device;
mt19937_64 generator(rnd_device());
uniform_real_distribution<double> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}


template<class ValueType>
void TimeFunctions(size_t num_repititions, size_t vec_size = (1u << 24)) {
auto lower = numeric_limits<ValueType>::min();
auto upper = numeric_limits<ValueType>::max();
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();
cout << "Average Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
cout << "Average Down Memory = " << time_down/(num_repititions * 1000) << " mus"
<< endl;
return ;
}


int main() {
size_t num_repititions = 1 << 10;
TimeFunctions<int>(num_repititions);
cout << '\n';
TimeFunctions<double>(num_repititions);
return 0;
}

sum_abs_up和 sum_abs_down做同样的事情(对数字向量求和) ，并且计时方式相同，唯一的区别是 sum_abs_up上升内存而 sum_abs_down下降内存。我甚至通过引用传递 vec，以便两个函数访问相同的内存位置。尽管如此，sum_abs_up始终比 sum_abs_down快。自己运行一下(我用 g + +-O3编译的)。

重要的是要注意我的计时循环是多么紧密。如果一个循环体很大(有很多代码) ，那么它的迭代器是向上还是向下内存并不重要，因为执行循环体所花费的时间可能会完全占据主导地位。另外，值得一提的是，对于一些罕见的循环，内存下降的速度比内存上升的速度快。但是，即使有这样的循环，也从来没有这样的情况，上升内存慢于下降 一直都是(不像小型循环上升内存，这通常是相反的情况; 事实上，对于少数几个循环，我已经计时，通过上升内存的性能增加了40% 以上)。

重点是，根据经验，如果你可以选择，如果循环体很小，如果让循环向上而不是向下进入内存之间没有什么区别，那么你就应该向上进入内存。

FYI vec_original是为了实验而存在的，它使得改变 sum_abs_up和 sum_abs_down变得容易，使得它们改变 vec，同时不允许这些改变影响未来的计时。我强烈推荐使用 sum_abs_up和 sum_abs_down并计算结果。

小开

你的老师所说的只是一些没有经过多少澄清的间接陈述。这并不是说递减比递增快，而是你可以用递减创建比递增快得多的循环。

不需要长篇大论，不需要使用循环计数器等等——下面重要的只是速度和循环计数(非零)。

下面是大多数人如何实现10次迭代的循环:

int i;
for (i = 0; i < 10; i++)
{
//something here
}

对于99% 的情况下，这是一个人可能需要的全部，但随着 PHP，PYTHON，JavaScript 有整个世界的时间关键软件(通常嵌入式，操作系统，游戏等) ，CPU 的滴答声真的很重要，所以简要看看汇编代码:

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个分支。是的，是的，我知道它可以做得更好(这只是一个例子)。

现在考虑一下这个经常被嵌入式开发人员编写的结构:

i = 10;
do
{
//something here
} while (--i);

它还迭代10次(是的，我知道 i 值与显示的 for 循环不同，但我们在这里关心迭代次数)。这可归纳为:

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兼容的)具有指令，这些指令可以减去寄存器，然后将 result 与 zero 进行比较，并在 result 与 zero 不同时执行分支。实际上所有的 PC CPU 都实现了这个指令。使用它，循环实际上只是一个(是的)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 没有实现上面的指令，它所需要的模拟操作也是一个递减操作，如果前面的指令的结果刚好为零，那么它就是一个条件跳转操作。

所以不管有些情况下，你可能会指出为什么我错了等等，我强调-是的，这是有益的循环，如果你知道如何，为什么和什么时候。

附言。是的，我知道明智的编译器(与适当的优化水平)将重写循环(与升循环计数器)做。.而等价于常量循环迭代... (或展开它) ..。