4 ms·

> The big advantage that RISC has these days is that fixed width instructions are easy on the decoder. One thing that I've wondered is how much more efforts ar

> The big advantage that RISC has these days is that fixed width instructions are easy on the decoder. One thing that I've wondered is how much more efforts are needed to decode variable-width instructions. Decoding itself sounds fairly easy (but frankly I don't know any details), to the point that the amount of time needed for loading/storing/calculating overwhelms that of decoding. But decoding should happen extremely fast to fill the pipeline, so the speed might still matter. Can decoding instructions be an actual bottleneck?

cesarb 10y ago
> Can decoding instructions be an actual bottleneck? Yes. We have processors which can execute 4 or more instructions in parallel (if I'm reading http://www.anandtech.com/show/6355/intels-haswell-architecture/8 http://www.anandtech.com/show/6355/intels-haswell-architectu... right, the processor I'm using to type this message can start the execution of up to 8 microinstructions in parallel). You need to decode the instructions fast enough to keep up. Since the clock is the same, you basically need several decoders in parallel. But with variable-length instructions, you have to know the length of the first instruction so the second decoder knows where to start; you have to know the length of both instructions so the third decoder knows where to start; and so on. The x86 architecture is a worst-case of a variable-length architecture: take a look at http://wiki.osdev.org/X86-64_Instruction_Encoding http://wiki.osdev.org/X86-64_Instruction_Encoding and think how you would determine the length of an arbitrary instruction. High-performance x86 implementations have to do all kinds of crazy tricks. An extra pipeline stage solely to figure out the instruction lengths (see http://www.anandtech.com/show/6355/intels-haswell-architecture/6 http://www.anandtech.com/show/6355/intels-haswell-architectu...), extra tags in the instruction cache to mark the instruction boundaries, decoding the instruction lengths while loading the instruction cache, caching already decoded instructions, and so on. Contrast this with for instance RISC-V with the compressed instructions extension, where you have to examine just two bits on each instruction to figure out if it's a 32-bit or a 16-bit instruction. I'd have to look up the encoding for Thumb-2, but I'd expect it to be something equally simple. Make it simple enough, and you might be able to split the instructions and decode them in the same pipeline stage.
- userbinator 10y ago
  The x86 architecture is a worst-case of a variable-length architecture I'm guessing you haven't seen VAX. The first byte isn't even organised in any discernable pattern so there are both rare and very common instructions there, and operands are specified using a very flexible system that makes length decoding far more difficult than x86. In contrast, x86 has a mostly consistent 2-3-3 octal-based encoding, and having the first 2-3 bytes is usually enough to decode the instruction's length: http://reocities.com/SiliconValley/heights/7052/opcode.txt http://reocities.com/SiliconValley/heights/7052/opcode.txt
  - spc476 10y ago
    The VAX is an interesting case. While it's CISC, the instruction set is, oddly enough, very regular with operands following a common structure. Each operand has an initial byte describing the location, plus some additional bytes for displacements and indexing. Aside from the CASE statement (yes, the VAX has a table jump instruction) that can be (if I calculated correctly) up to 65,558 bytes in size, the next longest instruction are the six-operand ones that can be (again, if I calculated correctly) 43 bytes in size. Two operand register-to-register operations (and some indexed-register operations) take 3 bytes (1 for opcode, one for each register). Once you get used to it, it's pretty easy to read the actual binary code.
dbcurtis 10y ago
OH, my, yes, it can become a bottleneck. Disclaimer: It has been a good many years since I was privy to the innards of an X86. In the X86, it is possible for an instruction to be from 1 to 15 bytes long. (Maybe more today? It was 15 when I cared.) All you can tell from looking at the first byte is that it is either one byte longer than one byte. All you can tell from the 2nd byte is that it is either 2 bytes or longer than 2 bytes, and so on. When you walk all the way out to the 15th byte, you might find a MOD/RM field, which may contain invalid combinations. Finally you have enough information to raise (or not) the illegal instruction exception. That is one very nasty equation. Just one example of how variable instructions can become annoying to a logic designer. OTOH, some machines are very regular in how instruction length is specified -- in IBM 370 code, for instance, you can look at the first 2 bits and know the instruction width. X86 is an example of organic accumulation of features over time leading to a large collection of special cases.
- userbinator 10y ago
  The majority are below 4 bytes though, and ModRMs are either the 2nd or 3rd (in case of 0F escape or other prefix) byte. The 15-byte limit still applies, and is very rarely approached. As I understand it, modern x86 decoders can handle (multiple of) the smaller instructions in one cycle, while longer ones take a cycle or two more.
  - Animats 10y ago
    Intel and AMD approach this differently. Intel decodes a few instructions ahead of execution, and sometimes decodes speculatively. AMD at one time was expanding an entire cache line to fixed length instructions and executing the decoded form. X86 allows you to store into code, even immediately ahead of execution. This made sense in the 1970s when Harry Pyle designed the instruction set and CPUs were slower than memory. Superscaler CPUs have to support this. But, since almost nobody does that any more, they don't do so efficiently. Storing into code near execution causes an exception event, flushing all the superscalar lookahead and backing up to just before the instruction doing the store into code. Then the code gets modified, and the pipeline reloads, having lost tens to hundreds of cycles.
