9 ms·

Does register selection matter to performance on x86 CPUs?

160 points by lelf 7y ago

deleted 7y ago
[deleted]
noelwelsh 7y ago
Related there is this old (old enough to be postscript, not PDF!) paper that compared register allocation on the usual 8 registers on Intel vs 32 virtual register that are then allocated to the 8 available registers. Doing the latter created faster code, suggesting that the CPU's register renaming is not as good as it could be. This was on a Pentium 2, so it might be that the results don't hold any more. It's also been at least a decade since I read this paper in detail so I might have remembered it wrong! http://www.smlnj.org/compiler-notes/k32.ps http://www.smlnj.org/compiler-notes/k32.ps
- vardump 7y ago
  Pentium 2 is almost 23 years old now. Some things might have changed a bit by now. :-)
- pizlonator 7y ago
  That's just saying that having more registers is better. That's definitely true if you only have 8. It's also not related to the key point of the original post: whether selecting different registers - in situations where doing so has no effect on spilling - could change performance.
  - noelwelsh 7y ago
    You've misunderstood...read the paper for the details. It's not that more registers are better, it's that they did a better job than the CPU at register allocation (Pentium 2 had 40 registers IIRC). Also note that my post starts with the word "related", indicating that I'm commenting on a similar, but identical, issue.
    - wahern 7y ago
      Modern CPUs are like miniature JIT compilers.[1] They do wondrous things but I guess it shouldn't be surprising that in critical sections static compilation with a more global perspective can often make better decisions.[2] I would think that would be even more true today than during the Pentium II era, or at least as true. Both the state-of-the-art and the resources that can be devoted to such optimizations have continued to progress for both static and JIT compilation. [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 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.
      - cwzwarich 7y ago
        The extent to which modern CPUs are “like JIT compilers” is highly overrated by SW people. 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.
        wahern 7y ago
        I also had in mind branch prediction units, and stuff like Intel's TSX. I assume these days the former bleeds into many other parts of the architecture, including the microcode; I'm certain (but can't say authoritatively) that the latter does. 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.
- sadiq 7y ago
  That's an interesting paper. For anyone on mobile who wants a PDF: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.863&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11...
- anonsivalley652 7y ago
  In the yee old'en days, only the length of opcode would make much of a difference or if it were implemented in a slightly different microcode path which would change the number of micro-ops slightly. Reg aliasing/renaming I think would make transfers between registers very fast unless a data hazard existed in subsequent/branch-predicted instructions (scheduling the "liveness" in the register file across the pipeline stages so it doesn't mess anything up). PS: Hehe.. anyone remember U/V pipe optimization? :) Michael Abrash books on assembly and 3D game programming, and assembly profiling on real hardware FTW.
  - bogomipz 7y ago
    What is the 'scheduling the "liveness" in the register file across the pipeline stages'? Is this part of garbage collecting or detecting when a register can be reallocated?
acqq 7y ago
> According to the Intel optimization manual, using EBP, RBP, or R13 as the base address will make LEA slower. 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.
- BeeOnRope 7y ago
  It's not clear and you are not correct in this case – at least per the actual behavior, and I assume the intent of the manual (but of course we can argue about whether the item is well-written). 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).
  - acqq 7y ago
    No, it's clear, especially if you'd know what it is about (BP is used in various calling conventions, so it has to be fast in common cases). That the list there is OR doesn't make every LEA which uses BP slow, as the article claims. 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"
    - BeeOnRope 7y ago
floatingatoll 7y ago
On Intel x86 CPUs; after the intro paragraphs: > Note, the rest of the article only talks about Intel micro-architectures
- deleted 7y ago
  [deleted]
lmilcin 7y ago
No numbers. I appreciate good theory, but it is much more useful when it was a backed by some experiments.
- BeeOnRope 7y ago
  Indeed, the article has several inaccuracies and lots of obsolete information, so it's a shame the author didn't try this stuff because they would have found a different story.
- djmips 7y ago
  Just saying x86 was a red flag because that encompasses such a huge swath of architectures and timeframes. No mention of AMD.
pechay 7y ago
1. MOV AL, BYTE PTR [RDI] 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
- vardump 7y ago
  Yeah. Second one would be shorter as XOR EBX, EBX, because EAX is always zero after that AND.
pcwalton 7y ago
This article does a great job answering the question "why don't compilers use AH/AL/etc. like DOS compilers did in the good old days?" Short answer: it causes unnecessary dependencies because the other parts of the register are preserved. 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!
- acqq 7y ago
  > 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.
  - Dylan16807 7y ago
    I don't know how anyone can look at the list of one-byte opcodes and conclude that x86 isn't a mess. 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.
    - pcwalton 7y ago
      > I don't know how anyone can look at the list of one-byte opcodes and conclude that x86 isn't a mess. Or heck, even just the fact that real mode is still a thing.
