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.

Microsoft bitten by a software patent

The injunction (PDF), which becomes effective in 60 days, prohibits Microsoft from selling future Word products that allegedly use the patented technology. It also enjoins Microsoft from testing, demonstrating, marketing or offering support for those future products.

Davis also ordered Microsoft to pay i4i more than $290 million in damages.

- Nick Eaton at The Microsoft Blog

Large corporations like Microsoft like software patents because they are a barrier to entrance for new corporations. Large companies can cross-license with each other. Small companies, meanwhile, don't have their own patent portfolio, so they can be sued out of existence. Occasionally the tables are turned, as in this case, but apparently Microsoft still thinks it's worth it, at least as of 2007.

From all other perspectives than that of the largest software companies, software patents are failing. The above patent should have never been granted. Worse, a company with the legal resources of Microsoft should have had no trouble proving prior art and overturning the patent. As much as I relish the irony of this case, it isn't just, and I hope it is overturned on appeal. There is no sense that i4i's inventions are being protected. It's simply legal warfare.

I should write more about software patents. As a place to start, the meandering manifesto of the League for Programming Freedom has several highlights that have influenced me.

Dead-for-Now (DFN) Code Splitting

Demand-loading of program code is an old idea that is very important for web applications. Ajax applications typically have 2-4 megabytes of JavaScript code, and it takes enough time to download and parse that code that there are large user-visible pauses. Web sites need to go lightning fast whenever possible, and one tool in the toolbox is to load only part of the code to begin with and load the rest later.

This idea isn't new, of course. Unix loads programs on demand, one page at a time. When you start an application on Unix, the OS loads only its first page. Whenever execution goes off of that page onto a new page, it traps into the OS to load a new page. On machines too memory-constrained for that to work, a manual-control variation called memory overlays are often used. Also, on the web, Java applets attempted to solve this problem by loading one class at a time. Unlike the prior two approaches, the class-by-class demand loading of Java applets failed to ever become practical, and it was abandoned in favor of loading at the jar granularity.

For about a year now, I've been maintaining GWT's implementation of demand loading, which was designed by Bruce Johnson. One of Bruce's key ideas was to break with the page-by-page loading done for applications loading from disks. Java applets initially stuck to that model, but there are severe problems with it, essentially equivalent to the problems of synchronous XHR that I previously posted about. Bruce is in the "yes, it's evil" camp, and I agree. The problems are just too hard to overcome. Therefore, a key part of GWT's demand loading system is that whenever you request code that might not be available yet, you supply a callback that is invoked asynchronously.

Another key part is that deployed GWT apps always go through a whole-program compile. As a result, GWT's code splitter can use static analysis as part of the system. A common static analysis is the identification of dead code, code that is part of a program but will never run. We like to say that GWT identifies code that is "dead for now."

The Fable of the Fable

Gene Expression is normally an interesting blog, but they have
now joined the ranks of Qwerty basher bashing.
They start by being merely incorrect:

In 1990, Stan Liebowitz and Stephen Margolis wrote an article
detailing the history of the now standard QWERTY keyboard layout
vs. its main competitor, the Dvorak Simplified Keyboard. In brief,
the greatest results in favor of the DSK came from a study that was
never officially published and that was headed by none other than
Dvorak himself. Later, when researchers tried to devise more
controlled experiments, the supposed superiority of the DSK mostly
evaporated.

They then go from this bad footing to launch stink bombs like this one:

Shielded from the dynamics of survival-of-the-fittest, all manner of
silly ideas can catch on and become endemic. In this case, the
enduring popularity of the idea is accounted for by the
Microsoft-hating religion of most academics and of geeks outside the
universities. For them, Microsoft is not a company that introduced the
best word processors and spreadsheets to date, and that is largely
responsible for driving down software prices, but instead a folk devil
upon which the cult projects whatever evil forces it can dream
up. Psychologically, though, it's pretty tough to just make shit up
like that. It's easier to give it the veneer of science -- and that's
just what the ideas behind the QWERTY and Betamax examples were able
to give them.

To take this backwards, I read the "Fable" article they link back in the 90s,
and I found it uncompelling. I went on to spend a month retraining with
Dvorak, because I expect to be typing for at least another decade. I believe
the benefits of Dvorak are modest, but given the enormous amount of
typing I expect to do, it will add up.

Microsoft never entered the picture except in a positive way. It occurred to me
at the time that, unlike with the computers of my childhood, computers
with operating systems like Microsoft's make it exceptionally easy to switch
the layout to Dvorak. Far from believing that Microsoft locked in Qwerty,
I have considered them part of the revolution. For me, Microsoft
does not explain the mystery. It deepens it.

The case for Dvorak looks good. The famous "Fables" article
mostly only argues that that Dvorak's study, from nearly a century
ago, is by itself not very compelling. It ignores substantial other
evidence that has accumulated since then. For one, the fastest
typist in the world prefers Dvorak. Further, the evidence is
overwhelming that Dvorak reduces finger travel distance
when typing English text. By Occam's Razor, we should
assume until proven otherwise that this longer finger distance
implies slower speed and greater wear and tear.

At this point, it looks like Dvorak really is better. The economic
study of how we got here, far from being based on a fable,
is a legitimate scientific probe into a surprising aspect of
our world.

Not a good job for the FTC

According to the Associated Press:

New guidelines, expected to be approved late this summer with possible modifications, would clarify that the [Federal Trade Commission] can go after bloggers - as well as the companies that compensate them - for any false claims or failure to disclose conflicts of interest.

Such activity seems out of place for American society. We normally allow wide latitude in speech about products, and because of that we get robust protection against biased claims. While people can claim any number of things I would rather they didn't, it is equally easy for others to rebut those claims. Each individual who cares then holds a personal court to weigh the arguments they have heard. It's a beautiful system in theory, and it seems to have worked well in practice. Societies where speech is monitored for impropriety, in addition to being rather unpleasant, tend to have individuals with worse information. The censors damp down everything, not just the bad information.

Given this rich history, what is the argument for doing things differently for blogs? After such good experience with free speech, why flirt now with gossip police?

My best guess is that the FTC is fighting to expand its scope. Especially if broadcast TV declines, which seems inevitable given its many competitors, the FTC might fear having a number of censors on hire but no content to monitor. That would be bad for the FTC, but it looks good for the public.

Can you spot Frankie?

He's skittish, and he hides all the time. However, he's not very good at it.

Google Wave Announced

Google Wave was announced yesterday.  If you haven't yet, check it out.  It provides a hosted messaging service that, with a few simple features, supports all of: email, instant messaging, and collaborative document editing.  It also has an open extension mechanism, so it can be used as a substrate for specialized applications, like blogging, photo album sharing, and issue tracking.

I haven't perused all the web information myself, but I hear that the Tech Crunch article is quite good.  Also, if you have some time, the demo is mind-blowing.

Features and vision aside, I must say they made an excellent choice in implementation technology.