Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Registers Are Fast and RAM Is Slow

mikeash.com

Post reply on HN
Print view View original

61–70 of 92 posts

Re: Why Registers Are Fast and RAM Is Slow

#61

Post by Symmetry »

joosters wrote: post #37

Has anyone done a study on the optimal number of registers to have? The website answers the register question well, but leads to a further question: If registers are so great, why stick with just 16/32/64/n registers? Why not have more? After all, x86-64 and ARM64 decided that having more suited them. In the end it must come down to a compromise, with the downsides of having more registers possibly being some of the…

Most high performance CPUs will have ~100 physical registers or so, possibly divided up in multiple segments.

But abstracting those you have your architectural registers that are presented by your ISA, and the CPU uses register renaming to map those onto the physical registers.

The tradeoffs involving ISA registers are more intense. You have to load and store all of them on thread swaps, but that's pretty tivial. More importantly the bits you have to use to specify which register you're using are bits that you're paying in every single instruction you have, increasing the size of your executable and the pressure on your caches.

Different sorts of architectures have their sweet spots at different places. In order processors doing lots of matrix math and such benefit from lots of architectural registers, the Itanium had 128 integer and 128 floating point registers and that was the right amount for a VLIW architecture with it's features. Modern GPUs are similar.

On the other hand, your typical OoO CPU will have either 16 or 32 registers you can address at a time, and that seems to be close to optimal. It's hard to say since instructions come in discrete chunks and your number of registers has to be a power of 2 as a practical matter.

Re: Why Registers Are Fast and RAM Is Slow

#62

Post by raverbashing »

demallien wrote: post #56
yan wrote: post #8

For a way more detailed look at memory architectures and implementation, check out Ulrich Drepper's classic paper "What Every Programmer Should Know About Memory"[1] [1] http://www.akkadia.org/drepper/cpumemory.pdf

Or on a more light-hearted note: http://folklore.org/StoryView.py?project=Macintosh&story=Sou... Which just goes to show, hitting memory is a Bad Thing(tm) even when you're running on a slow(from today's perspective) processor like a 68000.

Very impressive

Doing 22kHz generation on a Macintosh is very close to the limit

Re: Why Registers Are Fast and RAM Is Slow

#63

Post by sliverstorm »

joosters wrote: post #42
codex wrote: post #38

Earlier quoted context omitted.

Fundamentally, having more registers increases the speed of light delays in accessing the register. If it did not, we would just operate on main memory itself. However, two few registers and you lose the ability to perform complex computations efficiently. So I believe it is, indeed, a compromise between speed and a need to maintain scratch state. I would be surprised if Intel and AMD didn't constantly run simulation…

That's definitely another factor but I suspect it isn't the limiting factor. Sure, design a chip with a million registers and you'll end up constructing them like RAM. But with orders-of-magnitude fewer registers, 16 or 32 or whatever, the size of the register banks on the CPU can't be that significant to incur speed-of-light style delays, surely?

WITH 16x fewer registers, that equates to about 1 chip's worth of registers (remember a stick of DRAM often has 8-16 individual chips on it). While this is already clearly a huge problem, consider additionally that DRAM is made with trench capacitors, unlike SRAM. DRAM is dramatically slower and more dense than SRAM. So we either sacrifice speed, or bloat our one-chip's-worth of area by a few factors, say x4-8.

Then there's practicalities like sense amp design. Large register arrays are not read in a digital fashion, and current L2 and L3 sizes already press their sense amps to their limits. DRAM also uses sense amps, but the amps are again slower and larger.

http://en.wikipedia.org/wiki/Sense_amplifier

Re: Why Registers Are Fast and RAM Is Slow

#64

Post by knappador »

eksith wrote: post #12

This part stood out : "The ideal of 3-4 instructions per clock cycle can only be achieved in code that has a lot of independent instructions." And a bit later : "3.Modern CPUs do crazy things internally and will happily execute your instruction stream in an order that's wildly different from how it appears in the code." This may potentially explain why a smaller executable isn't necessarily faster when execut ing . I…

