3 ms·

I don't get what you mean by "linear is too slow" -- if you want to decode n bits you need at least O(n) time. Decoding every potential alignment seems equally

• Veedrac 11y ago
  > if you want to decode n bits you need at least O(n) time This is hardware. There aren't branches, there are wires. Decoding those n bits can be constant time at the cost of quadratic "space" usage.
  • darkmighty 11y ago
    By quadratic you mean O(2^(2n)) physical space, right? By a naive approach (making decoding like a ROM memory), I still can't see how it's not at least linear on the number of bits even assuming simplifying things for circuit sizes.
    • Veedrac 11y ago
      > By quadratic you mean O(2^(2n)) Quadratic is O(n^2), not O(4^n). n is the number of bits. The bits are decoded in parallel, ergo. in constant time. There may be a linear step afterwards (eg. numbering each instruction result) but the actual decode happens in parallel. I'm a bit confused about why you think it's linear time. (I suppose technically it even has to be constant time, since the number of bits is capped at a low constant, but I suppose that's also besides the point.) It's not actually quite that simple, since it's actually a 3-phase decode and there is some interdependence. However, the point remains that shifting the read along one instruction at a time would be too slow and parallel decode is key to fixing that. I suppose you might instead be asking why it's not linear hardware space complexity (rather than quadratic); the answer to that is a little more subtle.