Why some think ++i is faster than i++ ?

Originally posted in my portfolio.

A while ago, I have noticed reading some competitive programmers' code that a lot of them in their for and while loops tended to prefer using ++i instead of i++. For example you could see in their code:

for (;;++i) ...
while (--i) ...

So a question scratched my head to figure out why and if there is any real performance boost by using such expressions (since they were top competitive programmers).

The answer lies in the dark caves of compilers and assembler generation

So let's try to figure out what happens !

Analysis

Accessing an array index with an expression

Let's I have the following code:

// I have two variables 'a' and 'b'
arr[a+b];

When reading this instruction what does the compiler do ?
If we write what the compiler does in pseudo code it would give us something like this.

Get the value of a
Get the value of b
Calculate the expression a + b
Access the array position with the calculated index

Accessing the array index with a pre-increment

Now this time let's see what happens with ++i:

// I have a variable 'a' 
arr[++a];

the compiler translate this with:

Get the value of a
Increment that value
Store the new value
Access the array position with the calculated index

The breakthrough

Have you noticed a trend here ?

The compiler evaluate the expression inside the brackets before accessing the element. Which is different from what the usual i++ do !

if we have now:

// I have a variable 'a' 
arr[a++];

You can guess now how the compiler would translate that given the knowledge of what this instruction does:

Get the value of a
Store the value of a temporarily
Increment that value
Store the new value
Access the array position with the calculated index

Given the added storage - that might be interesting in the context of an array access but usually unnecessary in the context of a loop - we get an added instruction that could result, depending on the machine the code is executed on, a slight performance drop.

Closing words

You can guess by now that this syntax, in the context of modern machines the performance hit is generally not something to worry about. In addition to this I have found that usually compilers now optimize this kind of instruction to see if the value is really needed to be stored or can be dismissed. But this kind of questions is really helpful in understanding more how compilers work.

Comments

[naveenmittal]

I didn't get why compiler is storing value temporarily? Am I missing something?

[Vesa Piittinen]

I have not studied compilers, but this is what I think is the difference:

arr[i++]

1. Compiler finds i
2. Compiler finds ++ which will increment i
3. Compiler needs original value of i to access arr, so it makes a temporary clone before increment
4. Compiler increments i
5. Compiler accesses arr with value of temporary clone

Value of i cannot be used directly because it has been mutated, so a clone with previous value is required.

arr[++i]

1. Compiler finds ++ which will increment i
2. Compiler increments i
3. Compiler accesses arr with value of i

Value of i can be used directly.

[Hamza Tamenaoul]

If as an example a = 2, then arr[a++] requires the storage of the old value of a since after evaluating a++, a would be equal to 3, while it needs to access arr[2].