Optimization is often counter-intuitive
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
There’s the naïve solution:
void *currentInstruction = GetCurrentAddress();
If you look at the disassembly, you’ll get something like this:
mov eax, [esp]
mov [currentInstruction], eax
“Pah,” you say to yourself, “look at how inefficient that is.
I can reduce that to two instructions. Watch:
L1: pop currentInstruction
That’s half the instruction count of your bloated
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 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
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
It looks at the top of the return address predictor stack and
says, “I bet that
RET instruction is going to return to that
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
instruction, the return address predictor stack looks like this:
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
The return address predictor stack and the actual stack
now look like this:
But instead of executing a
you pop off the return address. This removes it from the
actual stack, but doesn’t remove it from the return address
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
L1 at all.
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.
RET instruction, the return address
predictor stack looks like this:
Eventually your caller returns. Again, the processor consults its
return address predictor stack and speculatively executes
caller1. But that’s not where you’re returning
to. You’re really returning to
And so on. By mismatching the
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
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.