It's done in hardware so it's cheap (2012) | Hacker News Reader

It's done in hardware so it's cheap (2012)

yosefk.com

93 pointstodsacerdoti40 comments

The idea that processors are so complex because of C is one of the more persistent stories on HN, and I have to wonder why. It's easy to find looking at publications from the time that the 68000 and 8086 were marketed with Pascal or PL/M. We would have gotten a similar model of execution anyway even if C hadn't eaten the world.

The 8086 couldn't properly run C unless you were willing to limit yourself to 64KB (or three times that, if separating code, data and stack didn't hurt your application). To use the full address space you had to use non standard extensions such as "near pointers" and "far pointers" (Microsoft) or "@" as an alternative to "*" but for the ES register (QNX). On the other hand, the addressing modes using the frame pointer were really great for Pascal. Segments didn't bother Pascal at all and even on the 68000 based Mac, which had a C friendly flat address space, the system software pretended to have segments.

Growing segments from 64KB to 4GB was enough to allow the 386 to finally run the same C software as other processors like the VAX or 68000.

> And if ARM beats x86, it won't be, straightforwardly, "because RISC is better" – x86 will have lost for business reasons, and it could have gone the other way for business reasons. But the fact that it will have lost to a RISC – that will be because RISC is technically better. That's why there's no CISC competitor to lose to.

Yosef must be using a different definition of RISC from Jim Keller, because in Jim’s interviews he says that modern ARM is essentially a CISC processor.

RISC vs CISC made a big difference when we had 100k-200k transistors to play with. That was a long time ago.

Today's machines aren't CISC or RISC internally - they're ginormous out-of-order execution engines doing stuff that really can't be expressed in a linear machine language, and if there's an overhead for CISC, it's a tiny additional amount of real estate per core. Note that this is not a constant factor - as the rest of the CPU gets more complex, any CISC-related overhead becomes a smaller and smaller fraction of the whole. You can probably take the same set of execution units, forwarding paths, branch predictors, etc. and slap several different ISAs over it - I've seen CPU architects show experiments where (for x86 and ARM at least) two chips with the same number and type of these internal features will perform the same regardless of the instruction set.

There are a lot of factors involved other than the now-tiny technical advantage of RISC. There's a strong business incentive for the largest CPU design team in the world (i.e. Intel) to continue to produce x86 CPUs, rather than switching to another ISA. (for that matter, they tried once, with Itanic^H^H^HItanium, and it didn't work out so well)

Ecosystem effects mean that CPUs with non-dominant ISAs incur a bunch of various costs for their users, because everything from software through hardware just gets harder when you're not on the dominant commodity platform. (don't get me started on my experience with some POWER9 machines over the last few years...) A non-x86 CPU that's marginally faster/$ than an x86 isn't good enough - it needs to be substantially faster before it's worth the expense of switching, plus some more just to be sure that things won't swing the other way far enough to force you to switch back and pay that price all over again.

Most of the other observations in the post are spot-on, though...

> You can probably take the same set of execution units, forwarding paths, branch predictors, etc. and slap several different ISAs over it - I've seen CPU architects show experiments where (for x86 and ARM at least) two chips with the same number and type of these internal features will perform the same regardless of the instruction set.

Isn’t this what Transmeta was trying to do back in the day? I remember they famously employed Linus Torvalds for a while, but I never learned anything about the technical details of their ISA front-ends.

Forgive me, it looks like I had mis-remembered, and Transmeta’s translation layers were mainly software?

It was purely software, but future developments of the idea (like NVIDIA Denver) wasn't purely software. However, the backend is necessarily tried to the ISA you are emulating (true for all of them, including SoftMachine). You need the data types to match (eg. Transmeta supported x87-style FP) to have any hope of performance. The universal machine is neither possible nor desirable (it would be inefficient).

These days the IMO most interesting ISA from a JIT point of view is WASM as it's the one that offers the most information (context) and the fewest constraints on the implementation.

The AM29000 is probably what you're thinking of. AMD turned it into the more well known x86 processor the K5 among other things.

Exactly. These days, the only remaining difference between RISCs and CISCs are simpler fixed size encodings and a load-store architecture.

And x86 is arguably a CISC layer on top of a RISC processor. I don’t think the divisions of the 90s any longer directly apply.

