| ▲ | bugake a day ago |
| 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. |
|
| ▲ | StilesCrisis a day ago | parent | next [-] |
| Optimizers eat stuff like this up. It'll restructure your loop however it wants. |
| |
| ▲ | bugake a day ago | parent [-] | | You should always check the compiled assembly with Compiler Explorer because compilers sometimes avoid certain optimizations for convoluted reasons, which are hard to predict. |
|
|
| ▲ | sltkr a day ago | parent | prev | next [-] |
| > 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. |
| |
| ▲ | nkurz a day ago | parent | next [-] | | 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? | |
| ▲ | bugake a day ago | parent | prev [-] | | 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. | | |
| ▲ | StilesCrisis a day ago | parent [-] | | 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. | | |
|
|
|
| ▲ | flohofwoe a day ago | parent | prev [-] |
| > ...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) |
| |
| ▲ | bugake 8 hours ago | parent [-] | | 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. | | |
| ▲ | flohofwoe 2 hours ago | parent [-] | | 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". |
|
|