C++ 在 for 循环中倒计时

Counting down in for-loops

提问by ohit

I believe (from some research reading) that counting down in for-loops is actually more efficient and faster in runtime. My full software code is C++

我相信（从一些研究阅读中）在 for 循环中倒计时实际上在运行时更有效、更快。我的完整软件代码是 C++

I currently have this:

我目前有这个：

for (i=0; i<domain; ++i) {

my 'i' is unsigned resgister int, also 'domain' is unsigned int

我的 'i' 是 unsigned resgister int，'domain' 也是 unsigned int

in the for-loop i is used for going through an array, e.g.

在 for 循环中 i 用于遍历数组，例如

array[i] = do stuff

converting this to count down messes up the expected/correct output of my routine.

将此转换为倒计时会弄乱我的例程的预期/正确输出。

I can imagine the answer being quite trivial, but I can't get my head round it.

我可以想象这个答案很简单，但我无法理解。

UPDATE: 'do stuff' does not depend on previous or later iteration. The calculations within the for-loop are independant for that iteration of i. (I hope that makes sense).

更新：“做事”不依赖于之前或之后的迭代。对于 i 的迭代，for 循环中的计算是独立的。（我希望这是有道理的）。

UPDATE: To achieve a runtime speedup with my for-loop, do I count down and if so remove the unsigned part when delcaring my int, or what other method?

更新：为了通过我的 for 循环实现运行时加速，我是否倒计时，如果是这样，在声明我的 int 时删除无符号部分，或者其他什么方法？

Please help.

请帮忙。

回答by Don Neufeld

There is only one correct method of looping backwards using an unsigned counter:

只有一种使用无符号计数器向后循环的正确方法：

for( i = n; i-- > 0; )
{
    // Use i as normal here
}

There's a trick here, for the last loop iteration you will have i = 1 at the top of the loop, i-- > 0 passes because 1 > 0, then i = 0 in the loop body. On the next iteration i-- > 0 fails because i == 0, so it doesn't matter that the postfix decrement rolled over the counter.

这里有一个技巧，对于最后一次循环迭代，您将在循环顶部有 i = 1，i--> 0 通过，因为 1 > 0，然后在循环体中 i = 0。在下一次迭代中 i--> 0 失败，因为 i == 0，所以后缀递减量在计数器上滚动并不重要。

Very non obvious I know.

我知道非常不明显。

回答by Jeremy Ruten

I'm guessing your backward for loop looks like this:

我猜你的向后 for 循环看起来像这样：

for (i = domain - 1; i >= 0; --i) {

In that case, because iis unsigned, it will alwaysbe greater than or equal to zero. When you decrement an unsigned variable that is equal to zero, it will wrap around to a very large number. The solution is either to make isigned, or change the condition in the for loop like this:

在这种情况下，因为i是unsigned，它总是大于或等于零。当您递减一个等于 0 的无符号变量时，它会回绕到一个非常大的数字。解决方案是进行i签名，或者像这样更改 for 循环中的条件：

for (i = domain - 1; i >= 0 && i < domain; --i) {

Or count from domainto 1rather than from domain - 1to 0:

或者从domain到1而不是从domain - 1到0：

for (i = domain; i >= 1; --i) {
    array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}

回答by Hejazzman

This is not an answer to your problem, because you don't seem to have a problem.

这不是您问题的答案，因为您似乎没有问题。

This kind of optimization is completely irrelevant and should be left to the compiler (if done at all).

这种优化完全无关，应该留给编译器（如果有的话）。

Have you profiled your program to check that your for-loop is a bottleneck? If not, then you do not need to spend time worrying about this. Even more so, having "i" as a "register" int, as you write, makes no real sense from a performance standpoint.

您是否分析了您的程序以检查您的 for 循环是否是瓶颈？如果没有，那么您无需花时间担心这一点。更重要的是，从性能的角度来看，在您编写时将“i”作为“寄存器”int 没有任何实际意义。

Even without knowing your problem domain, I can guarantee you that both the reverse-looping technique and the "register" int counter will have negligibleimpact on your program's performance. Remember, "Premature optimization is the root of all evil".

即使不知道您的问题域，我也可以向您保证，反向循环技术和“寄存器”int 计数器对您的程序性能的影响可以忽略不计。请记住，“过早的优化是万恶之源”。

That said, better spent optimization time would be on thinking about the overall program structure, data structures and algorithms used, resource utilization, etc.

也就是说，将优化时间花在考虑整体程序结构、使用的数据结构和算法、资源利用率等上。

回答by Michael

Checking to see if a number is zero can be quicker or more efficient than a comparison. But this is the sort of micro-optimization you really shouldn't worry about - a few clock cycles will be greatly dwarfed by just about any other perf issue.

检查数字是否为零比比较更快或更有效。但这是您真正不应该担心的那种微优化 - 几乎任何其他性能问题都会使几个时钟周期大大相形见绌。

On x86:

在 x86 上：

dec eax
jnz Foo

Instead of:

代替：

inc eax
cmp eax, 15
jl Foo

回答by Rob Kennedy

It has nothing to do with counting upor down. What can be faster is counting toward zero. Michael's answershows why — x86 gives you a comparison with zero as an implicit side effect of many instructions, so after you adjust your counter, you just branch based on the result instead of doing an explicit comparison. (Maybe other architectures do that, too; I don't know.)

它与向上或向下计数无关。可以更快的是向零计数。Michael 的回答说明了原因——x86 为您提供了与零的比较作为许多指令的隐含副作用，因此在您调整计数器后，您只需根据结果进行分支，而不是进行显式比较。（也许其他架构也这样做；我不知道。）

Borland's Pascal compilers are notorious for performing that optimization. The compiler transforms this code:

Borland 的 Pascal 编译器因执行这种优化而臭名昭著。编译器转换此代码：

for i := x to y do
  foo(i);

into an internal representation more akin to this:

变成更类似于此的内部表示：

tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
  foo(i);
  Inc(i);
  Dec(tmp);
end;

(I say notorious not because the optimization affects the outcome of the loop, but because the debugger displays the counter variable incorrectly. When the programmer inspects i, the debugger may display the value of tmpinstead, causing no end of confusion and panic for programmers who think their loops are running backward.)

（我说臭名昭著不是因为优化影响了循环的结果，而是因为调试器错误地显示了计数器变量。当程序员检查时i，调试器可能会显示 的值，这tmp对思考的程序员造成了无休止的混乱和恐慌他们的循环向后运行。）

The idea is that even with the extra Incor Decinstruction, it's still a net win, in terms of running time, over doing an explicit comparison. Whether you can actually noticethat difference is up for debate.

这个想法是，即使有额外的Inc或Dec指令，就运行时间而言，与进行明确的比较相比，它仍然是净胜出。你是否真的能注意到这种差异还有待商榷。

But note that the conversion is something the compiler would do automatically, based on whether it deemed the transformation worthwhile. The compiler is usually better at optimizing code than you are, so don't spend too much effort competing with it.

但请注意，转换是编译器会自动执行的操作，具体取决于它是否认为转换值得。编译器通常比你更擅长优化代码，所以不要花太多精力去与之竞争。

Anyway, you asked about C++, not Pascal. C++ "for" loops aren't quite as easy to apply that optimization to as Pascal "for" loops are because the bounds of Pascal's loops are always fully calculated before the loop runs, whereas C++ loops sometimes depend on the stopping condition and the loop contents. C++ compilers need to do some amount of static analysis to determine whether any given loop could fit the requirements for the kind of transformation Pascal loops qualify for unconditionally. If the C++ compiler does the analysis, then it could do a similar transformation.

无论如何，你问的是 C++，而不是 Pascal。C++“for”循环不像Pascal“for”循环那样容易应用这种优化，因为Pascal循环的边界总是在循环运行之前完全计算，而C++循环有时取决于停止条件和循环内容。C++ 编译器需要进行一些静态分析，以确定任何给定的循环是否能够满足 Pascal 循环无条件满足的转换类型的要求。如果 C++ 编译器进行分析，那么它可以进行类似的转换。

There's nothing stopping you from writing your loops that way on your own:

没有什么可以阻止您以这种方式自己编写循环：

for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
  array[i] = do stuff

Doing that mightmake your code run faster. Like I said before, though, you probably won't notice. The bigger cost you pay by manually arranging your loops like that is that your code no longer follows established idioms. Your loop is a perfectly ordinary "for" loop, but it no longer lookslike one — it has two variables, they're counting in opposite directions, and one of them isn't even used in the loop body — so anyone reading your code (including you, a week, a month, or a year from now when you've forgotten the "optimization" you were hoping to achieve) will need to spend extra effort proving to himself or herself that the loop is indeed an ordinary loop in disguise.

这样做可能会使您的代码运行得更快。不过，就像我之前说的，你可能不会注意到。像这样手动安排循环所付出的更大成本是您的代码不再遵循既定的习惯用法。你的循环是一个非常普通的“for”循环，但它看起来不再像一个——它有两个变量，它们以相反的方向计数，其中一个甚至没有在循环体中使用——所以任何阅读你的代码（包括您，一周、一个月或一年后，当您忘记了您希望实现的“优化”时）将需要花费额外的精力向自己证明该循环确实是一个普通的循环变相。

(Did you notice that my code above used unsigned variables with no danger of wrapping around at zero? Using two separate variables allows that.)

（你有没有注意到我上面的代码使用了无符号变量，没有在零处回绕的危险？使用两个单独的变量可以实现这一点。）

Three things to take away from all this:

从这一切中要带走三件事：

1. Let the optimizer do its job; on the whole it's better at it than you are.
2. Make ordinary code look ordinary so that the special code doesn't have to compete to get attention from people reviewing, debugging, or maintaining it.
3. Don't do anything fancy in the name of performance until testing and profiling show it to be necessary.

1. 让优化器完成它的工作；总的来说，它比你更擅长。
2. 让普通代码看起来很普通，这样特殊代码就不必为了引起、调试或维护它的人的注意而竞争。
3. 在测试和分析表明它是必要的之前，不要以性能的名义做任何花哨的事情。

回答by Alex Martelli

If you have a decent compiler, it will optimize "counting up" just as effectively as "counting down". Just try a few benchmarks and you'll see.

如果你有一个像样的编译器，它会优化“向上计数”和“向下计数”一样有效。只需尝试一些基准测试，您就会看到。

回答by Brian Neal

So you "read" that couting down is more efficient? I find this very difficult to believe unless you show me some profiler results and the code. I can buy it under some circumstances, but in the general case, no. Seems to me like this is a classic case of premature optimization.

所以你“读”到计数更有效？我发现这很难相信，除非您向我展示一些分析器结果和代码。在某些情况下我可以购买它，但在一般情况下，不会。在我看来，这是一个过早优化的经典案例。

Your comment about "register int i" is also very telling. Nowadays, the compiler always knows better than you how to allocate registers. Don't bother using using the register keyword unless you have profiled your code.

您对“register int i”的评论也很有说服力。如今，编译器总是比你更了解如何分配寄存器。除非您对代码进行了概要分析，否则不要使用 register 关键字。

回答by Andrew

When you're looping through data structures of any sort, cache misses have a far bigger impact than the direction you're going. Concern yourself with the bigger picture of memory layout and algorithm structure instead of trivial micro-optimisations.

当您遍历任何类型的数据结构时，缓存未命中的影响远大于您前进的方向。关注内存布局和算法结构的大局，而不是微不足道的微优化。

回答by Mikhail Semenov

You may try the following, which compiler will optimize very efficiently:

您可以尝试以下操作，哪个编译器将非常有效地优化：

#define for_range(_type, _param, _A1, _B1) \
    for (_type _param = _A1, _finish = _B1,\
    _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
    _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))

