Adrian (a.delete@this.acm.org) on June 6, 2022 10:59 am wrote:
> Nevertheless, for any distribution of the instruction frequencies it is possible to make an
> optimal encoding resulting in a minimum program size, if the constraint of having an integer
> number of bits per instruction is no longer imposed, e.g. by using arithmetic coding.
>
>
> Of course, it is unlikely that the reduction of the program size achieved by accepting the length
> of the instruction to be any integer number of bits or any fractional number of bits, instead
> of being a multiple of 8 bits, is worth the increase in the complexity of the decoder.

Would it really be so complex? If the program code is split in, let's say, 128 bits chuncks containing a variable number of arithmetic encoded instructions, would the decoder really be much more complex than a x86 encoder? Multiple chuncks could be decoded in parallel, and the result stored in a uop cache, also, I would expect in each chuck only a small subset of registers being used multiple times, being very compressible.

But someone could also have codes for common instruction sequences, getting a benefit similar to arithmetic coding but much simpler to decode.