f00zz 7y ago
Nice article, I learned something. Nitpick: MOVZX EAX, BYTE PTR [RDI] AND EAX, 0xFFFFFF00 MOV EBX, EAX // no partial register stall I think the author probably meant AND EAX, 0xFF. But the AND is redundant, as MOVZX is already zero-extending the byte. The snippet immediately above needs the AND, though.
- bonzini 7y ago
  I think he meant MOVZX EBX, [RDI] + AND EAX, 0xFFFFFF00 + OR EAX, EBX. The sequence would be equivalent to MOV AL, [RDI].
rwallace 7y ago
> According to the Intel optimization manual, using EBP, RBP, or R13 as the base address will make LEA slower. Now that's odd. What is special about those registers, that code using them can end up slower than the others?
- magicalhippo 7y ago
  The post explains it. LEA without those registers used as base can be computed in the address generation unit, which is separate from the regular arithmetic unit(s). 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] With normal arithmetic that would be three instructions that could not be done in parallel, but with LEA it's done in a single clock cycle[1]. More details here[2]. For some reason, the AGU seems incapable of dealing with those registers as base I guess. [1]: https://gmplib.org/~tege/x86-timing.pdf https://gmplib.org/~tege/x86-timing.pdf [2]: http://www.nynaeve.net/?p=64 http://www.nynaeve.net/?p=64 (point 3)
  - BeeOnRope 7y ago
    The article is wrong, AGU hasn't been used for LEA on mainstream Intel CPUs in a decade at least. 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.
    - magicalhippo 7y ago
      Alrighty then, time for me to never do any x86 asm programming again I see :) Thanks for the detailed correction.
userbinator 7y ago
We can see using ADD with EAX as dst register is 1-byte short than another, so that has higher code density and better cache-friendly. 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.
- thedance 7y ago
  I appreciate the sentiment but compilers optimizing size (gcc -Os) often produce rather bad full-program performance. Cache and TLB pressure are important topics but in my experience it seems to have been the case that hot/cold code splitting and other layout optimizations overcome the problem, and text on hugepages helps with iTLB miss rate. The best full-system performance I've been able to get on complex C++ servers has always been with really large outputs, 100s of MB of .text.
bogomipz 7y ago
The author states: >"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?

160 points by lelf 7y ago

deleted 7y ago

[deleted]

Related there is this old (old enough to be postscript, not PDF!) paper that compared register allocation on the usual 8 registers on Intel vs 32 virtual register that are then allocated to the 8 available registers. Doing the latter created faster code, suggesting that the CPU's register renaming is not as good as it could be. This was on a Pentium 2, so it might be that the results don't hold any more. It's also been at least a decade since I read this paper in detail so I might have remembered it wrong! http://www.smlnj.org/compiler-notes/k32.ps http://www.smlnj.org/compiler-notes/k32.ps

vardump 7y ago
Pentium 2 is almost 23 years old now. Some things might have changed a bit by now. :-)
pizlonator 7y ago
That's just saying that having more registers is better. That's definitely true if you only have 8. It's also not related to the key point of the original post: whether selecting different registers - in situations where doing so has no effect on spilling - could change performance.
- noelwelsh 7y ago
  You've misunderstood...read the paper for the details. It's not that more registers are better, it's that they did a better job than the CPU at register allocation (Pentium 2 had 40 registers IIRC). Also note that my post starts with the word "related", indicating that I'm commenting on a similar, but identical, issue.
  - wahern 7y ago
    Modern CPUs are like miniature JIT compilers.[1] They do wondrous things but I guess it shouldn't be surprising that in critical sections static compilation with a more global perspective can often make better decisions.[2] I would think that would be even more true today than during the Pentium II era, or at least as true. Both the state-of-the-art and the resources that can be devoted to such optimizations have continued to progress for both static and JIT compilation. [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 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.
    - cwzwarich 7y ago
      The extent to which modern CPUs are “like JIT compilers” is highly overrated by SW people. 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.
      - wahern 7y ago
        I also had in mind branch prediction units, and stuff like Intel's TSX. I assume these days the former bleeds into many other parts of the architecture, including the microcode; I'm certain (but can't say authoritatively) that the latter does. 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.
sadiq 7y ago
That's an interesting paper. For anyone on mobile who wants a PDF: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.863&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11...
anonsivalley652 7y ago
In the yee old'en days, only the length of opcode would make much of a difference or if it were implemented in a slightly different microcode path which would change the number of micro-ops slightly. Reg aliasing/renaming I think would make transfers between registers very fast unless a data hazard existed in subsequent/branch-predicted instructions (scheduling the "liveness" in the register file across the pipeline stages so it doesn't mess anything up). PS: Hehe.. anyone remember U/V pipe optimization? :) Michael Abrash books on assembly and 3D game programming, and assembly profiling on real hardware FTW.
- bogomipz 7y ago
  What is the 'scheduling the "liveness" in the register file across the pipeline stages'? Is this part of garbage collecting or detecting when a register can be reallocated?