^this, there are more layers now, and it's all fairly RISC like at the bottom or so I'm told.

This is a bit of a myth: microcode is used a lot in x86, but a lot of it is for emulating obselete instructions. The vast majority of instructions on x86 are still directly implemented in the hardware (including such decidedly non-RISC instructions as 'take this register, multiply it by 4, add it to this other register, then load that address from memory and do a floating-point multiplication of it with this 3rd register and store the result there', all without any microcode). If anything the RISC side of the coin (ARM) has become much more CISC like over time.

Also not entirely true. All x86 instructions are translated into an internal microcode/uop format; only the "complex" ones use the "microcode ROM".

The execution units don't know what `01 C0` (add eax, eax) means; only the decoder does. The decoder turns those bytes into something like `eax := ADD_DSZ32(eax, eax)` that the execution unit understands.

For example, `01 01 00 00` (add [ecx], ebx) is probably translated by the PLAs into 3 uops similar to these:

    tmp0 := LOAD_DSZ32(ecx)
    tmp0 := ADD_DSZ32(tmp0, eax)
            STORE_DSZ32(ecx, tmp0)

But any operation requiring four or more uops (such as "complex addressing") would go to either the "long" decoders or the microcode ROM

Ok now I'm confused. Is it possible you are both correct but your understanding are from different points in time where microcode based ops have been used more over time? i.e would the GPs comment be correct for a specific, older generation of intel x86, and yours perhaps be more applicable to newer generations?

My understanding is: every x86 processor from Intel and AMD has been microcoded to an extent. The 8086 through the 808486 used a "horizontal microcode" PLA (like all microprocessors of the era), but when Intel introduced the first superscalar x86 processor, the P5, they switched to "vertical microcode". IIRC, that vertical microcode has always been based around "simple" decoder PLAs and a "complex" decoder ROM.

Horizontal microcode is the execution unit control lines being toggled directly by the PLA. Vertical microcode (of the P5 and up) is more in line with what people understand "microcode" to be, but it's still internal uops, never "raw" x86 instructions. The encoding of the actual uop can usually be roughly correlated with the external ISA encoding, but that's just to ease work on the decoder.

Realistically, with CISC, you'll always have a microcode sequencer of some sort. More broadly, short of a TTA, there's going to be a PLA somewhere.

[0]: https://en.wikipedia.org/wiki/Transport_triggered_architectu...

Thanks! Strangely I wouldn't have guessed the 8086 had anything resembling microcode, even though when I think about it there are obvious examples of earlier microcoded CPUs - My understanding is definitely too vague, I wasn't even aware of the distinction between horizontal and vertical, thanks for highlighting the depth of this to me.

Sure thing! The world of microarchitecture is really interesting IMO.

If you're referring to uops, that's closer to VLIW than RISC.

AFAIK the whole RISC vs CISC thing has always been more about the software-visible instruction set than the implementation.

why would uops similar to VLIW? because they are very large and potentially encode control bits for multiple execution units? I never thought of them like that, but it could be a reasonable way to view them.

It was definitely about the implementation in the beginning.

Micro-ops aren't RISC instructions, too complex. For instance, vfmadd132ps instruction loads 32 bytes from memory, multiplies by 8 FP32 numbers, adds to another 8 numbers - yet on most processors that instruction decodes into a single micro-op.

Isn't that, in itself, a condemnation of CISC? The instruction set is so complex that the CPU has to translate to microcode at runtime.

If the compiler could emit that microcode directly, it would be easier to optimize and the CPU wouldn't have the task of decoding and translating the CIS.

The counterargument is that RISC architectures end up needing to use compressed instruction formats (e.g. ARM Thumb) because their clean orthogonal instruction encoding is so inefficient (e.g. it wastes a lot of instruction cache). If you already need the compiler to output some compressed encoding that your processor is going to uncompress at runtime, well, why not keep that uncompressed format as an implementation detail that you can change in future models of your processor?

> their clean orthogonal instruction encoding is so inefficient (e.g. it wastes a lot of instruction cache)

Perhaps, although ARMv8 is fixed 4 bytes and x86-64 averages more than 4 bytes an instruction despite each x86 instruction mapping to more than 1.0 uops on average. Oops.