Now you can use it:

现在你可以使用它：

for_range (unsigned, i, 10,0)
{
    cout << "backwards i: " << i << endl;
}

for_range (char, c, 'z','a')
{
    cout << c << endl;
}

enum Count { zero, one, two, three }; 

for_range (Count, c, three, zero)
{
    cout << "backwards: " << c << endl;
}

You may iterate in any direction:

您可以向任何方向迭代：

for_range (Count, c, zero, three)
{
    cout << "forward: " << c << endl;
}

The loop

循环

for_range (unsigned,i,b,a)
{
   // body of the loop
}

will produce the following code:

将产生以下代码：

 mov esi,b
L1:
;    body of the loop
   dec esi
   cmp esi,a-1
   jne L1 

回答by Samuel Danielson

Everyone here is focusing on performance. There is actually a logical reason to iterate towards zero that can result in cleaner code.

这里的每个人都专注于性能。实际上有一个合乎逻辑的原因是向零迭代，这可以导致更清晰的代码。

Iterating over the last element first is convenient when you delete invalid elements by swapping with the end of the array. For bad elements not adjacent to the end we can swap into the end position, decrease the end bound of the array, and keep iterating. If you were to iterate toward the end then swapping with the end could result in swapping bad for bad. By iterating end to 0 we know that the element at the end of the array has already been proven valid for this iteration.

