Tuesday, August 18, 2009

Optimizing not just for size, but compressed size

Ray Cromwell has come up with a new optimization goal for a compiler, and two examples of it:

I was drawn to a reversible transform the browser already includes support for: gzip compression, and decided to ask the question: what effect does the large-scale structure of the JS output code have on the DEFLATE algorithm of GZIP which is used to serve up compressed script? The answer it turns out, is substantial.

In short, he has found two semantics-preserving program transformations that have low impact on raw output code size, but have a big impact on what gzip can do with that output. One of them is to rename variables in a stable order, instead of the random order GWT previously used. The second is to reorder the top level function definitions so that textually similar functions are near each other. In combination these lead to a whopping 20% reduction in the compressed size of GWT's "Showcase" sample app.

The algorithms he has tried look like the tip of an iceberg of possibilities, yet the benefits are already huge.


Alex Rudnick said...

Lex, that is really exciting.

Are the Showcase improvements representative, do you think, of what other apps might see in the wild?

Lex Spoon said...

I'd guess the benefits apply widely. However, experience will have to show!