Optimization is often counter-intuitive

Raymond Chen

Raymond


Anybody who’s done intensive optimization knows that optimization
is often counter-intuitive.
Things you think would be faster often aren’t.



Consider, for example, the exercise of obtaining the current instruction
pointer.
There’s the naïve solution:



__declspec(noinline)
void *GetCurrentAddress()
{
return _ReturnAddress();
}


void *currentInstruction = GetCurrentAddress();



If you look at the disassembly, you’ll get something like this:



GetCurrentAddress:
mov eax, [esp]
ret


call GetCurrentAddress
mov [currentInstruction], eax



“Pah,” you say to yourself, “look at how inefficient that is.
I can reduce that to two instructions. Watch:



void *currentInstruction;
__asm {
call L1
L1: pop currentInstruction
}


That’s half the instruction count of your bloated

girly-code
.”



But if you sit down and race the two code sequences, you’ll find
that the function-call version is faster by a factor of two!
How can that be?



The reason is the “hidden variables” inside the processor.
All modern processors contain much more state than you can see
from the instruction sequence. There are TLBs, L1 and L2
caches, all sorts of stuff that you can’t see.
The hidden variable that is important here is the
return address predictor.



The more recent Pentium (and I believe also Athlon)
processors maintain an internal
stack that is updated by each CALL
and RET instruction.
When a CALL is executed, the return address is pushed both onto
the real stack (the one that the ESP register points to) as well
as to the internal return address predictor stack; a RET
instruction pops the top address of the return address predictor stack
as well as the real stack.



The return address predictor stack is used when the processor
decodes a RET instruction.
It looks at the top of the return address predictor stack and
says, “I bet that RET instruction is going to return to that
address.”
It then speculatively executes the instructions at that address.
Since programs rarely fiddle with return addresses on the stack,
these predictions tend to be highly accurate.



That’s why the “optimization” turns out to be slower.
Let’s say that at the point of the CALL L1
instruction, the return address predictor stack looks like this:

























Return address
predictor stack:
 caller1->caller2->caller3->
Actual stack: caller1->caller2->caller3->


Here, caller1 is the function’s caller,
caller1 is the function’s caller’s caller,
and so on. So far, the return address predictor stack is right on target.
(I’ve drawn the actual stack below the return address predictor stack
so you can see that they match.)



Now you execute the CALL instruction.
The return address predictor stack and the actual stack
now look like this:





























Return address
predictor stack:
 L1->caller1->caller2->caller3->
Actual stack: L1->caller1->caller2->caller3->


But instead of executing a RET instruction,
you pop off the return address. This removes it from the
actual stack, but doesn’t remove it from the return address
predictor stack.





























Return address
predictor stack:
 L1->caller1->caller2->caller3->
Actual stack: caller1->caller2->caller3->caller4->


I think you can see where this is going.



Eventually your function returns. The processor decodes your
RET instruction and looks at the
return address predictor stack and says,
“My predictor stack says that this RET is going
to return to L1. I will begin speculatively executing there.”



But oh no, the value on the top of the real stack
isn’t L1 at all.
It’s caller1. The processor’s return address predictor
predicted incorrectly, and it ended up wasting its time studying
the wrong code!



The effects of this bad guess don’t end there.
After the RET instruction, the return address
predictor stack looks like this:

























Return address
predictor stack:
 caller1->caller2->caller3->
Actual stack: caller2->caller3->caller4->


Eventually your caller returns. Again, the processor consults its
return address predictor stack and speculatively executes
at caller1. But that’s not where you’re returning
to. You’re really returning to caller2.



And so on. By mismatching the
CALL and RET instructions,
you managed to cause every single return address prediction on the stack
to be wrong. Notice in the diagram that,
in the absence of somebody playing games with the return address
predictor stack of the type that created the problem initially,
not a single prediction on the return address
predictor stack will be correct
.
None of the predicted return addresses match up with actual return
addresses.



Your peephole optimization has proven to be shortsighted.



Some processors expose this predictor more explictly.
The Alpha AXP, for example, has several types of control flow
instructions, all of which have the same logical effect,
but which hint to the processor how it should maintain its
internal predictor stack.
For example, the
BR instruction says, “Jump to this address, but do not
push the old address onto the predictor stack.”
On the other hand, the
JSR instruction says, “Jump to this address, and push
the old address onto the predictor stack.”
There is also a RET instruction that says,
“Jump to this address, and pop an address from the predictor stack.”
(There’s also a fourth type that isn’t used much.)



Moral of the story: Just because something looks better
doesn’t mean that it necessarily is better.

Raymond Chen
Raymond Chen

Follow Raymond