That doesn't really say anything about efficiency of coding, because you're missing the important component of how much work each instruction represents. If ARMv8 turns 'load, multiply, store' into 3 instructions of 4 bytes and x86 represents that as 1 5-byte instruction decoding to 1 uop, x86 is going to be winning on most counts (2x in terms of code density). Of course the reality is probably going to be closer than this, but your statements contain none of the information to actually make any determination one way or the other.

Watch the interviews with Jim Keller.

reduced instruction sets don’t have any advantage, because if I recall what he said correctly, decoding and translating are a very small part of the transistor and latency budget. Missed branch prediction, cache and memory access are what matters for a modern CPU. Fetching from main memory has a cost, just like fetching off spinning rust used to, so hoops are jumped through to avoid memory stalls.

Decoding instructions is ugly but a solved problem. As for scheduling instructions optimally, Itanium tried this, but they never achieved a “sufficiently smart compiler” to make full use of the microarchitectural pipelines and registers (and cache?). Even if they had, that code might make poor use of future CPUs, because more pipelines will be available for more instructions or retire some of them faster than expected.

Scheduling instructions optimally needs runtime information not available to compilers, even if they were correctly told the architectural generation.

But, yes, compilers rarely are told the right architectural generation to target.

High performance RISCs also have decoders and have the equivalent of uops internally as well. Their decoders are simpler than a CISC like x86, which has a very baroque encoding.

Still the claim that x86 implementations are RISC internally is not really true.

Having a translation layer means you can have a stable API that the compilers can target (the ISA) and then be able to make breaking changes to the microcode API every processor generation to improve performance.

Jim’s view of ARM being a CISC architecture is rather unconventional. The Wikipedia page literally describes it otherwise in the very first sentence [1]:

> ARM (stylised in lowercase as arm, formerly an acronym for Advanced RISC Machines and originally Acorn RISC Machine) is a family of reduced instruction set computer (RISC) instruction set architectures for computer processors, configured for various environments.

[1]: https://en.m.wikipedia.org/wiki/ARM_architecture_family

You are quoting the name of the company, who's name is 37 years old, not the current state of it's technology. It's true it was originally RISC, and is still somewhat RISC, but it's also true it's acquired many decidedly CISC instructions over the decades - is it CISC or RISC ? reality is not this simplistic, it's a bit of both, and I'm not qualified to judge how much of each.

The people arguing in the comments that indirection is free, or very cheap, made me chuckle. The thing about indirection is that it tends to compound. You're never just chasing pointers one level deep.

If it is only expensive if you do a lot of it, then it's cheap.

“It's done in hardware so it's cheap” (2012) - https://news.ycombinator.com/item?id=19340667 - March 2019 (38 comments)

"It’s done in hardware so it’s cheap" - https://news.ycombinator.com/item?id=4339024 - Aug 2012 (29 comments)

Thank you!

While it is nearly always true that implementing stuff in hardware doesn't help as much as software people would hope, there are interesting exceptions. The 1986 Smalltalk processor project from Canada, called Swamp, used the top two bits of the 32 bit word as a tag. If the bits were 00 or 11 then we had a 31 bit integer (which also happen to be valid 32 bit integers for addition and subtraction, no conversion needed), while 01 was an object pointer into the heap and 10 was a reference to the stack.

Deciding if a 32 bit value is an integer or not is awkward in software, which is why Smalltalk and similar VMs use other encodings. In hardware it is a single exclusive or gate.

> Deciding if a 32 bit value is an integer or not is awkward in software, which is why Smalltalk and similar VMs use other encodings.

Small integers (up to some small number of bits shorter than machine size) are stored as their value, everything else has other bits set to indicate a pointer, index into object space, or some other thing, is a very common dynamic language data representation in software VMs. XOR is cheap in softwate, too.

An architecture the author doesn't consider is the Haskell Reduceron.

https://yosefk.com/blog/high-level-cpu-follow-up.html:

"Reduceron is designed to run Haskell, and focuses on an optimization problem I wasn't even aware of, that of graph reduction. [...] I think I'll look into this whole business some more. Pure functional languages are a weak spot of mine; for now, I can only say three things for sure: (1) side effects are a huge source of bugs, (2) although they get in the way of optimizers, side effects are a poor man's number one source of optimizations, so living without them isn't easy, and (3) the Reduceron is a pretty cool project."

Reply on news.ycombinator.com