4

I was reading this article, and I noticed the jz instruction. This got me thinking:

Would the assembly of this code

for (int i=max;i!=0;--i){
    //Some operation
}

outperform the assembly of this code?

for (int i=0;i<max;++i){
    //Some operation
}

As long as you don't care that your data gets processed with an increasing i, there is no semantic difference. Cache misses shouldn't suffer either, because they can work sequentially either way.

I'm not good enough at assembly to write examples, but I would think that the first example would only use a jz. The second would use a cmp, then a jg, and also require another variable, max. The first example would only need the loop counter, because the 0 is implicit.

This may also be something that compilers use to optimize already, but I can imagine cases where it wouldn't be able to make the optimization.

5

3 Answers 3

2

Let's say that we have cmp a,b.

The processor will make a temporary subtraction of operands (without affecting their values), setting the flags properly and after this your jmp jump operation are evaluated.

So, it's faster in you example to make a jz, rather then a cmp and a jmp.

1
  • i forgot that the decrement would set the zero flag. good point.
    – JustKevin
    Sep 5, 2014 at 14:29
0

I'd consider this a largely solved problem with modern compilers. Or if not solved, then at least usually right, applying heuristics to yield better loop transforms. For x86[-64], there are more important considerations, e.g., does the loop 'body' fit in the instruction cache? Is the jump destination suitably aligned? Is the branch prediction effective?

There are multiple approaches to implementing loops with x86. e.g.,

  • Use of the j[e|r]cxz instruction, avoiding flags registers - though slower to decode.

  • Using sub or add prior to j<cond> rather than dec or inc to avoid partial flags register stalls.

The operation will matter too. is max known at compile time?

for (int i = 0; i < max / 4; i++)
{
    operation;
    operation;
    operation;
    operation;
}

If operation is simple enough (e.g., a floating-point operation), it might benefit from this sort of n-way scheduling. If each operation depends on the previous operation, it won't.

Have a look at something like GMP. The mpn/x86[-64] directories optimize loops for different micro-architectures. Agner Fog's optimization manuals are an excellent resource.

0

Sometimes having the loop count down can free up a register, which will probably be more useful (especially on x86-32, where registers are scarce), than any difference in jump conditions.

However, counting down in the loop can prevent auto-vectorisation. If your calculations can be done with SSE/AVX/whatever, you may need to write code like

for (i=end; i;){
    i-=4;
    val[i+0] = foo(i);
    val[i+1] = foo(i);
    val[i+2] = foo(i);
    val[i+3] = foo(i);
    }

and then you have to make sure end%4 == 0, all to save one register.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.