当您通过与数组末尾交换来删除无效元素时，首先迭代最后一个元素很方便。对于不与末端相邻的坏元素，我们可以交换到末端位置，减少数组的末端边界，并继续迭代。如果您要迭代到最后，那么与最后交换可能会导致交换坏的。通过迭代 end 到 0，我们知道数组末尾的元素已经被证明对这次迭代有效。

For further explanation...

进一步解释...

If:

如果：

1. You delete bad elements by swapping with one end of the array and changing the array bounds to exclude the bad elements.

1. 您可以通过与数组的一端交换并更改数组边界以排除坏元素来删除坏元素。

Then obviously:

那么很明显：

1. You would swap with a good element i.e. one that has already been tested in this iteration.

2. 您将更换一个好的元素，即在此迭代中已经过测试的元素。

So this implies:

所以这意味着：

1. If we iterate away from the variable bound then elements between the variable bound and the current iteration pointer have been proven good. Whether the iteration pointer gets ++ or -- doesn't matter. What matters is that we're iterating away from the variable bound so we know that the elements adjacent to it are good.

3. 如果我们从变量边界迭代，那么变量边界和当前迭代指针之间的元素已经被证明是好的。迭代指针是 ++ 还是 -- 并不重要。重要的是我们正在迭代远离变量边界，所以我们知道与它相邻的元素是好的。

So finally:

所以最后：

1. Iterating towards 0 allows us to use only one variable to represent the array bounds. Whether this matters is a personal decision between you and your compiler.

4. 向 0 迭代允许我们只使用一个变量来表示数组边界。这是否重要是您和编译器之间的个人决定。