Topic: compressed code

topics > computer science > programming > Group: code generation

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


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 up

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 up

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

Subtopic: split-stream encoding up

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 up

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

Subtopic: dictionary encoding up

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 up

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 up

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)

Updated barberCB 12/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.