C++ - extremely strange machine code behaviour

Question

The full code is here: http://pastebin.com/MM3vWmqA

In the function fast_generator I've added comments to two statements. If you switch those statements, the code will run ~1.8x faster. If you remove the first statement the code will perform faster than the original version, but slower compared to if they were switched.

The test cases should be the following.

First - slowest. 452ms.

counter++;
i--;

Second - faster than the first one. 280ms.

i--;
counter++;

Third - faster than the first, but slower than the second one. 421ms.

i--;

The assembler output for the original statements is.

inc edx
mov eax, 6

I have verified that when switching those statements the assembler output stays the same, with the only difference of these asm instructions being interchanged.

I've tested it with VC++10 and VC++11, same behaviour. Can someone explain why switching these statements speeds up the algorithm ~1.8x? If you think that std::clock() is not accurate, change size = 7. On my machine the difference with size = 7 is 12000ms vs 7000ms.

Answer 1

Your slow examples are decrementing i immediately before using it to index the array at the beginning of the loop. Your fast example adds an intervening step. Without being privy to the internal architecture of the processor it's impossible to know for sure, but most likely what is happening is the processor already has buffer[i] in its pipeline, but the decrement invalidates that value, causing a pipeline stall. With the intervening step it has more time to recover the correct value before it is needed.

By the way, mov eax, 5 isn't the instruction that's doing the i--. It would be helpful to post more of the assembly context, for those of us without your compiler.