In some ways, the actual execution of code is opaque to compilers. Modern x86 processors further divide their instructions into op-codes in the instruction translation units. AMD and Intel both have their approaches to this internal instruction set deeply ingrained into every CPU since perhaps K7 for AMD and Pentium Pro for Intel. Pentium M and later the Core architecture contained op-code fusing where instead of just rearranging op-codes, the op-codes were combined into composite op-codes that could be executed in one step. The opcode fusing + out-of-order execution basically makes the CPU act like a compiler internally for binary. It's a like a JIT run-time for binary that's implemented in hardware.

As far as executable size and performance, compiling with -Os in GCC will occasionally yield a performance increase that might even change across CPU's and architectures as the memory sub-systems hit a good rhythm or there are less misses overall. Usually smaller is better for this. -O3 will occasionally unroll gigantic loops, while using compiler directed optimization to analyze which parts of a binary can benefit overall execution from unrolling vs less misses with smaller executable size can yield even better agreement between memory subsystem performance and execution speed.

Microarchitectures like MIPS have further blind alleys such as branch-delay slots that will finish execution even if a branch instruction -before- the slots is taken. This is an out-of-order program, but putting the burden on the compiler instead of implementing the reordering in hardware actually became a nuisance because the architecture couldn't change how it expected instructions without breaking binary compatibility and the compiler wouldn't have been able to tweak for different CPU's without a fat-binary approach.

Re: Why Registers Are Fast and RAM Is Slow

#65

Post by rdtsc »

ajuc wrote: post #40
codex wrote: post #36

Earlier quoted context omitted.

Usually the implicit assumption with O notation is that n may go to infinity. Time and the number of operations are equivalent here: as proof, just define the operation as "move an information-carrying photon a tiny distance episilon". That must take a finite amount of time, as the speed of light is finite, and the number of those operations must increase with the number of randomly accessed elements you're working w…

Algorithms have the same complexity no matter the machine: bubble sort is O(n^2) no matter if you use C64 or a new PC. That's why it uses operations instead of time - to be able to compare algorithms independently of machines it runs on. Operations are usually defined as addition or multiplication or comparison. Moving a photon by epsilon isn't a valid operation in any architecture I'm aware of. Even if we use moving…

> That's why it uses operations instead of time - to be able to compare algorithms independently of machines it runs on.

Splitting hairs here. You can talk about operations or time. Same thing as operations are sequential. One operation follows another. You can count them when you are done to get to total and the total is also referred to as the "time" in this context.

> I've seen ever implemented was incorrect - most use integers or floats or doubles so their input space is very limited

So are we talking about specific hardware here or not. I thought we weren't. There ambiguity and discussion point is there because one can define what they consider is a "constant" operation. You can say it is a hypothetical von neuman architecture machine and these operations (op1, op2, ....) take a constant time. Now we compare two algorithms and see how they do.

Re: Why Registers Are Fast and RAM Is Slow

#66

Post by brigade »

joosters wrote: post #37

Has anyone done a study on the optimal number of registers to have? The website answers the register question well, but leads to a further question: If registers are so great, why stick with just 16/32/64/n registers? Why not have more? After all, x86-64 and ARM64 decided that having more suited them. In the end it must come down to a compromise, with the downsides of having more registers possibly being some of the…

