Berry bytecode compression

[s-hadinger]

This has been on my mind for some time...

Berry's bytecode code density is quite low, with each instruction encoded on 4 bytes. I would like to explore ways to reduce solidified code size. I tried to define a shorter instruction set in 2 or 3 bytes, but this would be too complex for the VM to handle it.

Next option would be to apply Huffman-like compression on bytecode, and decompress in RAM before running. We can keep around a small cache of uncompressed bytecode for code ran often.

Obviously I'm still missing metrics about potential savings.

Any thoughts?

[skiars]

If we use variable-length bytecodes, VM changes will be very large, and performance is also a risk point. In addition, register-based VM instructions generally require more parameters, which are different from stack-based VM, so the benefits of using variable-length instructions may be limited. As an example:

; addition of register-based VM
ADD  R0 R1 R2
;  addition of stack-based VM
PUSH value1
PUSH value 2
ADD ; pop two operand values and push one result value

So I think Huffman compression is a better choice.

[s-hadinger]

Thanks,(when I have time) I will gather metrics of my codebyte base to get typical frequencies of values to feed in Huffman compressor.

[s-hadinger]

I did some stats 4351 opcodes from solidified code in Tasmota.

Opcodes

Not surprisingly, there is an uneven distribution of opcodes as shown here:

Huffman should be quite effective here.

Registers

Below are the distribution for A, KB and KC separately. I didn't consider Bx, it is anyways captured in C where most values for Bx imply C being zero.

Register A

Looking closer, values 0..6 account for 10% of the values each, the remaining 30% is quickly decreasing for other values

Register KB

KB has also some strong concentration over a few value

Register KC

For KC, the value 0 covers 44% of values alone, probably because it is also the high part of Bx. Here again we should achieve pretty high compression

[skiars]

You mean, we can design efficient compression algorithms for bytecode format?

If this is feasible, I think bytecode files should also be considered.

[skiars]

We can even save RAM through compression. For some ultra-low-end devices, some performance may be sacrificed, but at least it is possible to support Berry.

[s-hadinger]

I wouldn't be too optimistic. On ultra-low-end devices memory will be a show stopper unless you have very limited structures in memory

[s-hadinger]

I was thinking of a just-in-time decompressor of bytecode. Before running bytecode, the function would be decompressed in RAM and this 'normal' copy of the code would be used by the VM. To avoid a too high performance impact, we could keep a cache of recent or often used code in memory.

This means a tradeoff of using less Flash but more memory.

[skiars]

Yes, I think these strategies can be considered.

[s-hadinger]

I have analyzed the distributions and here are the optimized patterns for RegA, RegB and RegC:

Each code has 000 as an escape pattern, i.e. the value is the following 8 or 9 bits.

RegA
Bits Code           Symbol
(3)  000               -- escape
(3)  001               3
(3)  010               4
(3)  011               5
(3)  100               6
(4)  1010              8
(5)  10110             9
(5)  10111             10
(4)  1100              0
(4)  1101              1
(4)  1110              2
(4)  1111              7

RegB
Bits Code           Symbol
(3)  000               -- escape
(3)  001               256
(2)  01                0
(5)  10001             257
(4)  1001              3
(3)  101               1
(3)  110               2
(5)  11100             4
(5)  11101             5
(5)  11110             6
(5)  11111             7

RegC
Bits Code          Symbol
(3)  000              -- escape
(4)  0010             1
(5)  00110            2
(5)  00111            3
(3)  011              256
(5)  01000            257
(5)  01001            258
(5)  01010            259
(5)  01011            4
(1)  1                0

[s-hadinger]

Here is the code I propose for opcodes, the escape sequence is 000+<6_bits> for instructions not in the list:

Bits Code    Value Symbol
   3 000          -- Escape
   3 001          31       CALL
   3 010          23       MOVE
   3 011          35       GETMET
   4 1000         32       RET
   4 1001         34       GETMBR
   4 1010         22       LDCONST
   4 1011         30       JMPF
   5 11000        0         ADD
   5 11001        7         EQ
   5 11010        36       SETMBR
   5 11011        46       GETNGBL
   5 11100        19       LDNIL
   5 11101        21       LDINT
   5 11110        24       GETGBL
   5 11111        28       JMP

Running this over 4300 instructions gives -25% compression on the opcode alone. I will run tests for A/KB/KC later

[s-hadinger]

Here is the final code for KC:

RegC
Bits Code          Symbol
(3)  000              -- escape
(3)  001              256
(4)  0100             1
(5)  01010            2
(5)  01011            3
(5)  01100            4
(5)  01101            257
(5)  01110            258
(5)  01111            259
(1)  1                0

Compression ratio is -41%

[s-hadinger]

Final code for KB:

RegB
Bits Code           Symbol
(3)  000               -- escape
(3)  001               256
(2)  01                0
(3)  100               1
(3)  101               2
(4)  1100              257
(4)  1101              3
(5)  11100             4
(5)  11101             5
(5)  11110             6
(5)  11111             7

Compression is -55%

[s-hadinger]

And Finally for A:

RegA
Bits Code           Symbol
(3)  000               -- escape
(3)  001               3
(3)  010               4
(3)  011               5
(3)  100               6
(4)  1010              0
(4)  1011              1
(4)  1010              2
(4)  1011              7
(4)  1110              8
(4)  1111              9

Achieving -43%

[s-hadinger]

Wrapping all numbers above, I finally get

Number of bits:
opcodes = 19622 vs 26106
A = 19844 vs 34808
B = 17647 vs 39159
C = 23157 vs 39159

Total = 80270 vs 139232

If we count in bytes, that makes 10034 bytes vs 17404 bytes, of -42%. Of course this should be a little worse because of the rounding to next byte within each function.

Now I need to check the size of the decompressor code, so that the benefits are still there.