6 ms·

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 regist

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.
      - MaxBarraclough 7y ago
        To maintain the JIT analogy: you've addressed instruction-selection, but what about register allocation (with register renaming)?
    - blattimwind 7y ago
      An alternative view (imho more accurate) on Tomasulo-like processors is that they essentially execute the data flow graph implied by a sliding window of instructions.
      - wahern 7y ago
        Sort of like a tracing JIT? I'm not trying to equivocate modern CPUs with the JVM, just emphasize the similarities as a way to understand and explain observed behaviors.
  - CalChris 7y ago
    The Pentium 2 was the first Intel microarchitecture with register renaming. It was the first out of order as well. Intel certainly got better with later microarchitectures. I'm trying to figure out if there is anything generally useful for now in these papers.
    - pansa2 7y ago
      > The Pentium 2 was the first Intel microarchitecture with register renaming. It was the first out of order as well. Wasn’t that the Pentium Pro?
      - CalChris 7y ago
        I was reading Agner and he lumped them all together. But you might be right. DWIW, tick tock didn’t start until 2007.
      - gpderetta 7y ago
        Yes. PentiumII was basically the Pentium pro with the MMX extensions and some minor improvements for desktop computers.
    - FrankBooth 7y ago
      No. Pentium Pro in 1995 was the first Intel x86 with register renaming.
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?

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.
    - MaxBarraclough 7y ago
      To maintain the JIT analogy: you've addressed instruction-selection, but what about register allocation (with register renaming)?
  - blattimwind 7y ago
    An alternative view (imho more accurate) on Tomasulo-like processors is that they essentially execute the data flow graph implied by a sliding window of instructions.
    - wahern 7y ago
      Sort of like a tracing JIT? I'm not trying to equivocate modern CPUs with the JVM, just emphasize the similarities as a way to understand and explain observed behaviors.
- CalChris 7y ago
  The Pentium 2 was the first Intel microarchitecture with register renaming. It was the first out of order as well. Intel certainly got better with later microarchitectures. I'm trying to figure out if there is anything generally useful for now in these papers.
  - pansa2 7y ago
    > The Pentium 2 was the first Intel microarchitecture with register renaming. It was the first out of order as well. Wasn’t that the Pentium Pro?
    - CalChris 7y ago
      I was reading Agner and he lumped them all together. But you might be right. DWIW, tick tock didn’t start until 2007.
    - gpderetta 7y ago
      Yes. PentiumII was basically the Pentium pro with the MMX extensions and some minor improvements for desktop computers.
  - FrankBooth 7y ago
    No. Pentium Pro in 1995 was the first Intel x86 with register renaming.

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?