The studies would vary over time because CPU design and bottle necks have changed. Early designs were of course limited by transistor count, now we have OoOe and physical registers are limited by muxers and latency (see the presentations by the mill CPU guy [1]

Saving registers in functions is mostly irrelevant - you only save what you'd use, so saving more means fewer spills within the function.

Saving on context switches (interrupts alone aren't a big deal) was indeed a problem back when AltiVec was designed, thus it has a special register to keep track of which registers need to be saved. In modern designs this is less of a problem, between higher frequencies, multiple cores, and the other effects of a context switch dominating (effective flush of l1 cache and predictors).

The interesting bits nowadays are that load/store is expensive power-wise, which was what ARM identified as the major motivation behind having 32 registers (fewer spills in functions) and OoOe designs.

[1] http://m.youtube.com/watch?v=QGw-cy0ylCc&desktop_uri=%2Fwatc...

Re: Why Registers Are Fast and RAM Is Slow

#67

Post by vilda »

joosters wrote: post #37

Has anyone done a study on the optimal number of registers to have? The website answers the register question well, but leads to a further question: If registers are so great, why stick with just 16/32/64/n registers? Why not have more? After all, x86-64 and ARM64 decided that having more suited them. In the end it must come down to a compromise, with the downsides of having more registers possibly being some of the…

Note that the actual number of registers is considerably different than the number of registers you can access through instruction set. They are used via register renaming and optimizations of complex instructions.

Re: Why Registers Are Fast and RAM Is Slow

#68

Post by joosters »

brigade wrote: post #66
joosters wrote: post #37

Has anyone done a study on the optimal number of registers to have? The website answers the register question well, but leads to a further question: If registers are so great, why stick with just 16/32/64/n registers? Why not have more? After all, x86-64 and ARM64 decided that having more suited them. In the end it must come down to a compromise, with the downsides of having more registers possibly being some of the…

The studies would vary over time because CPU design and bottle necks have changed. Early designs were of course limited by transistor count, now we have OoOe and physical registers are limited by muxers and latency (see the presentations by the mill CPU guy [1] Saving registers in functions is mostly irrelevant - you only save what you'd use, so saving more means fewer spills within the function. Saving on context sw…

Saving registers in functions is mostly irrelevant - you only save what you'd use, so saving more means fewer spills within the function.

Ah, but I'm sure that if you have more registers available, you'd use more registers. Up to a certain point. But what point? Just how many registers?

Re: Why Registers Are Fast and RAM Is Slow

#69

Post by joosters »

vilda wrote: post #67
joosters wrote: post #37

Has anyone done a study on the optimal number of registers to have? The website answers the register question well, but leads to a further question: If registers are so great, why stick with just 16/32/64/n registers? Why not have more? After all, x86-64 and ARM64 decided that having more suited them. In the end it must come down to a compromise, with the downsides of having more registers possibly being some of the…

Note that the actual number of registers is considerably different than the number of registers you can access through instruction set. They are used via register renaming and optimizations of complex instructions.

Yes. As other commentors have said, if you are doing out-of-order execution well, the CPU will have many more 'hidden' registers and do register renaming to use them. But this has an interesting interaction with compilers.

Say you have a simple function that is going to add 1 to a bunch of variables. In an ARM-like assembly code, this could be written as:

  LDR r1, [r0, #0]
  ADD r1, r1, #1
  STR r1, [r0, #0]
  LDR r1, [r0, #4]
  ADD r1, r1, #1
  STR r1, [r0, #4]
  LDR r1, [r0, #8]
  ADD r1, r1, #1
  STR r1, [r0, #8]
Now, if your CPU can do OoOE, it can spot that register r1 is used for three independent loads, adds and stores, and can internally use three different registers for them, allowing the operations to be done in parallel. But, equally, the compiler could have written the code as:

  LDR r1, [r0, #0]
  ADD r1, r1, #1
  STR r1, [r0, #0]
  LDR r2, [r0, #4]
  ADD r2, r2, #1
  STR r2, [r0, #4]
  LDR r3, [r0, #8]
  ADD r3, r3, #1
  STR r3, [r0, #8]
Compilers and register renaming are fighting each other. In traditional compiler writing, you try to minimise the register usage and output the first code listing. But if you have plenty of registers, you could output the second code instead, and let the CPU do parallel execution without the need for register renaming.

In other words, once you have enough 'real' registers does it get rid of the need for register renaming? Intel added it to their pentiums to improve existing x86 code, but I wonder if it has that much of a benefit with newer ISAs that have 'enough' registers and properly tuned compilers?

Re: Why Registers Are Fast and RAM Is Slow

#70

Post by brigade »

joosters wrote: post #68
brigade wrote: post #66

Earlier quoted context omitted.

The studies would vary over time because CPU design and bottle necks have changed. Early designs were of course limited by transistor count, now we have OoOe and physical registers are limited by muxers and latency (see the presentations by the mill CPU guy [1] Saving registers in functions is mostly irrelevant - you only save what you'd use, so saving more means fewer spills within the function. Saving on context sw…

Saving registers in functions is mostly irrelevant - you only save what you'd use, so saving more means fewer spills within the function. Ah, but I'm sure that if you have more registers available, you'd use more registers. Up to a certain point. But what point? Just how many registers?

No one uses more registers just to use more registers - in OoOe designs the main reason to use more registers is to reduce spilling and reloading. So in effect a compiler isn't going to use a register it has to save, unless in doing so it saves a spill+reload, which would result in the same number of load/store as without the additional register.

In-order designs have more reasons to use more registers, but again they aren't going to use more registers unless they gain something.

Post reply on HN