Features Download
From: Kragen Javier Sitaker <kragen <at> canonical.org>
Subject: choosing powerful primitives for a simplified computing system
Newsgroups: gmane.culture.people.kragen.thinking
Date: Monday 16th July 2012 07:37:01 UTC (over 4 years ago)
One of the basic principles of the [FONC/STEPS system] [STEPS] is that
you can reduce the overall complexity of software by choosing powerful
primitives that simplify many parts of a system.  OMeta is sort of their
poster child: a generic rewriting system powerful enough to write
simple, efficient parsers with, but also to write compiler optimizers
and code generators with.

[STEPS]: http://vpri.org/fonc_wiki/index.php/Glossary

Here are some candidates for other primitives which, in practice,
simplify other parts of a computing system by more than the complexity they

LZ77 obsoletes curses and other things

Using zlib to compress your data streams and files greatly reduces the
performance penalty for not optimizing your file formats and protocols
to reduce file and message size.  Here are some exmaples.

### curses ###

At the Barracas [hacklab][] tonight, I was talking about why curses, the
programming library, is useless today.  Curses goes to a lot of effort
to minimize the number of bytes sent to your terminal, because at 300 or
2400 or 9600 baud, redrawing an entire 80×24 screen would take 66 or 8
or 2 seconds.  So it sought the minimum amount of change to your screen
to get it to match its internal screen image.

[hacklab]: http://lab.hackcoop.com.ar/

Fast-forwarding to 2012, if I’m receiving those bytes over a
connection at all, they’re being sent over an SSH connection
compressed with zlib.  If you send the same screen image twice with
small differences, zlib will notice that you’re sending a blob of
bytes you’ve sent before, and just transmit a reference to the earlier
index in the bytestream where you sent those bytes before.  What’s
more, it will also compress runs of whitespace, words that were
mentioned before, things that were on previous screens, and so on.  It
actually does a much better job than curses at reducing the bandwidth

So basically all of the cleverness that went into the special-purpose
screen-update optimization algorithms in curses (and Emacs, and other
things) has been replaced by a more general-purpose algorithm that
actually works better.  It requires a bit more CPU, and can’t be
executed by a nonprogrammable terminal, but that’s okay.