acqq 7y ago

> According to the Intel optimization manual, using EBP, RBP, or R13 as the base address will make LEA slower. 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.

BeeOnRope 7y ago
It's not clear and you are not correct in this case – at least per the actual behavior, and I assume the intent of the manual (but of course we can argue about whether the item is well-written). 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).
- acqq 7y ago
  No, it's clear, especially if you'd know what it is about (BP is used in various calling conventions, so it has to be fast in common cases). That the list there is OR doesn't make every LEA which uses BP slow, as the article claims. 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"
  - BeeOnRope 7y ago

floatingatoll 7y ago

On Intel x86 CPUs; after the intro paragraphs: > Note, the rest of the article only talks about Intel micro-architectures

deleted 7y ago
[deleted]

lmilcin 7y ago

No numbers. I appreciate good theory, but it is much more useful when it was a backed by some experiments.

BeeOnRope 7y ago
Indeed, the article has several inaccuracies and lots of obsolete information, so it's a shame the author didn't try this stuff because they would have found a different story.
djmips 7y ago
Just saying x86 was a red flag because that encompasses such a huge swath of architectures and timeframes. No mention of AMD.

pechay 7y ago

1. MOV AL, BYTE PTR [RDI] 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

vardump 7y ago
Yeah. Second one would be shorter as XOR EBX, EBX, because EAX is always zero after that AND.

pcwalton 7y ago

This article does a great job answering the question "why don't compilers use AH/AL/etc. like DOS compilers did in the good old days?" Short answer: it causes unnecessary dependencies because the other parts of the register are preserved. 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!

acqq 7y ago
> 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.
- Dylan16807 7y ago
  I don't know how anyone can look at the list of one-byte opcodes and conclude that x86 isn't a mess. 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.
  - pcwalton 7y ago
    > I don't know how anyone can look at the list of one-byte opcodes and conclude that x86 isn't a mess. Or heck, even just the fact that real mode is still a thing.

f00zz 7y ago

Nice article, I learned something. Nitpick: MOVZX EAX, BYTE PTR [RDI] AND EAX, 0xFFFFFF00 MOV EBX, EAX // no partial register stall I think the author probably meant AND EAX, 0xFF. But the AND is redundant, as MOVZX is already zero-extending the byte. The snippet immediately above needs the AND, though.

bonzini 7y ago
I think he meant MOVZX EBX, [RDI] + AND EAX, 0xFFFFFF00 + OR EAX, EBX. The sequence would be equivalent to MOV AL, [RDI].

rwallace 7y ago

> According to the Intel optimization manual, using EBP, RBP, or R13 as the base address will make LEA slower. Now that's odd. What is special about those registers, that code using them can end up slower than the others?

magicalhippo 7y ago
The post explains it. LEA without those registers used as base can be computed in the address generation unit, which is separate from the regular arithmetic unit(s). 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] With normal arithmetic that would be three instructions that could not be done in parallel, but with LEA it's done in a single clock cycle[1]. More details here[2]. For some reason, the AGU seems incapable of dealing with those registers as base I guess. [1]: https://gmplib.org/~tege/x86-timing.pdf https://gmplib.org/~tege/x86-timing.pdf [2]: http://www.nynaeve.net/?p=64 http://www.nynaeve.net/?p=64 (point 3)
- BeeOnRope 7y ago
  The article is wrong, AGU hasn't been used for LEA on mainstream Intel CPUs in a decade at least. 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.
  - magicalhippo 7y ago
    Alrighty then, time for me to never do any x86 asm programming again I see :) Thanks for the detailed correction.

userbinator 7y ago

We can see using ADD with EAX as dst register is 1-byte short than another, so that has higher code density and better cache-friendly. 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.

thedance 7y ago
I appreciate the sentiment but compilers optimizing size (gcc -Os) often produce rather bad full-program performance. Cache and TLB pressure are important topics but in my experience it seems to have been the case that hot/cold code splitting and other layout optimizations overcome the problem, and text on hugepages helps with iTLB miss rate. The best full-system performance I've been able to get on complex C++ servers has always been with really large outputs, 100s of MB of .text.

bogomipz 7y ago

The author states: >"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?