Hacker News Reader

Comment by bugake | Hacker News Reader

For the uninformed: counting backwards in a for loop is faster because comparing an unsigned integer against 0 is generally faster than comparing it against any other value.

It also says not to use `for (i >= 0)` because any unsigned integer is >= 0, and the loop will never end.

View on HN

Optimizers eat stuff like this up. It'll restructure your loop however it wants.

You should always check the compiled assembly with Compiler Explorer because compilers sometimes avoid certain optimizations for convoluted reasons, which are hard to predict.

> For the uninformed: counting backwards in a for loop is faster because comparing an unsigned integer against 0 is generally faster than comparing it against any other value.

No it's not. It generally makes no difference at all.

If you disagree, I dare you to write a benchmark that demonstrates a difference between forward and backward iteration on a modern CPU.

Hmm. I think both of you are both right and wrong!

That is, I claim that while it is no faster to execute a comparison against zero, it still can be faster to finish a loop at zero. This is because internal to the processor, the comparison and the branch are two separate ops. The comparison essentially does an arithmetic operation that sets a flag but throws away the result, and then the branch acts on it.

But if you finish at zero, the flag you are using is already set by the decrement, so no additional comparison op is necessary. Now normally this doesn't matter, since the processor is multiscalar with sufficient execution ports to fit in an extra comparison with no increase in total cycles spent. But in a tiny and highly optimized loop, occasionally you can get about 20% gain from having one fewer op to execute.

Getting this to actually happen can be complicated because modern processors do op-fusion that can "fuse" the CMP and branch back into something that can be executed on a single port. But DEC-JNZ can be fused too, which still gives it an advantage. More details on this here: https://chipswiki.org/Macro-operation_fusion

Now does anyone want to finish the "ground speed readout" routine (https://theaviationgeekclub.com/sr-71-blackbird-pilot-tells-...) by pointing out actually how with modern processors I'm actually wrong too?

I quote from "Optimizing Software in C++" by Agner Fog:

"Comparing an integer to zero is sometimes more efficient than comparing it to any other number. Therefore, it is slightly more efficient to make a loop count down to zero than to make it count up to some positive value, n. But not if the loop counter is used as an array index. The data cache is optimized for accessing arrays forwards, not backwards."

Yet that text was written for older CPUs. Modern CPUs are better at prefetching backwards access patterns, but if you try a microbenchmark with backwards array traversal, you may get misleading results.

Agner Fog is also discussing CPU architecture, not high-level language. The whole point is that the optimizer _already_ takes knows these things and rewrites your code automatically. If you write a zero-to-100 loop in C, that doesn’t mean the assembly will literally show a value going from zero to 100; it may unroll, or reverse the loop order, or any weird combination of things that the optimizer has decided will be equivalent and fast.

That's not guaranteed. An array or variable could be modified by another thread, meaning that reversing the order of operations could produce a different result. The compiler cannot always assume that such transformations are safe, and that's why the compiler avoids implementing a lot of those optimizations that you expect to be done automagically.

So you cannot expect the compiler to automatically perform every possible optimization. The programmer still needs to understand how the code behaves and write it with performance in mind.

You may be perfectly sure that no other thread modifies the data, but the compiler doesn't know, so it avoids all kind of optimizations.

If you expect the compiler to perform those optimizations automatically, you still have to do things like declare certain variable variables and or function parameters as constant (since the compiler may otherwise have to assume that their values could be modified by side effects/threads, preventing certain optimizations), use specific attributes or annotations on functions, and provide specific compilation flags. That's more complex than simply coding the for loop backwards.

And the worst thing is that frequently the compiler assumes a constant could be modified anyway, and avoids optimizing just in case.

> ...counting backwards in a for loop is faster...

Maybe in 1990 ;)

(it's one of many cargo cult wisdom snippets that have become mostly obsolete once C compilers got proper optimizer passes and CPUs got all sorts of pipeling tricks)

A cargo cult wisdom snippet is the belief that compilers automagically apply every possible optimization. But they don't, because compilers don't know everything you know. Compilers have to assume that your code can be subject to side effects you never thought of, that would change the result of the code, so a lot of possible optimizations are avoided.

Well you check the compiler output and profile of course. But "generalized" performance advice like "use reverse loops" hasn't been relevant for a long time, it's a similar myth like "pre-increment is faster than post-increment".

Reply on news.ycombinator.com