daurnimator 10y ago
LuaJIT recently gained an x86 instruction length decoder. Check it out: https://github.com/LuaJIT/LuaJIT/commit/73680a5fc760cb39760e4bbfce1166ce75de237f https://github.com/LuaJIT/LuaJIT/commit/73680a5fc760cb39760e...
- versteegen 10y ago
  Wow, I'm surprised that that's faster than the old byte-wise scanning of the instruction stream, and doubly surprised if the benefit isn't negated by the extra cache pollution. Actually, it's a lot simpler than I expected!
  - daurnimator 10y ago
    It's probably not; but it does fix a bug where bytes got misinterpreted. See http://www.freelists.org/post/luajit/Random-failures-in-compiled-code http://www.freelists.org/post/luajit/Random-failures-in-comp...
    - versteegen 10y ago
      I should have thought of that... of course it's easy to see the code was probably wrong in hindsight. Thanks for the explanation.
Symmetry 10y ago
Yes, it's certainly a concern. There are ways to decode lots of instructions at once in a clock cycle but they take lots of extra transistors and more power. "Lots" here is on the order of 5% or so of the power budget compared to an ISA with better encoding so it's not a decisive advantage but it's something you notice as a designer. And when balancing a CPU core you really want to make the front end wider than your execution resources would require so that you recover from branch mispredicts quickly and refill your various OoO buffers fast. x86 processors tend to do this less than, e.g., POWER because x86 decode is expensive.
- thechao 10y ago
  5%?! This isn't 2006, it's 2016. Decode is annoying, but it's a drop in the ocean compared to lighting up the memory stack.

cesarb 10y ago

> Can decoding instructions be an actual bottleneck? Yes. We have processors which can execute 4 or more instructions in parallel (if I'm reading http://www.anandtech.com/show/6355/intels-haswell-architecture/8 http://www.anandtech.com/show/6355/intels-haswell-architectu... right, the processor I'm using to type this message can start the execution of up to 8 microinstructions in parallel). You need to decode the instructions fast enough to keep up. Since the clock is the same, you basically need several decoders in parallel. But with variable-length instructions, you have to know the length of the first instruction so the second decoder knows where to start; you have to know the length of both instructions so the third decoder knows where to start; and so on. The x86 architecture is a worst-case of a variable-length architecture: take a look at http://wiki.osdev.org/X86-64_Instruction_Encoding http://wiki.osdev.org/X86-64_Instruction_Encoding and think how you would determine the length of an arbitrary instruction. High-performance x86 implementations have to do all kinds of crazy tricks. An extra pipeline stage solely to figure out the instruction lengths (see http://www.anandtech.com/show/6355/intels-haswell-architecture/6 http://www.anandtech.com/show/6355/intels-haswell-architectu...), extra tags in the instruction cache to mark the instruction boundaries, decoding the instruction lengths while loading the instruction cache, caching already decoded instructions, and so on. Contrast this with for instance RISC-V with the compressed instructions extension, where you have to examine just two bits on each instruction to figure out if it's a 32-bit or a 16-bit instruction. I'd have to look up the encoding for Thumb-2, but I'd expect it to be something equally simple. Make it simple enough, and you might be able to split the instructions and decode them in the same pipeline stage.

