Does register selection matter to performance on x86 CPUs?
fiigii.com
fiigii.com
It also answers the question "why don't compilers emit INC and DEC?" Short answer: they don't set the carry, so on some CPUs that means that they cause an unnecessary dependency on the previous instruction that sets EFLAGS.
The x86 ISA really is a mess!
No, it's not. I've written the compilers for both x86 and x64. One should not look for too much idealistic "symmetry" but look at it as a domain specific encoding language. Behind that encoding is anyway huge machinery that significantly speeds up that what is written in the language, and it's even proven that, when there is enough silicon, it is of advantage that some optimizations are actually done during the execution. Some execution statistics are simply dependent on the information which dynamically depends on execution and can't be pre-coded by a compiler.
Since long ago, even those processors that started as RISC got more and more instructions and started to worry about having them encoded with less bits.
And that all doesn't mean that the compilers shouldn't be as smart as possible to use the hardware the best it can be used.
Even ignoring all the annoying mismatches in semantics, all the awkwardly-fit expansions and prefixes do not lead to a good encoding. And it's far slower to figure out how long an instruction is than it should be.
Or heck, even just the fact that real mode is still a thing.
edit: there is no documented direct way to flip the segment/selector bit, which is the reason why you need documented vm86 mode. The hardware always calculate the linear address according to whatever is in shadow descriptor of segment/selector register, difference between real/vm86 and protected mode is what happens when you store something into there.
Although, they could disable real mode support in some CPUs as a market segmentation mechanism. Running a 64-bit OS with EFI boot, most users probably don’t really need real mode support.
So if someone has a legacy app running in a Windows XP/Vista/2003/etc VM, that VM needs real mode to boot.
And diagonally, the instruction set is surely not the reason why every internet page is tracked by thousands of companies and has to download more megabytes than the total RAM the whole x86 computers had.
And like I've said, all instruction sets since a while have to take care to be "compressed" in a way, which is simply a total opposite of what the critics pointed since RISC was introduced. Pure RISC was/is useful only under some very specific assumptions.
The appearance of "mess" is a result of "if was successful." But the problems it solved were/are real.
"It's not a mess" is quite another.
But 'compression' and 'mess' are very very different things. You can have organized compression. Look at the length encoding on RISC-V, or something. No prefix bytes in sight. On x86 the balance and methodology for getting different instruction sizes is completely garbage for historical reasons.
> The appearance of "mess" is a result of "if was successful." But the problems it solved were/are real.
It's because it's been collecting legacy since it was 8-bit all the way to 64-bit with vector units, not as an inevitable result of being successful.
> Since long ago, even those processors that started as RISC got more and more instructions and started to worry about having them encoded with less bits.
x86-64 is not very space efficient, because of all the REX prefixes. Look at the comparative sizes of AArch64 and x86-64 binaries if you don't believe me.
It's pretty awesome. Remember engineering doesn't happen in a void. It's influenced all sorts of shit including economics, existing investments etc.
The reason it matters is because a disproportionate amount of energy is spent in the instruction decode system.
And that affects your battery life.
The “mess”, though, is just a natural artifact of longevity. Many years of decisions that made sense in the moment accumulated to appear to be a “what WERE they thinking?” situation when, in fact, they were addressing the market forces and technology constraints of the day.
In the end, nobody buys your product because the elegant design means that two generations of your product later it will have good performance. Sales are driven by what you can do in the here-and-now. If you do that well enough, you can live long enough to accumulate the kind of cruft that is the X86 ISA.
> In the end, nobody buys your product because the elegant design means that two generations of your product later it will have good performance. Sales are driven by what you can do in the here-and-now. If you do that well enough, you can live long enough to accumulate the kind of cruft that is the X86 ISA.
I think Itanium, or the pursuit of making Itanium the replacement for x86, demonstrated these quite well.
Battery life in benchmarks (and in a lot of real-world use cases) is more about how long the CPU spends in its halted sleep state, and how much power that takes, than its "full throttle" power usage.
Mobile x86 CPUs since Core Duo(?) have the ability to turn off parts of their caches in lower-power modes, for this reason.
[Edit:] I got deja vu, searched my comment history, and found we were still harping on about this exact same crap 9 years ago: https://news.ycombinator.com/item?id=2061500
Even on 32nm, instruction decoding was a tiny % of die space!
Exactly that. Looking what the actual problems with the processors that tried to be better than x86-line were, the good or bad instruction "decoding" was certainly not what made them worse than x86-line, at the end.
A lot of the information there is a decade out of date.
And neither Clang nor GCC emits inc or dec: https://godbolt.org/z/47y8K3
OK, but what does it even mean that they avoid AL then, if they use them for 8-bit math? Under what other scenarios would they even want to use them?
FWIW, compilers could use 32-bit arithmetic ops almost all the time even when bytes are used in the source, because excect for right shifts and division, information flows only to more significant bits, so 32-bit bit ops give you the right results in the low bits.
In fact, I thought they did this more often – but when I looked into it recently they seem to prefer the low 8 bit registers.
> but they don't use the high bytes.
Not often, but of course the use case for the "second least significant byte" is very narrow in the first place [2]! If you just want to deal with byte values, you'll use the low bytes, after all.
The high 8-bit values are reserved for special cases, e.g., extracting that particular byte, and there compilers do use them (at least gcc, clang and icc on the first try, but not msvc):
The performance characteristics for the high bytes are quite different from the low bytes on modern, x86 too: see [1]!
> And neither Clang nor GCC emits inc or dec
Yes, if you don't set the march they will compile for an archaic blend of chips at least one of which may have the old inc/dec behavior.
Try setting a "modern" march flag like Haswell and fixing the issue where i wasn't actually used except as the loop induction variabale (allowing loop transformations away from simple +1) and both clang and gcc use inc:
---
[1] https://stackoverflow.com/a/45660140/149138
[2] It is possible one of the original motivations for the high bytes was to double the number of 8 byte registers in the 16 bit era. I.e., 8x byte registers was considered significantly better than 4x, and you couldn't use the low byte of di,si,sp and bp for other reasons.
In 64-bit, however, we now have 8 additional registers each with a low byte variant (r8b-r15b), so there are plenty of low byte registers for most work, so the remaining use of the high byte registers mostly seems to be taking advantage of their ability to quickly access the 2nd byte of a larger value.
[1] Someone else please speak up, but the Pentium II seems to be when Intel began leaning on microcode to optimize execution. https://en.wikipedia.org/wiki/Intel_Microcode
[2] Not always, of course. Sometimes local, runtime information is more important, as JIT enthusiasts love to point out. The problem is that the instrumentation to analyze and utilize that information is costly and incurred perpetually, whereas with static compilation it's a one-time deal.[3] As Rust and C++ has proven, many developers are willing to put up with several orders of magnitude more costs up-front than could ever be tolerated in a JIT, especially the JITs inside the CPU.
[3] This is a similar issue to GCs (mark & sweep and reference counting), where memory must be scanned and sometimes even copied many times during runtime whereas in static memory management there's exactly one operation for allocation and one for deallocation. So GC is usually (but, again, not always) slower. Optimizations like bump allocations (which in static compilation is often simply "the stack") that aggregate and amortize some costs don't change the fundamental costs.
Most important instructions map 1:1 to CPU micro-ops, with memory operands (on x86) being mapped to separate load/store micro-ops. There are cases where instructions map to long sequences (e.g. VMENTER) or get combined into one micro-op (e.g. compare-and-branch), but this is far from a JIT compiler.
From a wholistic viewpoint I think it's fair to characterize modern CPUs as JIT-like. It's easy to trivialize individual aspects of the whole. You can do the same for software JITs. They're not magic (notwithstanding the breathless claims and river of thesis papers), and often simpler is better, anyhow (e.g. LuaJIT). For obvious reasons the tactics employed by CPUs will tend toward the simpler end of the spectrum.
I'm trying to figure out if there is anything generally useful for now in these papers.
Wasn’t that the Pentium Pro?
PS: Hehe.. anyone remember U/V pipe optimization? :) Michael Abrash books on assembly and 3D game programming, and assembly profiling on real hardware FTW.
The same for INC/DEC (1 byte!) vs ADD/SUB --- and if my years of experience writing Asm for x86 (and easily beating compilers at size, speed, often both) have any good advice to give, it's to optimise for size first and then only in specific and particular cases give up size for speed. While the size-optimised code might lose (sometimes a lot) in a microbenchmark, cache misses are extremely expensive (especially when "cache miss" actually means "swapped to disk") so unless it's a special tight loop that really needs the last few % squeezed out of it because it's a huge time-sink, trying to optimise for speed "everywhere" can actually be counterproductive overall.
Nitpick:
MOVZX EAX, BYTE PTR [RDI]
AND EAX, 0xFFFFFF00
MOV EBX, EAX // no partial register stall
MOV EBX, EAX // partial register stall
2. MOVZX EAX, BYTE PTR [RDI]
AND EAX, 0xFFFFFF00
MOV EBX, EAX // no partial register
These don't do the same thing
No, that's not what was written there. The manual is clear:
For LEA instructions with three source operands and some specific situations, instruction latency has increased to 3 cycles" where one of these spcific situations is: "LEA that uses base and index registers where the base is EBP, RBP, or R13."
Note "with three source operands" and "uses base and index" as in "both at the same time." So it's not enough that LEA just "uses EBP, RBP or R13."
LEA is often used, and often used with EBP/RBP. It wouldn't be in Intel's interest to harm common uses (the existing already compiled code base).
If you care about how long which instruction takes in order to make some implementation decisions, the article just too misleading when it talks about the LEA.
The list given in that item is "or", i.e., if any of those conditions apply, you get the slow lea. The prose isn't giving additional conditions, it is just summarizing the list (although I can determine that not by careful parsing of the prose but rather because it's the only way the thing makes sense).
Only LEAs which use both BP and the index registers at the same time (or the three operand LEA variants) are "slow". It's documented in the said Intel's manual, even with the examples. One can write a lot of LEAs without three operands or without index register and of course use {E,R}BP in them without any issue.
The relevant section from which the article took the material but made wrong conclusion is:
"3.5.1.2 Using LEA"
If you are just saying that the issue is that the author says "ebp as base" rather than "ebp as base in an indexed addressing mode", then I agree.
Correct. I specifically wrote "One can write a lot of LEAs without three operands or without index register and of course use {E,R}BP in them without any issue."
Even if "OR" list notes that some uses of LEA are slower (actually, if I would say, with "higher latency"), LEA with BP is still too useful to reduce the logic to the article's claim:
"using EBP, RBP, or R13 as the base address will make LEA slower."
No it won't for enough cases where it's important to use it.
I didn't even address the topic that higher latency doesn't even have to mean that the throughput is reduced at all, when the rest of the code fits. But even at the low level of precision of the article, it's still a wrong claim, that what's written in that sentence.
It's just a detail, but at this level (of caring about which instruction to use where), everything is exactly about the details.
I probably misunderstood what you were saying here:
> Note "with three source operands" and "uses base and index" as in "both at the same time."
When you said "both" I thought you were referring to both clauses you mentioned ("3-arg" and "base and index"), but I see now you may have saying both base and index (it was the mention of 3-arg that threw me off).
Slow LEA is slower in a throughput sense too: half the throughput on modern mainstream Intel except Ice Lake.
> I didn't even address the topic that higher latency doesn't even have to mean that the throughput is reduced at all, when the rest of the code fits.
Agreed, but that's true of almost any fine-granied performance discussion ever. I think it's fine to say that a LEA with half the throughput and triple the latency is slower in a sense, even though "in-situ" there may be plenty of cases where it makes no measurable difference. The same is true of other slow stuff like muls, divs, branch mispredictions, atomic ops: there are cases where all of those don't matter (not just in an approximate sense, as in "the penalty is zero"). You are not wrong but always putting that caveat gets tiring, it would be nice if we could just assume it.
Beyond that, almost any use of a "slower" instruction can actually speed things up, e.g. due to an alignment or scheduling effect, but man I don't want to mention that every time either.
As a practical matter, few people have the capability to mentally simulate the pipeline to determine whether slow LEA is going to have an impact or not (and this is error prone and in any case not all the details are out there to do it totally accurately. So the problematic r13/rbp cases are mostly easy to avoid, just avoiding them seems like reasonable advice.
That's why the people should not do it most of the time, that's why we have compilers. And I claim that a compiler programmed in absolutes as advised by the article "just don't use EBP with LEA" would produce poor code.
And that much is easy to follow even by humans.
I'm wasn't even arguing for the use of the over-broad rule in the part you quoted: I was actually arguing for the use of the full rule but without worrying too much about the caveat that even using slow lea might be just as fast (or faster, due to non-monotonic effects).
There's nothing that prevents existing assemblers to already do this -- I haven't checked them though, since I used my own -- I use the term "compiler" as everything together up to the parts that produce the actual binary codes.
I know that e.g. gcc makes (or, at least, made) an explicit separation producing the assembly in the source form. But it still would be plausible that it's already implemented in such assemblers -- which would make the userbinator's argument here even less relevant.
It's kind of too little, too late though: you want the higher level compiler to be avoiding rbp/r13 in scenarios where this could occur and the assembler couldn't fix it. I don't think compilers do this, though.
The insight here is that LEAs which "use both BP[sic] and the index registers at the same time" is the same as "three operand LEA variants", because the instruction encoding does not allow using BP as a base without an offset. The offset is there, it's just encoded as 0; but the hardware does not bother to check for a 0 offset and emits a uop to add it anyway.
Assembly/Compiler Coding Rule 30. (ML impact, L generality) If an LEA instruction using the scaled index is on the critical path, a sequence with ADDs may be better.
As to the article, partial register stalls aren't that bad on modern CPUs, not 5-6 cycles. And CFLAG bits get renamed. I think the article gets at that.
Basically, anything which sticks out in a real benchmark gets hammered down and optimized by Intel.
There's the third operand --- it's just "hidden". Hence the somewhat misleading wording of that advice.
And that's not as important as you make it appear.
If you write [EBP + 24] (where the index register is simply not used), do you think that's a "slow" LEA?
The [EBP + 24] form is what my (and I guess most of other's) compiler produced most of the time. Open any program with disassembler and try to count how often index register is ever used with EBP, and how often no index register is used. Former happens practically never, the later (no index) is very common.
>"Consequently, on certain Intel architectures, compilers usually do not generate INC/DEC for loop count updating"
They then gave an example of a classic for loop. Can someone explain why compilers don't generate INC/DEC for loop count updating? I'm guessing this is an optimization. What is INC/DEC replaced with?
> Note, the rest of the article only talks about Intel micro-architectures
Now that's odd. What is special about those registers, that code using them can end up slower than the others?
Since x86 supports complex but useful addressing, the AGU was made fast so memory operations wouldn't be dog slow.
The LEA exploits this resource for computation rather than "just" for addressing memory, for example:
lea eax, [ecx+eax*2-30h]
For some reason, the AGU seems incapable of dealing with those registers as base I guess.
[1]: https://gmplib.org/~tege/x86-timing.pdf
[2]: http://www.nynaeve.net/?p=64 (point 3)
LEAs are calculated on ALU execution units like other ALU ops. r13 and rbp are special because the usual way of encoding those registers in an indexed addressing mode without an offset was repurposed instead for another mode: offset only or RIP-relative in x86-64.
This affected only ebp in x86-32 but also r13 in x86-64 because of the way the instruction was encoded.
As a result, if you want to use rbp as a base, you need to use an explicit offset (which can be zero) and that ends of triggering the "three source rule" for slow LEA in the case of indexed addressing, even though you have included any offset in the assembly.
Thanks for the detailed correction.
The PBLENDVB case is interesting: the VEX-encoded variant takes 2 uops in every uarch, but 1 uops (since Skylake) in the non-VEX encoded variant that takes XMM0 as a hardcoded input.
My guess is that it wasn't an execution or rename limit, since PBLENDVB should be "just as hard", but a decode or (pre-rename) uop format limit: i.e., the uop format in the IDQ couldn't handle three variable inputs, but the implicit xmm0 is fine (doesn't take any space). Or the decoders couldn't handle it. Still, once 3-input stuff like FMA did appear I don't know why it wasn't fixed. Possibly FMA has special handling...