(There’s a separate question of how important it is to conserve the
bandwidth of text login sessions when we have megabits instead of

### SNMP and BER in general are ad-hoc compression that doesn’t work ###

Similarly, it turns out that if you represent the contents of a
typical SNMP packet as simple ASCII text with explicit name-value
pairs (with short names), and then compress it with either zlib LZ77
or the LZW implementation in `compress`, it ends up about the same
length as the BER-represented format that SNMP actually uses.

The following [sample packet][] is 53 bytes in BER. 

[sample packet]: http://www.pccl.demon.co.uk/papers/snmpdecode.html

    302B            SEQUENCE (LEN = 43)
    0201 00                 Version 1
    0404 55544D43           Community = UTMC
    A320                    SetRequestPDU (context constructed 3) (Len =
    0204 023712FB                   REQID = 0X023712FB
    0201 00                         Error = NONE
    0201 00                         ErrIndex = 0
    3012                            SEQUENCE (LEN = 18)
    3010                                    SEQUENCE (LEN = 16)
    060B 512C010401010401010100                     OID =
    0201 01                                         Integer = 1

The following version is 45 bytes in ASCII; `compress` makes it 44 bytes,
`gzip -9c` makes it 54 bytes; `bzip2` makes it 79 bytes.


If we run it through a stupid expansion phase (“binary dump”) where we
out two bytes per bit, it becomes 721 bytes, which gzip down to 106 bytes,
bzip2 down to 99 bytes, or LZW compress down to 138 bytes.  So even fairly
extreme inefficiencies in representational choice only cost a few dozen
of overhead.

This is nearly a best case.  SNMP packets in the wild commonly contain
multiple similar OIDs, long sequences of zero bytes, and similar
highly-compressible nonsense.  (To say nothing of endianness errors,
signedness errors, and integer truncation errors.)

The ad-hoc compression in SNMP is similar to the ad-hoc compression in
DNS, which would also be well-served by an ASCII text protocol with
optional compression.

### LBX was a waste of effort because LZ77 works better ###

Similarly, X11R6.3, one of the versions of X-Windows in the 1990s,
added a protocol extension called LBX, Low-Bandwidth X.  A great deal
of ingenuity went into reducing the size of messages in the X11
protocol, and an extension was added to the X server.  It met the same
fate; mostly quoting Wikipedia here:

> LBX was never widely deployed as it did not offer significant speed
> improvements. The slow links it was introduced to help were
> typically insecure, and RFB (VNC) over a SSH connection — which
> includes compression — proved faster than LBX, and also provided
> session resumption.
> Finally, it was shown that greater speed improvements to X could be
> obtained for all networked environments with replacement of X’s
> antiquated font system...

Unfortunately, I don’t think ASN.1 BER or curses are likely to meet
the same fate as LBX any time soon.  But if you were designing a
system today, with the knowledge of LZW and LZ77, you could avoid them

### Git uses compression instead of storing file diffs ###

Obsolete version-control systems like RCS and Subversion use the
worst-case O(N²) longest-common-subsequence algorithm to determine the
smallest possible edit to get from the current version of a file to its
previous version, or vice versa, so that storing all the past versions
of a file takes only slightly more space than storing the current
version of it.  This complicates file renaming and fails to save any
space when you're using the wrong newline convention.  However, it means
that the diffs are already computed and, in theory, available for use in
merging branches.

Git, instead, concatenates many different versions of many different
files into a “packfile”, sorted by a crude measure of similarity, and
compresses it with LZ77.  This turns out to produce a smaller total
filesize, and it eliminates the coupling between the storage format and
merge algorithms that has plagued many obsolete version control systems.

### Complexity and adaptability to pathological cases ###

LZW is only about 50 lines of code, which is a lot less than LZ77, and
it has less overhead than `gzip`, but neither it nor Burrows-Wheeler do
as well as LZ77 compression in extreme cases; the Gnumeric file
mentioned above is 9kB compressed with `compress`.  Some screen updates
I tested --- concatenating slightly modified copies of a 2.5K screen
image --- were an average of 140 bytes each with `gzip`, but 1200 bytes
each with `compress` and 270 bytes each with `bzip2`.

### Summary ###

So, to a great extent, you can forget about the space-efficiency of your
formats and wire formats if you run them through a generic compression
algorithm as a last step, and optimize them entirely for readability,
extensibility, and simplicity.  Gnumeric takes this approach.  A particular
Gnumeric spreadsheet I have handy here, representing a screenful of text,
2.7kB on disk; `gzip -d` on it produces 32kB of XML.

SAT solvers and theorem provers

I assert without proof that a substantial chunk of compiler
optimizations could be solved with a general-purpose SAT solver, and
even more with a general-purpose theorem prover.

Suffix arrays provide searching, sorting, indexing, and compression

Computer systems have a lot of code in them to do search.  LZ77
implementations must search for previous occurrences of the current
input string within their window.  Compilers and linkers must search
for symbols in symbol tables.  Databases must search by various keys,
including occasionally finding keys within ranges.  Full-text search
engines must search for terms that occur anywhere within documents.
Filesystems must search for filenames within a directory.

### Full-text indices subsume single-column RDBMS indices ###

There’s a small software company in Florida called askSam, which sells
a piece of software also called “askSam”, billed as a “free-form
database”.  Basically you divide your data into records.  Your records
are basically strings of text, but there’s a convention for “fields”:
a field named FOO is the text following the string “FOO[” up to the
next “]”.  This sounds kind of hokey, but with a little bit of
full-text indexing, an awful lot of queries get performance comparable
to the performance they’d get in a traditional relational database
with, you know, columns and shit.  (There are some queries that don’t,
of course, like multicolumn queries.)

So, in a sense, full-text indices subsume the more normal kinds of
database indices as a special case.  (Except for multicolumn indices,
and even for single-column queries, they’re probably worse by constant

### Suffix arrays ###

One particularly interesting kind of full-text index is the suffix
array.  In a suffix array, you consider your entire corpus (database)
as one long string, and the index is an array of integers, one integer
per index point, and that integer is the offset into the string of
that index point.  (In the usual case of indexing a document full of
words, you might have an index point at the beginning of each word; if
you want to support arbitrary substring search, you might instead have
an index point at every character.)  The tricky part is that the
integers are sorted in the *lexicographical order of the suffixes of
the corpus starting at the points they point to*.  Which means that
all the index points followed by, say‚ “walnuts” are in a single run
in the array.  So you can binary-search in the array to find all the
occurrences of a word, and the first thing alphabetically following
it.  (There’s a trick called an LCP-LR array that stores some extra
information so that you can find arbitrarily long strings in
essentially linear time.)

It turns out that there’s a linear-time algorithm for constructing a
suffix array in about 50 lines of code, called the “skew algorithm”,
discovered by Kärkkäinen and Sanders.  (This might sound like it’s
asymptotically better than the O(N lg N) needed to construct a regular
database column index, but that’s sort of an illusion.  I’d be very
surprised if it turned out to be faster in practice.  But I don’t
expect it to be many times slower or asymptotically slower, either.)

Another feature of suffix arrays is that they give you the suffixes
beginning with a given string in *sorted* order.  That means that if
you have a big text file, you can find the range of its suffix array
that begins with '\n' and iterate over it, and you have the lines of
the text file in sorted order.  (Except for the first.)  And if you
want your emails sorted by subject, you can get most of the way there
by looking at the suffixes of your email file that begin with
'\nSubject:' --- then you just need to search from there to the
beginning of each email, which can be done relatively efficiently.

So what would it mean if you could replace most sorting and searching
code with the use of a single suffix-array primitive?  Things would be
a constant factor slower, but how much slower?

### Burrows-Wheeler compression is easy once you have a suffix array ###

Also, revisiting the subject of generic compression algorithms, there's
Burrows-Wheeler compression, which is commonly substantially more
efficient than LZW or LZ77, the hard part of which is generating a sort
of suffix array.  Perhaps if you already have an efficient suffix array
generation algorithm, implementing Burrows-Wheeler compression and
decompression might be easier than implementing LZ77 and almost as easy
as implementing LZW.  (You still need the other algorithms, though,
because Burrows-Wheeler isn't suitable for compressing streams such as
remote desktop sessions, and it does much worse than LZ77 at compressing
extremely repetitive things like Git packfiles or sequences of screen

There are “compressed full-text indices” or “self-indexes” based on
Burrows-Wheeler transform that simultaneously provide the search
of suffix arrays and the compressed-text-retrieval functionality of BWT
compression — in effect, the overhead of indexing your text is negative
So far I’ve been too intimidated by Navarro and Mäkinen's highly-cited
[survey paper on the subject][Navarro] (67 pages long, including a
bibliography) to actually read it, so I don’t know if they have the kind
power-to-complexity ratio that the other things in here have.

[Navarro]: ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/survcompr.ps.gz

### Replacing hash tables ###

It may be a little hard to see how you could replace hash tables in
general with suffix arrays, since hash tables often contain references
to garbage-collected objects in memory, not just text strings.  You
could generalize your strings to contain object references as well as
characters, which doesn’t cause any problems for the skew algorithm as
long as there’s a well-defined ordering for object references; you could
end up building strings like this:


where the punctuation characters are actually references to objects.
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-tol
CD: 4ms