userbinator 10y ago
The x86 architecture is a worst-case of a variable-length architecture I'm guessing you haven't seen VAX. The first byte isn't even organised in any discernable pattern so there are both rare and very common instructions there, and operands are specified using a very flexible system that makes length decoding far more difficult than x86. In contrast, x86 has a mostly consistent 2-3-3 octal-based encoding, and having the first 2-3 bytes is usually enough to decode the instruction's length: http://reocities.com/SiliconValley/heights/7052/opcode.txt http://reocities.com/SiliconValley/heights/7052/opcode.txt
- spc476 10y ago
  The VAX is an interesting case. While it's CISC, the instruction set is, oddly enough, very regular with operands following a common structure. Each operand has an initial byte describing the location, plus some additional bytes for displacements and indexing. Aside from the CASE statement (yes, the VAX has a table jump instruction) that can be (if I calculated correctly) up to 65,558 bytes in size, the next longest instruction are the six-operand ones that can be (again, if I calculated correctly) 43 bytes in size. Two operand register-to-register operations (and some indexed-register operations) take 3 bytes (1 for opcode, one for each register). Once you get used to it, it's pretty easy to read the actual binary code.

dbcurtis 10y ago

OH, my, yes, it can become a bottleneck. Disclaimer: It has been a good many years since I was privy to the innards of an X86. In the X86, it is possible for an instruction to be from 1 to 15 bytes long. (Maybe more today? It was 15 when I cared.) All you can tell from looking at the first byte is that it is either one byte longer than one byte. All you can tell from the 2nd byte is that it is either 2 bytes or longer than 2 bytes, and so on. When you walk all the way out to the 15th byte, you might find a MOD/RM field, which may contain invalid combinations. Finally you have enough information to raise (or not) the illegal instruction exception. That is one very nasty equation. Just one example of how variable instructions can become annoying to a logic designer. OTOH, some machines are very regular in how instruction length is specified -- in IBM 370 code, for instance, you can look at the first 2 bits and know the instruction width. X86 is an example of organic accumulation of features over time leading to a large collection of special cases.

userbinator 10y ago
The majority are below 4 bytes though, and ModRMs are either the 2nd or 3rd (in case of 0F escape or other prefix) byte. The 15-byte limit still applies, and is very rarely approached. As I understand it, modern x86 decoders can handle (multiple of) the smaller instructions in one cycle, while longer ones take a cycle or two more.
- Animats 10y ago
  Intel and AMD approach this differently. Intel decodes a few instructions ahead of execution, and sometimes decodes speculatively. AMD at one time was expanding an entire cache line to fixed length instructions and executing the decoded form. X86 allows you to store into code, even immediately ahead of execution. This made sense in the 1970s when Harry Pyle designed the instruction set and CPUs were slower than memory. Superscaler CPUs have to support this. But, since almost nobody does that any more, they don't do so efficiently. Storing into code near execution causes an exception event, flushing all the superscalar lookahead and backing up to just before the instruction doing the store into code. Then the code gets modified, and the pipeline reloads, having lost tens to hundreds of cycles.

daurnimator 10y ago

LuaJIT recently gained an x86 instruction length decoder. Check it out: https://github.com/LuaJIT/LuaJIT/commit/73680a5fc760cb39760e4bbfce1166ce75de237f https://github.com/LuaJIT/LuaJIT/commit/73680a5fc760cb39760e...

versteegen 10y ago
Wow, I'm surprised that that's faster than the old byte-wise scanning of the instruction stream, and doubly surprised if the benefit isn't negated by the extra cache pollution. Actually, it's a lot simpler than I expected!
- daurnimator 10y ago
  It's probably not; but it does fix a bug where bytes got misinterpreted. See http://www.freelists.org/post/luajit/Random-failures-in-compiled-code http://www.freelists.org/post/luajit/Random-failures-in-comp...
  - versteegen 10y ago
    I should have thought of that... of course it's easy to see the code was probably wrong in hindsight. Thanks for the explanation.

Symmetry 10y ago

Yes, it's certainly a concern. There are ways to decode lots of instructions at once in a clock cycle but they take lots of extra transistors and more power. "Lots" here is on the order of 5% or so of the power budget compared to an ISA with better encoding so it's not a decisive advantage but it's something you notice as a designer. And when balancing a CPU core you really want to make the front end wider than your execution resources would require so that you recover from branch mispredicts quickly and refill your various OoO buffers fast. x86 processors tend to do this less than, e.g., POWER because x86 decode is expensive.

thechao 10y ago
5%?! This isn't 2006, it's 2016. Decode is annoying, but it's a drop in the ocean compared to lighting up the memory stack.