Dazo-org/zerovm — Issue #16: CompressedNEXE
Author: camuel
Created: 2011-11-30 16:17:45+00:00
State: open
Labels: DESIGN, FEATURE, MAJOR

Add NEXE compression support. NEXE are statically linked (because of newlib, general robustness, avoiding DLL-hell, avoiding scenario where NEXE is tested with one version of library and then is run at server with another version that it was never tested with and other various reasons) and so tend to be relatively large even for small programs, about 1 MB for hello-world equivalent program and it is expected to get larger as ZRT (zerovm standard runtime lib) grows. Another reason for compressible increased size is frequent padding in each 32 bytes of code.

Hence, the proposed feature of keeping all NEXEs always compressed.

In addition to conventional compression a pre-agreed shared dictionary/statistics could be helpful. All the libraries standard and common third-party ones can be used by compressor as pre-agreed shared dictionary between a compressor on client and decompressor on server side.

A naive implementation can go like this:

1. Client asks server for the dictionary, the dictionary is just a list of key-value pairs where key is MD5/SHA1 hash of the value and the value is actual recognized data.

2. Compressor scans NEXE for such recognized parts and breaks NEXE into chunks. All chunks are written into NEXE header. Recognized chunks contain just the positions within the file and the hash, unrecognized chunks are compressed with generic compression and contain in addition to compressed data just the positions where it should be inserted.

3. Decompressor opens NEXE file checks if it is compressed by looking for magic number and if it is then reads chunk table and builds the file, recognized chunks are inserted using dictionary and unrecognized chunks are inserted using chunk table.

It could be that generic compression is more efficient when done on whole file rather then individual chunks in the chunk table, however that will require two-pass decompression.

Decompression is straightforward but compressor is tricky to implement. If dictionary is large it can be resource intensive to check whether it contains any of recognized chunks. Heuristics and hints can be used to reduce search space, for example compressor can take hints of the ZRT version and with some insight into NEXE structure will quickly identify the ZRT library portions and code them, same regarding hinting other libraries. In anycase compression is something that is done only once for NEXE and decompression is frequent so making decompression fast should be the goal.