Th Topic: compressed code

Topic: compressed code

topics > computer science > programming > Group: code generation

Topic:
compressed data
Topic:
data compression algorithms
Topic:
incremental execution
Topic:
intermediate representation of code
Topic:
interpreter
Topic:
just-in-time compilation
Topic:
load-time code generation
Topic:
mobile code
Topic:
packed data
Topic:
threaded code
Topic:
type reflection and introspection

Summary

The internal structure of computer code allows custom compression algorithms.
Interpreted code is usually more compact that native code. The bytes codes may be compressed further.
Compression is particularly useful for mobile code and embedded devices.
Examples include split-stream encoding, echo compression, dictionary encoding, instruction cache compression, grammar-based compression. (cbb 2/07)

Subtopic: reducing code size

Quote: survey article on code-size reduction methods from 1984 to 2002 [»beszA9_2003]
Quote: use contours to compress identifiers during interpretation; each entry in contour includes all information to access variable [»debaEH_1990]
Quote: wire-format code is decompressed or compiled before use [»ernsJ6_1997]

Subtopic: echo compression

Quote: simple, 30% compression of bytecodes allowing direct interpretation; echo instruction executes previous instructions [»frasCW4_2006]

Subtopic: split-stream encoding

Quote: 24% smaller compressed code by separating an intermediate representation into streams [»frasCW5_1999]
Quote: split-stream dictionary compression compresses code to half size with fast decompression; only 27% overhead for JIT translation [»luccS6_2000]
Quote: split-stream dictionary compression constructs a dictionary with each instruction and each repeated, 2-4 instruction sequence [»luccS6_2000]
Quote: SSD includes an input-specific dictionary; better than BRISC if at least 30KByte [»luccS6_2000]
Quote: large program frequently reuse small sequences of instructions
Quote: compressed code five-fold: patternize literals from tree-structured code, separate streams for patterns and literal operands, move-to-front, gzip
Quote: compress code by separating opcodes from operands; otherwise byte-stream compression will miss correlations among sub-byte components [»ernsJ6_1997]

Subtopic: instruction cache compression

Quote: decompress code words into the hardware instruction cache for practical, 70% software compression [»lefuC1_2000]

Subtopic: dictionary encoding

Quote: method to compress assembly code; includes procedural abstraction(repeated codes), cross-jumping (common tails), and threaded code [»frasCW6_1984]
Quote: compress assembly code by identifying common substrings via suffix trees; 7% compression on average [»frasCW6_1984]
Quote: compress a program with a semantic-dictionary encoding; uses a symbol table and an abstract syntax-tree [»franM3_1994]

Subtopic: grammar-based compression

Quote: executable, compressed programs by encoding program as a list of grammar rules that generate basic blocks; 29-42% compression, 140x slower [»evanWS8_2003]
Quote: compressed bytecodes using profiled grammar rewriting; lcc 2/3 smaller with 11KB larger interpreter [»evanWS6_2001]

Related Topics

Topic: compressed data (16 items)
Topic: data compression algorithms (53 items)
Topic: incremental execution (22 items)
Topic: intermediate representation of code (31 items)
Topic: interpreter (59 items)
Topic: just-in-time compilation (20 items)
Topic: load-time code generation (13 items)
Topic: mobile code (14 items)
Topic: packed data (11 items)
Topic: threaded code (18 items)
Topic: type reflection and introspection
(28 items)