alt Hacker News> 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.
Replies
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.
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?