as simple as possible, but no simpler

Box2D as a Measure of Runtime Performance

2011-12-15T15:52:00.000-05:00

For those unfamiliar with it, Box2D is a great 2D physics library written by Erin Catto, which is at the core of a large number of casual games on consoles and mobile devices. Angry Birds is one you might have heard of, but there are many, many others.

It's also not a simple library by any means. When porting Angry Birds to HTML5, we found that in some cases Box2D performance could be the limiting factor in the game's frame-rate (on the more complex levels). It turns out this little library is doing a lot of work under the hood. And the work it's doing isn't limited to any one tight loop or hotspot. Rather, its work is distributed all over the place -- matrix and vector math, creation of lots of small objects, and general object-oriented logic distributed over a complex code base.

Motivation

Box2d makes a great general benchmark -- it's a bottleneck on real-world apps, and there's no one thing that a VM or compiler can optimize to "fix it". It also has the nice property that it's been ported to lots of different platforms -- the original is written in C++, and it's been ported to ActionScript, Java, Javascript, and several other systems. So I took it upon myself to put together a little benchmark that measures the time it takes to simulate one frame of a reasonably complex Box2D world.

The goal of this little experiment is not to add fuel to the flames of the Internet's already-tiresome "Compiler and VM Wars" -- rather, my intention is to get some hard data on what behavior real-world performance-sensitive code can actually expect to see in practice on various platforms. Measuring the performance of virtual machines in isolation is particularly tricky, but this benchmark has the nice property that, if a VM or compiler improves it, then real-world problems are actually solved in the wild, and everyone wins.

The Platforms

My intention is to measure the performance of various platforms, not particular Box2D ports. The ports themselves necessarily vary somewhat from one-another, but they should still be broadly equivalent. The reason Javascript VMs are represented four times in this list is that I wanted to make sure that we compared Javascript VMs, at their best, to the JVM, NaCl, and native code.

Native : This is the standard Box2D code, compiled via gcc or clang/llvm (the latter on my test machine, as described below).
NaCl : The same code, compiled via the NaCl SDK's custom gcc build, and running within Chrome.
Java : The JRE (1.6), as currently shipped by Apple on Mac OS 10.6.
Box2D-web : The hand-written Javascript Box2D port, on various browsers.
Emscripten : The original C++ code, compiled via Emscripten to Javascript.
Mandreel : The original C++ code, compiled via Mandreel to Javascript.
GwtBox2D : The Java port, compiled via GWT to Javascript.

The Test

World

Picking the right world structure for this kind of benchmark is a bit tricky, because it needs to have the following properties:

A high per-frame running time.
Not settle quickly: simulations that settle eventually stop doing work, as the physics engine skips calculations for settled objects.
Stable: Subtle variations in the behavior of floating-point math can cause the behavior on different VMs to diverge badly, invalidating comparisons.

I eventually settled on a simple pyramid of boxes with 40 boxes at the base, for a total of about 800 boxes. I manually verified that this simulation is stable on all the systems tested, and that it doesn't settle within the number of frames simulated for each test. It takes at least 3-4ms to simulate in native code, and only gets slower from there, so the running time is sufficient to avoid problems with timer resolution.

Code

All the test code is available on GitHub. Some of it requires a bit of care and feeding to get running (especially the C++ version), but should allow you to reproduce these results if so desired. There are also copies of the Mandreel and Emscripten Javascript output checked in, so you won't have to go through the pain of building those yourself.

Test System

I used my MacBook Pro 2.53 GHz Intel Core i5 as a test machine. It seems a fairly middle-of-the road machine (maybe a bit on the fast side for a laptop). As always, your mileage may vary.

Data

The raw data I collected is in the following spreadsheet. I ran each test several times, to mitigate spikes and hiccups that might be caused by other activity, and to give each system a fair chance. Each run warms up over 64 frames, and then runs for 256 frames -- I've confirmed that the simulation is stable over this duration on all the platforms under test.

First, let's look at all the results together, on a log-scale graph:

The first thing you'll notice is that there are three clusters of results, centered roughly around 5ms, 10ms, and 100ms. These clusters are associated with native code, the JVM, and Javascript VMs.

Now let's compare the best of the best of each of these three groups.

This is similar to the first graph, except that we've removed the noise of NaCl (which is within 20-30% of raw native performance) and all but the best of the various Javascript approaches. This looks a bit better for Javascript, clocking in at a mean of around 50ms (interestingly, this number is achieved by the Mandreel C++ cross-compiler running on Chrome 17; more on this below).

Analysis

Looking at the last graph above, I believe the most important observation is that, while Javascript implementations have improved drastically in recent years, the best result achieved by any Javascript implementation is still more than an order-of-magnitude slower than native code. This is perhaps an unsurprising result to many, but some have begun suggesting that modern Javascript VMs are "nearing native performance". While this may be true for some workloads, they still have a long way to go in this case.

This also demonstrates that native code compiled via NaCl stays within 20-30% of the performance of un-sandboxed native code, which is in line with what I've been told to expect.

Finally, it's somewhat interesting to see that the JVM is running 3x slower than native code. I've been told, anecdotally, that OpenJDK on Mac OS X is producing numbers closer to 6ms/frame, which would be ~50-60% slower than native, but I need to confirm this. I don't think it can be proven, but I suspect the JVM's performance can be taken as a rough lower-bound on what one can expect from any dynamic VM. Thus, Javascript VM implementors can take the JVM's performance as a reasonable target to shoot for.

Appendix: Javascript Implementations and Compilers

While it wasn't a primary goal of these benchmarks, they do give some interesting data about Javascript VMs, and the various compilers that use Javascript as a target language.

The following is a graph of the Javascript VMs in Chrome, Safari, Firefox, and Opera (IE9's Chakra VM is not yet included because it seems that Box2D-Web is using Javascript properties, which it doesn't support yet).

First off, all the VMs tested are well within 3x of each other, which is wonderful, because wildly variant performance across browsers would make it exceedingly difficult to depend upon them for any heavy lifting. V8 and JSCore are quite close to one-another, but JSCore has an edge in variance. It's not immediately obvious what's causing this, but GC pauses are a likely culprit given the regularly-periodic spikes we see in this graph.

Now we move to the various Javascript compilers. Here we have Box2D-Web (representing "raw" Javascript), Emscripten, Mandreel, and GWT (Closure Compiler should give performance roughly in line with "raw" Javacript on any modern Javascript VM).

The real shocker here is that Mandreel outperforms all the others fairly consistently, given that it's translating C++ to Javascript (!). Note that the Emscripten results are not as good as they could be -- the author is currently finishing up a new optimizer. I also believe the GWT compiler should be doing a better job than it is; there are a couple likely culprits in the compiled output involving static initializers and array initialization overhead. It should be possible to optimize these out and improve the results.

Note: See the update below about Emscripten performance

Caveats

As with all benchmarks, especially ones as fuzzy as this, there are a lot of caveats.

The code's not identical

These are all ports of the same C++ source code, so by their nature they must vary from one another. It may be the case that a particular port is unfairly negatively biased, because of particular idioms used in the code. If you suspect this is the case, please say so and preferably offer a patch to the maintainer. These aren't being used in the same way as, e.g., the V8 or Kraken benchmarks, so it's entirely fair to optimize the code to get better numbers.

I may have made mistakes

I suppose this goes without saying, but there are a lot of knobs to be tweaked here, and there could easily be something sub-optimal in my configuration, makefiles, or what-have you. If you notice anything amiss, please say so and I'll try to address it.

This is just one machine

As described above, I ran these tests on my MacBook Pro. The relative performance of these tests might not be the same on different machines.

Update

Based on feedback from comments and elsewhere, I've updated a few of the numbers in the linked spreadsheet, along with the graphs.

Emscripten: I got an updated build with a better compiler, and the numbers are now much more in line with the other Javascript implementations.
Java: I updated the JVM implementation to use a faster sin()/cos() implementation (there was a flag for this in the JBox2D code that I simply missed. It's no about 2.5x the speed of the native implementation. I also wasn't entirely clear about what I meant by the "JVM" -- so to be clear, this means the standard Mac OS X JDK 1.6 server JVM (there is no standard client JVM on the Mac).

None of this changes the core conclusions in any substantive way, however.

An Ugly Bug in the IE9 Beta

2010-09-16T12:33:00.001-04:00

Hot on the heels of my very happy discovery that IE9 finally plugs its leaks, I've found a subtle-but-important bug in the IE9 beta. Bear with me, as it's a little tricky to explain.

The Good News

IE9 finally implements the standard HTML5 DOM element interfaces, which will make many things simpler. Further good news: IE9 includes a nice debugger you can use to explore these interfaces. As I understand it, the IE team has cleaned up all the bizarre old COM bindings that have been giving developers fits for years. So when you inspect an element in their nifty new debugger, you get something like this:

document.body   {...}                     [Object, HTMLBodyElement]
- accessKey     ""                        String
- appendChild   function appendChild(...  Object, (Function)
...

The Bad News

This is beautiful, and matches your expectations of the interfaces quite nicely. But then I discovered this little gem:

elem:           {...}                     DispHTMLImg
- [Events]
- [Expandos]
- [Methods]
- accessKey     ""                        String
...

What on earth is this? It sure looks like an IDispatch interface to an element -- but I thought we weren't supposed to be seeing that sort of thing anymore. But if you resolve properties on the object using the Javascript VM, most of them resolve the same way, so no harm done, right?

Not so fast. When digging into a bug in my code, I kept running into this bizarre situation where elements didn't seem to be comparing properly. Specifically, I got into a situation where (ElemA == ElemB) and (ElemB != ElemA). These were two different elements, so they shouldn't have been equal to one another anyway, but the asymmetric equality relation was a really big surprise!

As you might have guessed, one of these two elements was an HTMLElement, while the other was a DispHTMLDivElement. Ok, if one of them is a Disp interface to an element and the other is a native DOM host object, you can imagine how the comparison might get screwed up (I'm going on the assumption that IE didn't expect to have those Disp objects exposed at all). Which begs the question of how I got that reference in the first place.

When I tried to reproduce the bug in isolation, everything seemed to work fine -- no Disp references in sight. I finally tracked it down to the fact that my code was running in an iframe, while the DOM elements themselves were in the outer frame (this is a not-uncommon technique for isolating code). Specifically, it seems to be triggered by the following situation:

Outer page:
  <div id='target'>...</div>

IFrame:
  <script>
  var target = parent.document.getElementById('target');
  target.onclick = function(evt) {
    // both 'evt' and 'elem' will be Disp interfaces
    var elem = evt.currentTarget;
  };
  </script>

So it appears that something's going wrong when marshalling the event object from one frame to the other. And once you get one of these funky Disp objects, all references you get from it will be Disp objects as well. Which opens you to these comparison failures.

A couple of caveats

I'm assuming that the "Disp" part of these objects' names refers to IDispatch, but if that's not correct it doesn't really change much. Also, you may have noticed that I used the == comparison operator above -- it turns out that === behaves as expected. However, there's no good reason to use === when comparing two objects.

A possible explanation

If I understand IE's architecture correctly, older versions appeared to use DCOM for cross-frame communication. If I'm correct about this (and it's still the case in IE9), then it may be that something just went wrong in the marshalling of references from one frame to another (hence my assumption that "Disp" means "IDispatch").

Does This Really Matter?

Yes. It might seem really subtle, but these are the kinds of bugs that can take hours or days to track down when something goes wrong (and for which the fix is non-obvious at best). And while putting your code in an iframe might seem like a slightly odd thing to do, there are very good reasons for it under some circumstances (I'll have more to say on precisely why this is important in a follow-up post).

Repro

I've posted a relatively simple reproduction case here. It's a little screwy, because it's a case hoisted out of a much more complex app, but it should illustrate the issue reasonably well.

IE9: Memory Leaks Finally Declared Dead

2010-09-16T11:26:00.001-04:00

It is with great pleasure that I can finally declare the infamous, painful, long-standing, never fixed IE memory leak bug fixed! With the release of IE9, I have verified that every leak pattern I'm aware of is fixed. It's been a long-time coming, but I'm starting to feel more confident that IE9 can be reasonably called part of the "modern web" -- the web that is sufficiently powerful to support complex applications, and not just lightly scripted documents.

One caveat: Do be aware that your "standard" pages need to explicitly request "IE9 Standards" mode, using either an HTTP response header or a meta tag like the following:

<meta http-equiv='X-UA-Compatible' content='IE=9'/>

Failure to do so, in addition to giving you all the old crufty bugs and quirks in previous IE versions, will continue to leak memory, presumably because it is using the DLLs from the old rendering engine.

Now perhaps I can finally stop writing about this stupid bug!

Trying out the new Wave element

2010-04-30T18:01:00.003-04:00

Google Wave just added a new "web element" that makes it easy to embed a wave in a blog or article, so I thought I'd try it out. If you're one of the two people who actually reads this, give it a shot. If you don't have a Wave account, you won't be able to edit -- if you need an invite, ping me at jgw@pobox.com.

Quake II in HTML5 -- What does this really mean?

2010-04-02T14:26:00.000-04:00

Now that we've finally been able to push our port of Quake II to the browser public, it's time to discuss the questions "what's the point?" and "what does this mean for the future?".

Let me begin with a tweet I saw last night, which neatly summarizes a very salient point:

Not sure if the best endorsement of JS engine speed in 2010 is ports of games from 1997...

http://twitter.com/tberman/status/11446377136

Well said. We should be setting the bar higher than this. The choice of Quake II was mainly predicated on the fact that a Java port already existed, and this was just a 20% project (more like -5%, actually -- nights and weekends for the most part). I'm pretty certain Quake III would have ported just as easily (perhaps more easily, as it was written specifically for hardware acceleration and likely leans on the hardware a little more).

So then there's the fact that it's running at frame rates about a third of what's possible on the same hardware in C (or on the JVM, for that matter). There are a few reasons for this:

There are inefficiencies still to be worked out in WebGL implementations, especially the expensive frame buffer read-back on Chrome.
There are things being done in Javascript that really ought to be done in vertex shaders; this especially applies to things like model animation interpolation, which is a nasty hot spot in the Javascript code that could easily be pushed to the shader.
There are some things, such as dealing with packed binary data structures, that are incredibly inefficient in Javascript (and I mean something like 100x slower than JVM or C code). This can be largely mitigated through better APIs, such as the Khronos Group's Typed Arrays spec.
This code is fairly idiosyncratic, having been ported from straight C, and exercises some code generation paths in the GWT compiler that could be better optimized (using lots of small arrays, and lots of static methods, still needs some work).

I would be willing to hazard a guess that we could easily get another 30% out of the frame rate with relatively minor tweaks. If the game were written from the ground up to work with web technologies, it would likely be twice as fast on any reasonable metric (frame rate, startup time, etc.). That's an extremely rough estimate, but I'd be willing to bet on it.

So back to our original question. What's the point? What this code currently proves is that it's feasible to build a "real" game on WebGL, including complex game logic, collision detection, and so forth. It also did an excellent job exposing weak spots in the current specs and implementations, information we can and will use to go improve them.

Now if I were starting with a plain C code base, I would most likely prefer to port it using a technology like NaCl -- that's what it's for. But while it's not feasible to actually ship games on WebGL yet (it will be a while before it's widely deployed enough for that), one can envision a world where game developers can deploy their games as easily as we currently deploy web pages, and users can play them just as easily. And that's a pretty damned compelling world to imagine.

Javascript Variables, Continued

2009-09-11T14:29:00.001-04:00

In my previous post, I addressed the question of the speed of variable access, as originally explored by Mike Wilcox here. In the comment section of his blog, he posted a cogent response to my concerns that I failed to address at the time (about a month ago). Sorry about that, Mike -- I blame the 10-month-old girl who consumes most of my time and attention lately :)

Terminology

A commenter on that post appears to take serious offense with my choice of terminology, so let's start by clearing that up:

Array Notation: What I am referring to here is the array-like syntax for accessing properties on Javascript objects. I am fully aware that there is a difference between accessing string-keyed and integer-keyed properties in this way. But it is not uncommon to refer to this as array-access notation. Call it what you will, but I suspect anyone reading this will have little trouble understanding what I'm referring to.
Globals and Fields: Perhaps I'm letting my Java-centric view of the world poke through a bit here, but I thought it was fairly clear from the examples I gave. I was using the term "global" to refer to a globally-scoped variable defined with an explicit "var" statement. The term "field" I used somewhat loosely to refer to an explicitly-defined property on an object. Again, sorry if this wasn't clear from context. Henceforth, I'll refer to the latter as "properties", which is more accurate in a Javascript context.

Now allow me a moment to clarify speicifically why I bring up the question of "array access" notation vs. "dot" notation (call them what you will). The problem with using them interchangeably in performance tests is that while logically they both refer to properties on an object, we have no reason to believe that their performance will be identical in all Javascript engines. In addition, there is good reason to suspect that accessing globals via window[name] may be significantly different from simply accessing them via an unadorned name expression.

Mike's Concerns

From Mike's comment:

I think we were going for slightly different goals, and that makes your tests very complimentary to mine.

This is an entirely fair point. Let me attempt to justify the particular forms of variable access that I chose to test. In a nutshell, I wanted to test the precise form of usage that I see in much, if not all, idiomatic Javascript, and that we produce from the GWT compiler. This involves global variables that are declared explicitly, as in:

var g0 = 0, g1 = 'foo', ...;

And objects whose fields (or properties, if you prefer), are explicitly declared and initialized (usually in a constructor function, but the expression form below is common as well):

{
  f0: 0,
  f1: 'foo',
  ...
}

These correspond to static and instance variables, respectively, in Java source code.

One thing to note, and I’m pretty sure neither of us did, is that the JS engine may possibly resolve those variables in the code block before the code is executed. Keeping them in functions (and not in the global scope) should prevent that.

setLVars = function(){ var a0=0;var a1=1;var a2=2;var a3=3;var a4=4; … 5000 }

I believe this is referring to the above test of initializing local variables, and it doesn't sound inplausible. In an attempt to work around this possibility, the "locals" test I added separates variable declarations from their assignments, and uses the same random values as all the other tests to initialize them.

A word on closures

When I added the test for variable access "via closure", it was to test a structure I've seen used a lot to isolate the "global" namespaces used by separate chunks of Javascript code. This pattern tends to look something like this:

(function() {
  var g0, g1, ...;

  function init() {
    // Do stuff with g0, g1, ...
  }

  init();
)();

This is a really useful pattern when you want to keep separately-loaded scripts from stepping on each-others' toes, and I thought it worthwhile to see if using such a structure imposed any significant overhead on access to globals.

You may note that my results for closures are much more flattering on some browsers than before. This is because I made a bad typo in the test and failed to declare the variables properly. This led to them being declared implicitly in the global scope.

Test Code

It also appears that both my dear commenter and Mike Wilcox himself had some difficulty reproducing my results with the simple snippets I provided, so I am publishing the test page here. I've made a few changes in the process:

I have changed references to "fields" to refer to "properties" for clarity.
I added a test for "locals" that should be self-explanatory.
I fixed a bug in the "closures" case that was skewing the results fairly badly.

If anyone notices anything amiss with this code, please do let me know. I am aware that the tests conflate read and write times, and that the accumulator code makes their absolute values irrelevant. What I'm attempting to tease out here is only the relative costs of defining variables in each scope.

Results

(Note that for simplicity's sake, I've simplified these results to only cover Safari 4, IE8, Firefox 3.5, and Chrome 2)

MacBook Pro 2.4 GHz Core 2 Duo:

Safari 4:
- Globals: 11ms
- Properties: 24ms
- Locals: 12ms
- Closures: 11ms
Firefox 3.5:
- Globals: 44ms
- Properties: 47ms
- Locals: 14ms
- Closures: 91ms

VMWare on aforementioned Mac:

IE8:
- Globals: 31ms
- Properties: 47ms
- Locals: 15ms
- Closures: 31ms
Chrome 2:
- Globals: 28ms
- Properties: 30ms
- Locals: 5ms
- Closures: 6ms
Firefox 3.5:
- Globals: 32ms
- Properties: 35ms
- Locals: 16ms
- Closures: 69ms

Again, please note that the results for closures are rather different than in my previous post, because of the aforementioned bug in my original test.

Regardless, though, the most clear patterns that emerge here are as follows: - In none of these cases are properties on a local object faster to access than globally-scoped variables. - Locals are almost invariably faster than (or the same speed as) global or property accesses, which is not terribly surprising. - Accessing variables via closure can be as fast as accessing variables in the global scope, but on Chrome it's actually faster, while on Firefox 3.5 it's about twice as slow.

Where should I define Javascript variables?

2009-08-10T23:12:00.001-04:00

I recently stumbled across this article by Mike Wilcox at SitePen, which suggests that defining Javascript variables in the global scope causes reads and writes to them to be much slower than if they are defined as fields on an object. While Javascript VMs never fail to surprise in their strange and disparate behavior, something didn't quite smell right about this, so I decided to dig in a bit further.

As I understand it, the investigation was triggered by Mike noticing a large number of global variables in the Google Docs graphics editor. The variables in question are defined something like this:

var rs=parseFloat;
var us="shape",vs="activeElement", ...

In all likelihood, a combination of normal static variables, interned strings, and such. In order to test the hypothesis that defining these variables in the global scope could be a performance problem, he created a test that looks something like this:

// Assume that v[i] is a randomly-created variable name.
obj = {};
setLocals = function(){
  for(var i=0;i<v.length;i++){
    obj[v[i]] = true;
  }
}

setGlobals = function(){
  for(var i=0;i<v.length;i++){
    window[v[i]] = true;
  }
}

Tests for reads follow basically the same form. You can see the results in the linked article, but the upshot is that accessing "globals" in this manner is anywhere from 1x to 10x slower than the equivalent object field access.

There are two main problems with this test:

It always accesses globals via the window object explicitly.
It doesn't explicitly declare the variables in either scope.
- This conflates creation with assignment.

Let's rewrite these tests to be closer to normal, idiomatic Javascript usage. We will declare global variables explicitly, and reference them implicitly. We will also explicitly declare the object fields explicitly, for as close an apples-to-apples comparison as possible. Note that the random variables, as well as the accumulator and return value, are probably-unnecessary attempts to normalize for any static optimization tricks that newer Javascript VMs might be playing.

// Allocate a bunch of random values to be used later in assignments.
var r0 = Math.random(), r1 = Math.random(), ... ;

// Test assignment and reading of global variables.
var g0 = 0, g1 = 0, ... ;
function globals() {
  var a = 0;
  g0 = r0; g1 = r1; ... ;
  a += g0; a += g1; ... ;
  return a;
}

// Test assignment and reading of fields on a local object.
var obj = {f0 : 0, f1: 0, ... };
function locals() {
  var a = 0, o = obj;
  o.f0 = r0; o.f1 = r1; ... ;
  a += o.f0; a += o.f1; ... ;
  return a;
}

In addition, we'll test the the performance of the increasingly common pattern of scoping variables via closure.

// Test assignment and reading of locals via closure.
function closures() {
  var c0 = 0; c1 = 1; ... ;

  return function() {
    var a = 0;
    c0 = r0; c1 = r1; ... ;
    a += c0; a += c1; ... ;
    return a;
  };
}

This is all far from "real-world" Javascript, but it's a lot closer than referencing everything by name, using the array notation. I generated the above code such that there were 1000 variables, assignments, and reads. I then averaged the times over 100 runs, getting the following results:

MacBook Pro 2.4 GHz Core 2 Duo:

Safari 4:
- Globals: 15ms
- Fields: 30ms
- Closures: 30ms
Firefox 3.0.12:
- Globals: 60ms
- Fields: 43ms
- Closures: 78ms
Firefox 3.5.2:
- Globals: 43ms
- Fields: 46ms
- Closures: 52ms

VMWare on aforementioned Mac:

IE8:
- Globals: 31ms
- Fields: 47ms
- Closures: 47ms
Chrome 2:
- Globals: 31ms
- Fields: 47ms
- Closures: 47ms
Firefox 3.0.8:
- Globals: 35ms
- Fields: 29ms
- Closures: 68ms

The absolute values aren't as important as the relative values for each browser. The most notable pattern is that globals and fields don't perform all that differently from one-another, and referencing variables via closure is almost invariably slower. This is a random smattering of browsers, and doubtless others will perform differently. But most importantly, there's no clear-cut advantage to either one.

This has limited implications for hand-written code; you're almost always going to want to write whatever makes the most sense to you, because the differences aren't all that great either way. It does have strong implications for tools (like GWT) that generate Javascript. Such tools have a high degree of latitude in how they define variables, and these small effects can be amplified for large programs.

I'd say the moral of this story is that you must be careful to measure precisely what you think you're measuring, especially in as complex and unpredictable a doman as Javascript VMs. I can understand how Mike arrived at this point -- in any sane world, (window[name]) would be the same as (name), since they do precisely the same thing. But we're not in a sane world here, are we?

Memory Leaks in IE8

2009-07-12T23:28:00.003-04:00

Now that IE8's out, it seems I get to revisit this topic once again, which is getting quite tedious. When Microsoft first began touting IE8 features, I noticed a couple of pages pointing out that they had done a great deal of work to "mitigate" memory leaks in IE. The word "mitigate" sounds a bit fishy, as the source of the problem is pretty fundamental to the design of the COM interface that their script engine uses to access the DOM and other native objects.

As you may recall, IE7 contained a rough attempt to solve this problem by walking the DOM on unload, cleaning up leaks on any elements still there. This helped somewhat, but left many common leak patterns unresolved (in particular, any element removed from the DOM could still leak easily).

From my tests, IE8 appears to have resolved all of the most common leak patterns (as described in the two IE8 links above). In particular, I can't uncover a single leak that doesn't at least get cleaned up on unload. This is good news for IE users, because under most circumstances it means that the browser won't get slow and bloated over time.

How IE8 leaks

With some cursory testing, however, I have uncovered at least one pattern that still leaks memory on IE8. Consider the following code (which you can run here):

// This approach hangs a massive js object from a dynamically created DOM
// element that is attached to the DOM, then removed. This pattern leaks
// memory on IE8 (in "IE8 Standards" mode).
function spew() {
  // Create a new div and hang it on the body.
  var elem = document.createElement('div');
  document.body.appendChild(elem);

  // Hang a *really* big-ass javascript object from it.
  var reallyBigAss = {};
  for (var i = 0; i < 5; ++i) {
    reallyBigAss[i] = createBigAssObject();
  }
  elem.__expando = reallyBigAss;

  // Complete the circular reference.
  // Comment out the following line, & the leaks disappear.
  elem.__expando.__elem = elem;

  // Remove it from the DOM. The element should become garbage as soon as
  // this function returns.
  elem.parentElement.removeChild(elem);

  // Just to give it a fighting chance to collect this garbage.
  CollectGarbage();
}

function createBigAssObject() {
  var o = {};
  for (var i = 0; i < 100000; ++i) {
    o[i] = 'blah';
  }
  return o;
}

This will leak at runtime on IE8. It does get cleaned up when the page is unloaded, but it can still be a serious problem for long-running pages (complex Ajax applications, for example).

This particular example is admittedly somewhat contrived, but it is actually isomorphic to a common use pattern:

Create an element.
Attach it to the DOM.
Create some event handlers that result in circular refs.
At some point in the future, after the user's done with it, remove it.

Sounds like a popup, a menu bar, or just about any interactive element that gets created and removed in an application, n'est-ce pas?

What should I do about it?

Honestly, I would advise that you continue to do whatever you always have done. Most Java[script] libraries (GWT, Dojo, jQuery, Prototype, etc.) already have code in place to clean up these sorts of leaks, and they will continue to work as advertised (I've personally checked GWT for leaks on IE8). It is unfortunate that we have to continue doing these things, because they have a non-trivial performance cost; and although it's taken a while, WebKit and Gecko seemed to have finally nailed their own memory leak issues.

Aside: Drip is dead

I wrote Drip some years back in order to help track down memory leaks on Internet Explorer. I incorrectly assumed that it would be useful for a year or two, as the problem would eventually be dealt with by Microsoft.

Well, they did finally deal with the problem, primarily by building their own memory leak detector. The good news is that it works quite well, and is probably much more comprehensive than Drip ever was (and I haven't had much time to maintain it). The first caveat I would add is that you almost invariably want to change it to report "actual leaks" -- I don't find the IE6 and IE7 options to be useful in practice. The really bad news is that it isn't useful on IE8 -- it will install, but doesn't catch any actual leaks, as far as I can tell.

Oct 28, 2009 update: Keilaron kindly points out that Microsoft's memory-leak detector article has been updated, and I've updated the above link accordingly. The linked article still claims that "In IE8 the problem is completely mitigated.", which appears to still be an overstatement at best.

GWT, JavaScript, and the Correct Level of Abstraction

2009-07-12T15:10:00.006-04:00

[note: I originally posted this last December on the "Unofficial GWT Blog" that Scott Blum and I created, but neither one of us has had much time to maintain it, so I'm copying it back here to keep everything in one place.]

John Resig seems to have stirred up a bit of a hornet's nest with a recent post on JavaScript language abstractions. I don't want to wade into the details of the argument; I think Francisco over at cappuccino.org does a great job of explaining the value of language abstractions that I largely agree with.

However, I've noticed a number of misunderstandings about GWT in this and other articles, and I feel some clarification is in order.

Why Java?

First and foremost, let me clarify yet again the reasons behind the decision to use Java as a source language. Allow me to quote from the "Making GWT Better" document:

Why does GWT support the Java programming language instead of language X? In a word, tools. There are lots of good Java tools. That's the entire explanation. It isn't that we don't like language X or that we think the Java programming language is somehow superior. We just like the tools.

This point has perhaps been beaten to death, but there are a lot of good tools for Java, whether you love the language itself or not. Code completion, automated refactoring, static error detection, code coverage, testing, and so forth, are pretty hard to give up once you're used to them.

But wait, there's more. Let's talk about compiler optimizations a bit. I'll quote Ray Cromwell, from the comments on Resig's article:

... Aggressive compiler optimizations, that happen before code is sent down the wire. This is a problem that no amount of trace-jitting will solve. Far from being bloated, as I demonstrated in my GWT Query presentation at Google I/O, GWT can produce code an order of magnitude smaller than most selector libraries in specific circumstances. GWT can prune dead code far better than any JS optimizer, and can obfuscate code to reduce size in a way that helps maximum GZIP/DEFLATE algorithms.

What Ray's referring to here is the fact that a statically-typed language like Java allows you to perform absolutely correct optimizations far in excess of what is achievable without type information (There's a lot more to say on this topic, which I'll save for a future post).

Why is this so important for JavaScript output? In a word (or two), code size. Code that grows without bound is a serious problem for Javascript applications, and static analysis gives us a lot of leverage over the problem. The GWT compiler can determine precisely which classes, methods, and fields are actually used and aggressively prune everything else. And this pruning feeds back into the iterative compilation process, allowing still more optimizations (e.g., type-tightening, devirtualization, and so forth) to be performed.

Indeed, you can take this even further, with a concept we refer to as runAsync(). With static whole-program analysis, it is possible to automatically break a program into optimal fragments at user-defined cut points. This is still experimental, but the preliminary results look pretty good.

To put all this in concrete terms, check out this great example on Ray's blog showing the following transformation:

  public class MyArray implements Iterable<string> {  
    private String[] items = {"foo", "bar", "baz"};  

    public Iterator<string> iterator() {  
      return new StringArrayIterator(items);  
    }  

    private class StringArrayIterator implements Iterator<string> {  
      private String[] items;  
      private int index;  

      public StringArrayIterator(String[] items) {  
        this.items = items;  
        this.index = 0;  
      }  

      public boolean hasNext() {  
        return index < items.length;  
      }  

      public String next() {  
        return items[index++];  
      }  

      public void remove() {  
        throw new UnsupportedOperationException();  
      }  
    }  
  }  

  void iterate() {
    MyArray m = new MyArray();  
    for(String s : m)   
      Window.alert(s);  
  }

iterate() becomes

  function $iterate(m){  
    var s, s$iterator;  
    for (s$iterator = $MyArray$StringArrayIterator(new MyArray$StringArrayIterator(), m.items);  
       s$iterator.index < s$iterator.items.length;) {  
      s = s$iterator.items[s$iterator.index++];  
      $wnd.alert(s);  
    }  
  }

which becomes something like

  function x(a){var b,c;for(c=y(new z(),a.a);c.b<c.a.length;){b=c.a[c.b++];$wnd.alert(b);}}

The point of going into all this detail about tools and optimization is that choosing Java as a source language gives GWT leverage that would have been provably impossible in JavaScript. It's most emphatically not about loving or hating any given language, or providing Java programmers with a way to avoid JavaScript -- it's a pragmatic decision based upon specific, measurable benefits.

I've seen lots of assertions that various languages are either "higher level" or "lower level" than others, without any clear definition of what metric is being used to justify these statements. For example, "JavaScript is the assembly language of the web" or "Java is a low-level language because it doesn't have closures and dynamic typing". These sorts of arguments are pointless at best, and at times simply disingenuous. What matters is not some ill-defined notion of a language's "level of abstraction", but rather what you can actually achieve with it.

JavaScript Interop

So what if I need to write or use existing Javascript code? Most everyone seems to finally be aware that it's possible to write JavaScript directly in your Java source using JavaScript Native Interface methods, like so:

  // Java method declaration...
  native String flipName(String name) /*-{
    // ...implemented with JavaScript
    var re = /(\w+)\s(\w+)/;
    return name.replace(re, '$2, $1');
  }-*/;

What doesn't seem to be clear is just how fundamental a feature this is. I've seen various people suggest that this is somehow "circumventing" the "normal" way of doing things -- and while it's true that you lose some of the benefits of Java type-checking, optimization, and debugging in these methods, they're also the foundation upon which all the GWT libraries are built. And there's no particular reason they have to be short snippets, either. They can be complex methods and classes that reach back into Java code, pass exceptions around, and so forth.

What about calling into existing JavaScript libraries, or exposing GWT classes to JavaScript code? For the former, check out Sanjay Jivan's SmartGWT library, which wraps the massive Isomorphic SmartClient library. For the latter, have a look at Ray Cromwell's GWT-Exporter gwtexporter library.

It's also worth noting that this functionality, combined with Overlay Types makes it really easy to efficiently parse and operate on JSON structures. Once again, you get a side-benefit: once you've written the overlay type for a particular JSON type, everyone using it gets code completion and documentation for free. For example:

  var customerJsonData = [
    { "FirstName" : "Jimmy", "LastName" : "Webber" },
    { "FirstName" : "Alan",  "LastName" : "Dayal" },
    { "FirstName" : "Keanu", "LastName" : "Spoon" },
    { "FirstName" : "Emily", "LastName" : "Rudnick" }
  ];

  class Customer extends JavaScriptObject {
    protected Customer() { } 

    public final native String getFirstName() /*-{ return this.FirstName; }-*/;
    public final native String getLastName()  /*-{ return this.LastName;  }-*/;
  }

which means, as a user of this class, if I get a Customer type from somewhere, I don't have to ask what fields and methods are available. The IDE can simply tell me.

HTML DOM Integration

But don't GWT's abstractions keep you from just working with DOM elements? Again, no. It has always been possible to work with the DOM from GWT (how else do you think all those widgets get implemented?), but as of 1.5, it's gotten a lot easier. See this Google IO presentation for details. Here's a taste, though:

  TableElement table = ...;
  String s = table.getRows().getItem(0).getCells().getItem(0).getInnerText();

Which of course translates to:

  var s = table.rows[0].cells[0].innerText;

With the important addition that as you type "table.[ctrl-space]", the IDE can actually tell you that "getRows()" is an option. Given that TextAreaElement alone has nearly 100 methods, that starts to be pretty useful.

The statement "You are likely to never see a DOM object or pieces of the native JavaScript language" is actually only as true as you want it to be. Most JavaScript frameworks provide some sort of higher-level abstraction than simple DOM elements, and GWT is no exception, but you should pick the right level of abstraction for the task at hand.

Independently Useful Parts

Finally, we have the question of whether (GWT === GWT's libraries). This is another common misconception -- GWT looks interesting, but I don't like the way their widget library works. That's like saying you like JavaScript, but not the way Prototype (or whatever) works.

GWT "eats its own dogfood" almost all the way down. That is to say, there's practically no module you can't replace (including the JRE). Like the DOM and JRE modules, but not all the widgetry? Write your own widgets. Don't like any of the modules? Replace the whole bloody thing! The many problems of building browser-based UIs are not yet well-solved in the state of the art, so it's highly unlikely that GWT's widget library represents a "perfect" solution. For a completely different take on how a widget library should work, have a look at the Ext-GWT library.

To Sum Up

I hope I've managed to convey the pragmatic goals that underlie GWT's design decisions, and the methods we've used to achieve them. There are still a million things we'd like to build and/or change, but I feel like it's off to a pretty good start. Nothing would make me happier than if we could stop arguing about abstract notions of what language is "right" and focus on practical goals and metrics.

IE's Memory Leak Fix Greatly Exaggerated

2007-09-17T16:08:00.002-04:00

So Microsoft (as reported here and here) recently released a "cumulative security update" for IE that fixes its egregious memory leaks. Sounds great. Even if it takes a while to get everybody updated, at least the problem is fixed and we can all stop bending over backwards to work around this problem in our libraries, right.

Not So Fast

Let's have a look at the actual knowledge-base article to see exactly what it says:

"... a Web page that uses JScript scripting code, a memory leak occurs in Internet Explorer. When you visit a different Web page, the leaked memory is not released."

So far so good. It even references the original "circular-reference" knowledge-base article, implying that this is indeed what is fixed.

When I saw this article, I nearly spilled tea all over the keyboard. They really fixed this issue? You mean I can untangle all the painful code in GWT that works around this issue, diligently cleaning up all its circular DOM references under all sorts of circumstances?

Settle Down, Beavis

Before I got too excited, I had to do a little gut-check. Did they really go back and make it possible for their garbage collector to chase references through COM objects? That would be wonderful, but I'm not holding my breath.

And it's a good thing, because there's basically no way in hell they did that. In fact, it turns out that all they did was write a little code to sweep the DOM on unload and clean up all the extant circular references on those elements. This means that all elements not still attached on unload are still leaked, along with the transitive closure over all references Javascript objects. In even marginally complex applications, that means you're still going to leak like a bloody sieve!

I put together a little test script to show this in action. Have a look in any version of IE, and watch its spew memory!

I'm With Alex ...

... on this one. This is more like a bad joke than anything else. I recognize that fixing IE's memory leaks is a really complex problem, but the fact that it's not being done is still more evidence that Microsoft is abandoning IE, at least as far as any real progress is concerned. I just wish they would come out and say it.

In the Meantime

Don't go ripping out that memory-leak cleanup code. And keep checking for leaks (perhaps with Drip).

This Old Blog

2007-01-07T17:04:00.001-05:00

I think I may have broken the 'longest period of time between two blog posts' record, at roughly two years. The few people who remember it will probably be asking themselves, 'what the hell happened to it, anyway?'

Well, you may not be terribly surprised to learn that I took a job at Google, and have been incredibly busy in the intervening time, working on the Google Web Toolkit. Initially, I tried to keep up with the blog and related flood of random email, but it got to be a bit more than I had time to deal with, so I just decided to nuke it so I could concentrate. This worked, of course, but seemed to irritate a few people who saw a little value in some of the posts.

Now that I've got a little more time, I've decided to resurrect it. I kept copies of the old articles around, some of which I've re-posted. I apologize for the loss of the old comments -- some of them were really helpful, but they're really a pain to get back into Blogger (maybe I'll find a way to do this easily sometime).

I do plan on covering largely the same subjects, and please feel free to email me with questions or subjects you'd like me to cover.

Google Maps Information

2005-07-11T16:22:00.000-04:00

I've been getting a slow but steady stream of requests for more information on how to work with Google Maps. I would love to respond to each of these individually, but honestly haven't been doing much with it since I wrote my first few articles on the subject. Fortunately, I just ran across the Google Maps Mania blog. It seems to be doing a pretty good job of aggregating all of the stuff going on with Maps at the moment. I'm really quite amazed at the array of different things people are building with it (and I doubt there's any way I could keep up with it all anyway). Happy mapping to all!

Another Word or Two on Memory Leaks

2005-06-22T16:50:00.001-04:00

Ok, I promised to explain in more detail how to get rid of memory leaks once you've found them. Though I haven't had time to gather all of the information and examples I would have liked, I have run across a few external resources that might be of help.

The first of these is a new Microsoft Technical Article that discusses the various forms that IE memory leaks can take in some detail. Particularly interesting is the fact that it discusses an even more obscure type of leak that's not even a DOM element. It's definitely worth a read.

A bit more information on JavaScript closures can be found on Eric Lippert's blog (which I highly recommend) here.

For a nice, straightforward library that does an excellent job helping you avoid the problem altogether, take a look at Mark Wubben's Event Cache. I particularly like the fact that if you follow a simple set of rules, then you cannot easily leak elements.

On Another Note

I suggested earlier that the slowdown associated with leaking large amounts of memory in IE might be associated with hash tables or something similar getting full and therefore more inefficient. Eric Lippert left the following comment, which makes perfect sense to me and seems more likely to characterize the problem:

The symbol tables are very search-efficient. What's more likely is that the non-generational mark and sweep garbage collector is getting more and more full, and therefore taking longer and longer to walk each time a collection happens. A generational GC, like the .NET framework's GC, solves this problem by not GCing long-lived networks of objects very often.

And don't worry, I haven't forgotten about Drip at all. As time allows, I will be adding the features that I mentioned earlier. Of course, if anyone else wants to play with the source and make their own additions, please feel free!

Drip 0.2

2005-06-06T18:15:00.000-04:00

Happy Monday morning to everyone (or, depending upon where you may be, evening). This is just a quick note to announce Drip 0.2! Here is a quick list of changes in this version:

The main window is now resizeable.
The property list is sorted.
Property lists are now separate from the leak dialog. You can double-click on an element to see its properties. And you can double-click on any object property to see its properties. Think of it as a poor-man's expandable property list.
The source is also available here.

My current list of definitely known issues is as follows:

Still need to hook node.cloneNode() to catch all possible leaks.
Still need to hook new windows as they are created.
It sometimes reports that leaks are coming from about:blank rather than their actual source.

And my current list of possible issues is:

A couple of people have mentioned crashes occuring, which I have not yet been able to reproduce. If anyone having such a problem has a chance to build the source and catch this in a debugger, that would be wonderful.
I've also heard mention of issues with deeply-nested frames. My demo leak test page should exhibit this issue, but seems to work fine. Again, any help appreciated.

As always, please let me know of any other issues you discover, suggestions, and (even better) patches. And I haven't forgotten about my promise to provide a solid overview of how to deal with leak issues. I'm still doing a bit of research on the subject, but this will be forthcoming soon!

Drip Redux

2005-06-04T18:20:00.001-04:00

Wow. Thanks for all the excellent feedback on Drip. It was really just a tool that I needed for myself, but I'm glad that it may prove useful for others as well.

There were a lot of comments, both here and on Slashdot, so I'm going to try to put as many of my thoughts and responses as possible in this post. As such, it may be a bit of a grab-bag.

Exacerbating the problem

The first point I want to make is in response to one or two comments here, and many on Slashdot: That is, that I am not particularly concerned about whether or not I am exacerbating the problem by helping developers to "work around" IE's issues. Don't get me wrong; I find it just as unfortunate as everyone else that these problems exist in the first place. It is truly awful that developers using such a high-level tool as a web browser have to take memory allocation issues into account. Particularly given the fact that they're not really given the tools to effectively deal with them (window.CollectGarbage() doesn't count, since it won't really fix the problem).

Anyone who's spent a significant amount of time developing software has to realize that they will always be dealing with inadequacies of their tools and platforms. This has always been the case. It doesn't mean that vendors shouldn't fix their mistakes, but it does mean that you can't usually bitch at your customers for their choice of platform. If you are going to make software development your profession, then you must generally accept this responsibility. Certainly there are cases where you can dictate the details of the client's platform, but this is not the case for most vendors.

I also want to point out two things about this specific problem. First, IE's memory leak issues stem largely from the underlying model that allows scripting languages to interface with native COM objects (that is, making all objects accessible to scripting languages COM objects deriving from IDispatch). While imperfect, this model is also quite efficient -- and given that it was developed in the mid-90's, not an unreasonable compromise at the time. The second point I want to make is that IE is not the only browser with this problem. Mozilla had fairly severe memory leak issues until recently, and I've been told that Safari does as well. So let's not use this as an excuse to jump all over Microsoft.

When do leaks matter?

This is another point that I think bears some discussion. If you've spent a little time pointing Drip at existing sites, you've probably found that most sites exhibit no issues at all. This is simply because most sites simply don't use enough complex DHTML (with complex object graphs and the like) to create the specific sort of circular references that cause leaks. Most sites that do have a few leaks seem to be of PARAM objects passed to Java and/or Flash components. I've gotten mixed reports on when this happens, and when it causes a significant leak, so the jury's still out on whether this matters.

On the other hand, I saw one comment to the effect that Google Maps leaks a lot of elements. This is exactly the sort of application that is in danger of leaking enough to matter. If you look at the Maps code, you'll discover that they've done an excellent job of abstracting the components that comprise the application, and it's quite easy to follow (if you de-obfuscate it, anyway). And I believe that the fact that it leaks so much is actually an indication that its developers have done a good job. The problem is that the very abstractions that make a code base of that size manageable make it really easy to create leaks. Because there are a lot of references among all of its objects, and most DOM elements are wrapped in one way or another, even a single leak can cause the entire reference graph to leak. Nasty, huh?

How do I fix leaks?

This is a pretty complex question. So I've decided to punt this to a forthcoming post. There are a lot of resources out there on this subject, but I hope to gather as much of it as possible into one post so that I can provide a reasonable framework for finding and dealing with them.

What now?

I've gotten a lot of helpful suggestions and a couple of bug reports. What I would like to do now is to list all of the fixes and enhancements that I can think of, and solicit advice on how to prioritize them. Once I've had another pass at the code, I will release the source as well so that you can all help maintain it! This is my current list:

Deal with deeply nested frames. This is a real issue for a lot of sites -- apparently Drip only hooks one level of nested frames, but fails to hook deeper windows.
Hook the cloneNode() method. This is simply an oversight on my part, but it's necessary to catch all possible leaks.
Resizable window. This was just me being lazy. I've gotten really used to constraint-based layout in the Java world, and to be honest, I just didn't want to deal with doing this by hand in MFC.
Sorted and expandable element properties. 'Nuff said.
Hook new windows (via window.open). I think this is feasible, and will do my best.
Anything else you guys can think of!

Drip: IE Leak Detector

2005-05-31T18:02:00.001-04:00

To anyone still following this site, my apologies for taking a millenium or two between posts recently. Things have been a bit crazy of late, but I have something to introduce that will hopefully make up for the radio silence:

Drip -- an Internet Explorer leak detector

Over the last few months, a number of people have written to me or left comments asking questions about their memory leak issues with DHTML (or AJAX or whatever-you-want-to-call-it-this-week) applications. Unfortunately, there's not much I could offer in the way of advice that most people don't already know. Get rid of closures, unhook your event handlers, etc. This advice just isn't all that helpful when you've got a giant mess of JavaScript (often inherited) and visually detecting leak scenarios can be maddeningly subtle.

I did, however, find it quite surprising that no one had ever built a leak detector for Internet Explorer (or apparently for any other browser with leak problems; Mozilla has some, but they seem to be more for developers working on Mozilla itself, and the browser does a pretty good job of cleaning up leaks anyway). So I built one.

What it Does

It's a pretty simple application. Basically, it lets you open an HTML page (or pages, in succession) in a dialog box, mess around with it, then check for any elements that were leaked.

The interface is currently rather spartan. Here's what the main app looks like:

[Sorry, I lost the image somewhere along the way]

On the top you'll notice what looks like a crude version of Explorer's navigation bar. You've got the standard back and forward buttons, the URL box, and the 'go' button. These behave exactly as you might expect. To the right of it, however, is a 'check leaks' button, which will be grayed out when you first run the app. In order to try it out, you will first need to go to an HTML page (preferably one that you suspect leaks). The test page at [sorry I lost this page] will work. When you load this page, the 'check leaks' button will become enabled. Click it to see the following report:

[Yet again, I lost the image somewhere along the way]

This simple page leaks two DOM elements, a DIV and a BUTTON. These two elements are displayed in the top list, along with their source documents (useful if you've loaded more than one document between leak tests, or if you have more than one frame), the number of outstanding references on them, and their ID and CLASS attributes.

If you click on one, you'll see a list of its enumerable attributes in the bottom list. A particularly useful attribute for identifying the elements is 'innerHTML'.

Blowing Memory

Back to the main dialog for a moment. You might also have noticed the interestingly-titled 'blow memory' button. Its function is simple: to constantly reload a page as fast as it can, and to report the process' memory usage in the list box below. This is a helluva lot easier than pressing F5 for hours to determine how fast a page leaks memory.

How it Works

Fortunately, Internet Explorer's architecture made this app fairly easy to build. It's basically a simple MFC app with a browser COM component in it. The strategy for catching leaked elements is as follows:

When a document has been downloaded, sneakily override the document.createElement() function so that the application is notified of all dynamically-created elements.
When the document is fully loaded, snag a reference to all static HTML elements.
To detect leaks: navigate to a blank HTML page (so that IE attempts to release all of the document's elements),
force a garbage-collection pass (by calling window.CollectGarbage()),
and look at each element to see if it has any outstanding references (by calling AddRef() and Release() in succession on it).

Within the leak dialog, each element's attributes are discovered and enumerated using the appropriate IDispatch/ITypeInfo methods.

Caveats

This is basically an alpha release. The interface more or less blows, and I may have left glaring holes in the leak-detection strategy or in the code itself. It seems to work for me, but I would really like for anyone using it to keep an eye out for any problems so that I can fix them. And please don't hesitate to contact me, of course, if you have any ideas, praise, criticism, or even rants to offer. I really want this to help people to stop dealing with these god-awful leaks, and since Microsoft doesn't seem inclined to fix this design flaw, we can at least try to make it more bearable.

What Next?

Obviously, I would like any feedback I can get. There are definitely some interface quirks I need to iron out. And I would like to do more to help determine the actual cause of each leak. There are a few things that I would like to find out, and if anyone has any pointers, please share them:

Can you perform similar tricks with Safari/KHTML or Opera? (I know you can with Mozilla, but since it doesn't really leak much, that seems rather pointless)
Does anyone know if it's possible to enumerate variables on one of IE's JavaScript closures? (meaning the stack frame hanging off of the function reference)
How about enumerating expandos on IE DOM objects from C++? (I only seem to get built-in properties from ITypeInfo)

I'm sure other questions will come up in the near future. Oh, and I will be releasing the source before too long, as soon as I get a few things cleaned up.

Happy leak hunting!

More Maps

2005-04-07T09:38:00.001-04:00

This wasn't intended to be the Google Maps blog. Really. But hey, since they just released the Keyhole mode, I thought it might be worth going over the structure of the data.

Actually the integration of the Keyhole images is quite straightforward. The only things that had to change were (a) the functions that map between longitude/latitude pairs and pixel coordinates and (b) the tile URL generator.

The first of these is very simple. It would appear that the Maps team simply adhered to the coordinate system already in use by Keyhole, as it's completely different than the Maps coordinate system. The mapping functions are as follows:

// Initialize the zoom levels.
//
var gZoomLevels = new Array();
for (var zoom = 0; zoom &lt; 15; zoom++)
  gZoomLevels[zoom] = Math.pow(2, 25 - zoom) / 360;

// Compute the longitude and latitude for a given pixel coordinate.
//
function getLngLat(pixelX, pixelY, zoom) {
  return new Point(
    pixelX / gZoomLevels[zoom] - 180,
    180 - pixelY / gZoomLevels[zoom]
  );
}

// Compute the pixel coordinate for a given longitude and latitude.
//
function getPixelPos(longitude, latitude, zoom) {
  return new Point(
    (longitude + 180) * gZoomLevels[zoom],
    (180 - latitude)  * gZoomLevels[zoom]
  );
}

Nothing too surprising there. The part that seems to have people scratching their heads is the image URL format. At first glance, it appears to be a wacky series of characters with lots of 'q, r, s, and t'. Well, there is a method to this madness. First, have a look at the de-obfuscated function below:

// Compute the URL of the tile with the given coordinates.
//   (note that these coordinates are not the same as in the
//    two functions above:  they must be divided by the tile
//    size, which is 256).
//
function tileUrl(x, y, zoom) {
  var range = Math.pow(2, 17 - zoom);

  // Wrap-around x coordinate.
  //
  if ((x &lt; 0) || (x &gt; range - 1)) {
    x = x % range;

    // The mod operator isn't quite the same on a computer as it is
    //   in your math class (negative isn't handled correctly).
    //
    if (x &lt; 0)
      x += range;
  }

  // Build the quadtree path, working our way down from 2^16
  //   to the current zoom level.
  //
  var Ac = "t";
  for (var pow = 16; pow &gt;= zoom; pow--) {
    // Drop to the next zoom level.
    //
    range = range / 2;

    if (y &lt; range) {
      if (x &lt; range) {
        // Upper-left quadrant.
        //
        Ac += "q";
      } else {
        // Upper-right quadrant.
        //
        Ac += "r";
        x -= range;
      }
    } else {
      if (x &lt; range) {
        // Lower-left quadrant.
        //
        Ac += "t";
        y -= range;
      } else {
        // Lower-right quadrant.
        //
        Ac += "s";
        x -= range;
        y -= range;
      }
    }
  }

  return "http://kh.google.com/kh?" + "t=" + Ac;
}

Ok, so my comments were a bit of a giveaway. Basically, it looks like Keyhole stores its data in a quadtree structure, and the URL describes the 'path' through the tree to find a given tile. A quadtree, many of you may remember from your undergraduate graphics class, is a nice little structure for efficiently storing and accessing large tile arrays. It's particularly effective when not all areas need to be stored with the same level of detail (as is clearly the case with Keyhole).

I won't go into detail on the structure here, as others have already done a better job of explaining it (just do a Google search on 'quadtree'). For our purposes, suffice it to say that q, r, s, and t refer to the four quadrants at each depth in the tree. Thus, a sequence of these characters uniquely identifies a tile at some depth.

Ajax Buzz

2005-03-15T16:28:00.001-05:00

I've always found it quite interesting how giving something a name seems to make it "real". Case in point? AJAX. When I first [heard][adpativepath] this term, I thought to myself, "who really needs a specific term for a mishmash of technologies that's been around for a long time?" Well, as is often the case, I misunderestimated the importance of having a mental "handle" for an otherwise complex concept. And just like LAMP, it's not the specific technologies that are important (the 'P' in LAMP is heavily overloaded, just as the 'XML' in AJAX isn't as important as the idea of communicating directly with the server).

I don't know if I particularly care for the appelation -- particularly the XML bit -- but that no longer really matters. The name has probably stuck now that the WSJ has an article that opens with the words "Meet Ajax, the technology powerhouse." So it's settled, the concept has a name now.

And I believe it is a good thing that some kind of name has stuck. For some time now, I've found that everyone has their own ideas about what "rich" means to a web application (or if you're more into Flash, an internet application); and it just takes too long to try and explain "it's like the difference between Hotmail and Outlook".

So now that we have a name, and an "AJAX" application has a specific meaning, what do we do now? Certainly there is more than one way to approach the problem. Should I use some sort of framework, or bang out all of the Javascript by hand? How should I encode my server calls? How should I handle back button support? What about URL-encoding my application's state? There is a host of issues like these that need solutions (probably many solutions, depending upon your needs). It's now time for us to begin gathering the existing solutions to these problems, and to build new ones, so that we can move the Web far beyond its current state.

Should be fun!

Making the Back Button Dance

2005-02-12T16:23:00.001-05:00

It seems that I keep discovering nifty things about Google Maps. I didn't notice anyone commenting on the details of the way it interacts with the browser history, but there's one really groovy trick it plays that really adds to usability.We already know that clicking the back button causes it to display the results of your previous search. That's certainly helpful, as you don't lose your search history. If you play with it a bit, however, you may also notice that it also moves the map to your previous search location as well. This applies to all of your search history, as you move forwards and backwards amongst your results. Try it out.

But how?

If you dig through the DOM a bit (e.g. using Mozilla's DOM Inspector), you will see that there are three input fields in the hidden IFrame that the application uses to communicate with the server. At first glance, it doesn't appear that they're used for much of anything (I myself first dismissed them as an unfinished attempt to make the application state easily to link to). If you look at the application code, you'll see that it stores the current map state (latitude, longitude, and zoom level) in these fields every time it changes.

Here's the tricky part. When a search result comes back from the server, the HTML in which it's wrapped contains yet another set of three empty fields. When you click back, though, the browser replaces the IFrame contents with its previous state, including the values that were stored in these fields. You've probably seen this before in regular web applications, when the browser tries to maintain the state of forms when it goes back to a cached version.

So you've clicked the back button, the hidden IFrame contains its previous state, and the right panel now displays your previous search results. The application also reaches into these three fields to get the previous map state, and pans/zooms as necessary to display the map in its previous state as well (you'll find the code that does this in the application's loadVPage() method). Voila!

Reclaiming the back button

I believe that, as more developers build web applications that make good use of DHTML, we will find tricks like this to be invaluable in maintaining the user experience. Hopefully, users will be able to depend upon the browser history to work as advertised -- something we can't often say about most web apps these days.

Still more fun with maps

2005-02-11T16:06:00.002-05:00

Well, that was certainly an unexpected flood of responses. Apparently I wasn't the only one that found Google Maps interesting &emdash; I was amazed at some of the creative hacks that some commentors created. After sifting through this deluge, I decided to summarize some of the findings, clarify a few points, and add a few other comments on implementation details. This is kind of a grab bag of points, so please bear with me.

Cut Google some slack on Safari

I noticed a lot of people complaining both here and on Slashdot about the lack of Safari support. And I'm not completely unsympathetic, as I'm running a shiny new Mac Mini at home that I love. However, as anyone can attest that has ever tried to build an even remotely complex web application, it just ain't easy. And please don't blather on about who implements 'web standards' better &emdash; no one really implements them, and even if they did, you'd still be outta-luck if you wanted to do anything interesting in DHTML.

If you take some time to dig through Google's Javascript, you'll find that there is proto-Safari support all over the place. They're clearly working on it, and you really can't ask for much more than that.

The route overlay

There's one really interesting facet of the route display that I totally failed to notice the first time around &emdash; I was doing everything in Mozilla and simply didn't notice that they were actually using Microsoft's VML to render the route on IE. It may be non-standard, but you have to admit that it's very fast and effective! And switching off between client-side and server-side rendering in one code base is a pretty cool hack.

Decoding polylines and levels

Also because I only noticed the server-side route rendering the first time around, I failed to check whether the route's polylines were being decoded on the client. Well, as several commentors pointed out, they are. In fact, the decoding loop is fairly simple (just have a look at decodePolyline() for the details). I originally assumed this stream was encoded so that you could just grab it and send it back to the server for rendering (thus making the image server stateless, and the rendered route cacheable). However, since they're decoded on the client, it appears that it also served the purpose of keeping the size reasonable &emdash; encoding all those points as XML would get pretty fat.

I also glossed over the fact that there's another stream associated with the route called 'levels'. This is an interesting trick that allowed them to encode the route points at different zoom levels in the same stream (because there's really no opportunity to easily go back to the server for a new route when you change zoom levels &emdash; when you're rendering on the client).

Flow of control for form submit and IFrame

Although it's something of a wacky implementation detail, it's interesting to note how the search form at the top of the application works. It is actually contained in a FORM element, although it has three separate DIVs whose visibilities are swapped as you click on the different search links. However, it can't be submitted directly, as that would cause the entire application to reload. Instead, the event handler for the form's submit button suppresses the reload, gathers the search parameters, and calls the application's search() method. This method builds a query URL and sets a hidden IFrame's 'src' parameter, which causes it to gather a new chunk of XML from the server.

As I believe I mentioned in the previous article, requesting the XML via this IFrame has the additional benefit that it ties the browser's history perfectly to the application's state. Although it would be nice if someone would fix Mozilla such that the history titles are correct (this works properly in IE).

`asynchronousTransform()`

It turns out that Google Maps communicates with the server both through the hidden IFrame and the XMLHttpRequest object. I mentioned in the last article that it transforms the downloaded XML using XSL. Well, that XSL is not actually hard-coded into the application. Instead, whenever it needs to perform a transform, it requests the XSL via XMLHttpRequest, performs the transform, and caches the XSL itself so that it won't need to download it again.

Permalink and feedback

One of the potential downsides to building an application that runs entirely within a single page is that the address bar never changes, so it's not possible for the user to create links to the application's current state. Of course, many 'normal' web applications don't really work properly when you try to link to their internal pages, but people have still come to expect it to work most of the time.

Google's solution to this problem was to create the 'link to this page' anchor in the right panel. When you click on it, it refreshes the entire application with a URL that encodes the entire application state. Pretty nifty, as it gives you the important parts of the behavior everyone likes to call 'REST' without having to break the application up into a million little pieces.

You may have noticed that the 'feedback' link also encodes the application's state. The map application actually updates the hrefs of both of the stateful links every time the application state changes.

Profiler

Often you can tell quite a bit from code that is left lying around unexecuted. In this case, it appears that the Google Maps team may have had performance problems in some methods (or may simply have been trying to head them off). You can tell this because there are some prologue/epilogue functions being called in various methods that definitely smell like a hand-rolled profiler. And if you look at the list of methods that contain these hooks, it definitely makes sense:

Polyline.decodePolyline()
Polyline.decodeLevels()
Polyline.getVectors()
Page.loadFromXML()
Map.getVMLPathString()
Map.createRawVML()
Map.createVectorSegments()
Map.createImageSegments()
Map.drawDirections()

If this is indeed the case, I think it's worth noting that Mozilla's profiler actually does a reasonably good job. And although performance on one browser is not perfectly indicative of performance on the others, the Mozilla results have been roughly indicative of results on IE in my experience.

Tiles & longitude/latitude mapping

The mapping of tiles to longitude/latitude pairs is relatively straightforward. The code for doing transformations in both directions can be found in the functions getBitmapCoordinate(), getTileCoordinate(), and getLatLng(), and several commentors have picked apart the transforms in more detail. As mentioned before, the tiles' image source URLs encode the longitude, latitude, and zoom level.

Several commentors also suggested that the entire map was pre-rendered at every zoom level, so that the web server could simply deliver the tiles without further consideration. While I believe this is partially true, I also am fairly certain that some areas will be viewed far more often than others. Clearly, Google is working from vector data at some level, and it would probably make far more sense to render tiles on the fly and caching them. This would also make a big difference when it came to dealing with updates to the vector data, especially if those updates could be localized such that the entire tile cache need not be invalidated.

Crazy 'bookmarklet'

Finally, I have to give kudos to those who've been working on the 'bookmarklet' that reaches into the running application and makes it dance. It's completely novel to me that you can add bookmarks of the form 'javascript:' and have them run in the context of the current page. It makes perfect sense, of course &emdash; I just never thought of it. It appears that the current state of the art of this hack can be found here.

The only unfortunate part about this (through no fault of the authors') is that it's likely to be brittle in the face of updates to Google Maps &emdash; the Javascript has to reach into global variables within the running application, which will probably change when Google's code obfuscator is run. It does give us a glimpse of a possible future, however, when even web pages publish public API's for developers to use. Very interesting!

Mapping Google

2005-02-09T09:29:00.001-05:00

By now, many of you will have gone and tried out the new Google Maps application. By and large, you have to admit that it's pretty damned slick for a DHTML web application -- even my wife was impressed, and that's not easy with geek toys. So, in the spirit of Google Suggest and GMail, I've decided to have a quick peek under the hood to figure out what makes it tick.

Not quite like GMail

The first thing I noticed is that it doesn't quite work like GMail. Whereas GMail uses XMLHttp to make calls back to the server, Google Maps uses a hidden IFrame. Each method has its benefits, as I'll discuss below, but this difference of approach does seem to imply that it may not be the same team doing the work.

The Graphics

Probably the most striking thing about Google Maps is the very impressive (for DHTML, anyway) graphics. Now, I'm sure that many of you old JavaScript hacks out there have known this sort of thing was possible for a long time, but it's very cool to see it (a) actually being used for something real, and (b) where normal users will see it.

For those to whom the implementation is less than obvious, here's a quick breakdown. The top and side bars are (more or less) simply HTML. The center pane with the map, however, is a different beast. First, let's address the map itself. It is broken up into a grid of 128x128 images (basically like an old tile-based scrolling console game). The dragging code is nothing new, but the cool trick here is that each of these images is absolutely positioned -- and the 'infinite' scrolling effect is achieved by picking up tiles that are off-screen on one end and placing them down on the other end. The effect is kind of like laying track for a train by picking up track from behind it.

Google map, with tiles outlined

The push-pins and info-popups are a different matter. Simply placing them is no big trick; an absolutely-positioned transparent GIF does the trick nicely. The shadows, however, are a different matter. They are PNGs with 8-bit alpha channels. Personally, I didn't even realize you could depend upon the browser to render these correctly, but apparently (at least with IE6 and Mozilla), you can. And they actually render pretty quickly -- for proof, check out the overlaid route image (at the end of the article), which is often as big as the entire map view.

The pushpin, with its two images outlined

Communicating with the Server

There are two ways in which Google Maps has to communicate with the server. The first is to get map images, and the second is to get search results. It turns out that getting map images is remarkably easy -- all you have to do is set an image tile's URL. Because the coordinate system is known and fixed (each tile represents a known area specified in longitude and latitude, at a given zoom level), the client has all the information it needs to set tile URLs. Each tile URL is of the following form:

http://mt.google.com/mt?v=.1&x={x tile index}&{y tile index}=2&zoom={zoom level}

I'm not sure what the 'v' argument specifies, but it never seems to change. The others are fairly self-explanatory. One nice side effect of this is that the images have fixed URLs for a given chunk of the earth's surface, so they get cached. If you're doing most of your searches in one region, then the app can be quite snappy once everything gets cached.

Doing searches is another matter. Clearly, you can't 'submit' the entire page, because that would destroy your map and other context. Google's solution is to submit a hidden IFrame, then gather the search results from it. Let's say, for example, that you simply wanted to go to Atlanta. You type 'Atlanta' in the search area, and the following HTTP GET is made:

http://maps.google.com/maps?q=atlanta&amp;z=13&sll=37.062500%2C-95.677068&sspn=37.062500%2C80.511950&output=js

There are a couple of things to notice here. The 'question' is passed in the 'q' parameter (much like Google). The other arguments are 'z' for zoom, 'sll' for longitude &amp;amp;amp;amp;amp; latitude (your current focus, I believe), and 'sspn' to specify the span/size of your viewing area. What's interesting is what comes back:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="content-type" content="text/html; charset=UTF-8"/>
    <title>Google Maps - atlanta</title>
    <script type="text/javascript">
    //<![CDATA[
    function load() {
      if (window.parent &amp;& window.parent._load) {
        window.parent._load({big chunk of XML}, window.document);
      }
    }
    //]]>
    </script>
  </head>
  <body onload="load()">
    <input id="zoom" type="text" value=""/>
    <input id="centerlat" type="text" value=""/>
    <input id="centerlng" type="text" value=""/>
  </body>
</html>

This HTML is loaded into the hidden IFrame which, when loaded, will punt a big chunk of XML back up to the outer frame's _load() function. This is kind of a cool trick, because it saves the outer frame from having to determine when the IFrame is done loading.

I mentioned before that there was some advantage to be had by using a hidden IFrame over making direct XMLHttp requests. One of these is that the IFrame's state affects the back button. So every time you do a search, it creates a new history entry. This creates an excellent user experience, because pressing the back button always takes you back to the last major action you performed (and the forward button works just as well).

Big Hunks of XML

Ok, so now the outer frame's code has a big chunk of XMl. What can it do with that? Well, it turns out that Google Maps depends upon two built-in browser components: XMLHttpRequest and XSLTProcessor. Oddly enough, even though it doesn't use XMLHttpRequest for making calls to the server, it does use it for parsing XML. I'll get to the XSLT later.

Here's an example of the XML response that comes back from the 'Atlanta' request above:

<?xml version="1.0"?>
<page>
  <title>atlanta</title>
  <query>atlanta</query>
  <center lat="33.748889" lng="-84.388056"/>
  <span lat="0.089988" lng="0.108228"/>
  <overlay panelStyle="/mapfiles/geocodepanel.xsl">
    <location infoStyle="/mapfiles/geocodeinfo.xsl" id="A">
      <point lat="33.748889" lng="-84.388056"/>
      <icon class="noicon"/>
      <info>
        <title xml:space="preserve"></title>
        <address>
          <line>Atlanta, GA</line>
        </address>
      </info>
    </location>
  </overlay>
</page>

Nothing surprising here -- we have a title, query, center & span, and the location and name of the search result. For a slightly more interesting case, let's look at the response when searching for 'pizza in atlanta':

<pre>
<?xml version="1.0" ?>
<page>
  <title>pizza in atlanta</title>
  <query>pizza in atlanta</query>
  <center lat="33.748888" lng="-84.388056" />
  <span lat="0.016622" lng="0.017714" />
  <overlay panelStyle="/mapfiles/localpanel.xsl">
    <location infoStyle="/mapfiles/localinfo.xsl" id="A">
      <point lat="33.752099" lng="-84.391900" />
      <icon image="/mapfiles/markerA.png" class="local" />
      <info>
        <title xml:space="preserve">Kentucky Fried Chicken/Taco Bell/<b>Pizza</b> Hut</title>
        <address>
          <line>87 Peachtree St SW</line>
          <line>Atlanta, GA 30303</line>
        </address>
        <phone>(404) 658-1532</phone>
        <distance>0.3 mi NW</distance>
        <description>
          <references count="9">
            <reference>
              <url>http://www.metroatlantayellowpages.com/pizzaatlanta.htm</url>
              <domain>metroatlantayellowpages.com</domain>
              <title xml:space="preserve">Atlanta<b>Pizza</b> Guide-Alphabetical Listings of Atlanta<b>...</b></title>
            </reference>
          </references>
        </description>
        <url>http://local.google.com/local?q=pizza&near=atlanta&amp;amp;amp;amp;amp;amp;amp;latlng=33748889,-84388056,11825991348281990841</url>
      </info>
    </location>
    { lots more locations... }
  </overlay>
</page>

Again, nothing too surprising when you think about the data that's going to show in the map pane. But how do the results get shown in the search result area to the right? This is where things get a little wacky. The JavaScript actually uses the XSLTProcessor component I mentioned earlier to apply an XSLT to the result XML. This generates HTML which is then shown in the right panel. We've come to expect this sort of thing on the server, but this is the first time I've ever seen it done on the client (I'm sure it saves Google lots of cycles, but personally I didn't even know XSLTProcessor existed!)

Driving Directions

There's one last case to discuss, and that's driving directions. This works just like other searches, including XSLT to show the results, with one exception: the result XML includes a tag that two opaque values encoding the geometric route to be taken. This data appears to be base 64 encoded (or something similar, anyway). Remember the giant transparent PNG I mentioned earlier for rendering routes? This data is used to render that sucker. The data looks like this:

<polyline numLevels="4" zoomFactor="32">
  <points>k`dmEv`naOdGC??EtD??@|DAxL??hEFjJ@ ...</points>
  <levels>BBB???BB?BB??@??@?????BB??@?????@? ...</levels>
</polyline>

This polyline data is then used to request the route PNG from the server using a URL like so:

http://www.google.com/maplinedraw?width=324&height=564&path=sRS?k@fB@?}As@e@CGAIA}@BwCEu@Bs@?E_@cACS@a@PaC ...

The route overlay

In Summary

That's about it. I hope that demystifies this application a bit; the real magic, of course, is all the work going on to enable this on the back-end. The fact that Google's servers can handle all of these images requests, route finding, line drawing, searches and the like so quickly is the real magic. I also want to point out that their map renderer (or the one they purchased) works much better than all the other ones I've seen on Mapquest, Mapblast, and the like. That alone makes it worth using, if only so you can actually read the map!

I also think it bears noting that Google is pulling out all the stops to build rich web apps, no matter how weirdly they have to hack the browser to make them go. And I strongly believe that this is a trend that is here to stay -- XHTML Strict/CSS/etc be damned. At the end of the day, what really matters to users is compelling apps that let them get their work done quickly.

DHTML Leaks Like a Sieve

2005-01-02T16:55:00.001-05:00

Most web browsers leak memory like a bloody sieve

You heard me: Like a sieve. Gobs and gobs of memory. Necessarily. "Gee, that's funny", you might say, "My browser doesn't seem to leak noticably". And you're probably right. However, the design of both major browsers (Internet Explorer and Mozilla) leaks memory necessarily (To be honest, I'm not sure about Safari and Opera, but it wouldn't surprise me).

Let's take a moment to think about that "necessarily" part. What I mean by this is that these browsers are not poorly implemented (I'm not going to pass judgment on that), but rather that their design leads inexorably to memory leaks. The reason you don't usually see this when browsing is that (a) most individual pages are simple enough so as not to exhibit the leak and (b) the few sites that use truly heavy JavaScript often work very hard to get around these leaks.

If you've ever built a really complex site using lots of JavaScript, you've probably seen this problem. You may even have some idea of where it comes from. Well, I'm writing this explanation because (a) I think I fully understand the problem and (b) there are a lot of confused (or simply wrong) explanations out there.

The Joy of Automatic Garbage Collection

The problem is not JavaScript. Nor is it really the DOM. It is the interface between the two. JavaScript uses (sometime after Netscape 2.0, I think) a fully garbage-collected memory allocator. For anyone who doesn't understand this, this simply means that memory can never be truly leaked, even when objects reference each other circularly (e.g. A->B->A). Both Internet Explorer and Mozilla are built on roughly similar component models for their native object layer (i.e. the DOM). Internet Explorer uses the native windows COM model, while Mozilla uses a very similar XPCOM model. One of the things these two models have in common is that objects allocated within them are not garbage collected &emdash; they are reference counted. Again, for those unfamiliar with the vagaries of memory management systems, this means that objects might not get freed if they take part in a circular reference (as above).

Now the designers of these browsers have gone to some trouble to keep their COM layers (I'll refer to both as COM for simplicity) from leaking during normal usage. If you're careful, this is not too difficult &emdash; you simply have to be vigilant about potential circular references and use various hacks to refactor them out of existence. And of course their JavaScript garbage collectors can't really leak at all. Where things start to go sour is when you have circular references that involve both* JavaScript objects and COM objects. Let me use an example to illustrate this point. Let's say you have a JavaScript object 'jsComponent' with a reference to an underlying DIV. And the DIV contains a reference to the jsComponent object. It might look something like this:

var someDiv = document.getElementById('someDiv');
jsComponent.myDomObject = someDiv;
someDiv.myComponent = jsComponent;

What's wrong with this? What basically appears to happen is that jsComponent holds a reference to someDiv. In a reference-counted memory manager, this means that it has a reference count of at least 1, and thus cannot be freed. Now someDiv also holds a reference to jsComponent (because jsComponent cannot be freed if it is still accessible via someDiv, or things could go really bad). Because COM objects cannot truly participate in garbage collection, they must create a 'global' reference to myComponent (I'm not sure what the actual implementation looks like under the hood, because I haven't dug through the source for either browser, but I imagine it's similar to the semantics of Java's createGlobalRef() JNI call). Thus begins the deadly embrace: someDiv's reference count will stay at 1 as long as jsComponent is not freed, but jsComponent will not be freed until someDiv drops its global reference to it. Game over: that memory is irretrievable without human intervention.

At this point, you might be asking yourself how common circular references of this sort really are. First, I would argue that they ought to be relatively common, because building any sort of reusable component framework in JavaScript requires this sort of structure to tie the component and DOM layers together. However, there are many schools of thought on this subject, and if that were the only problem, it wouldn't be so bad. However, there are two very common cases that make this problem much more notable.

Event Handlers

Perhaps the most common manifestation is in DOM event handlers. Most event handlers take the form " onclick='this.doSomething()' ". This doesn't really pose a problem. However, if the event handler references a JavaScript object in any way (as in the aforementioned component scenario), then it serves as a back-reference. This is why, in many posts and articles I've read about avoiding memory leaks, the statement "don't forget to unhook all of your event handlers" is often made.

Closures

A much more subtle (and therefore nasty) situation where circular references occur is in JavaScript closures. For those not familiar with the concept, a closure binds stack variables to an object created in a local scope. You may well have used them before without realizing it. For example:

function foo(buttonElement, buttonComponent) {
  buttonElement.onclick = new function() {
    buttonComponent.wasClicked();
  }
}

At first glance, it may appear that this method of hooking events on a button avoids the circular reference problem. After all, the button's 'onclick' event doesn't directly reference any JavaScript object, and the button element itself contains no such reference. So how does the event find its way back to the component? The answer is that JavaScript creates a closure that wraps the anonymous function and the local variables (in this case, 'buttonElement' and 'buttonComponent'). This allows the code in the anonymous function to call buttonComponent.wasClicked().

Unfortunately, this closure is an implicitly created object that closes the circular reference chain containing both the JavaScript button component and the DOM button element. Thus, the memory leak exists here as well.

So Now What?

Unfortunately, there really is no easy way around this problem. If you want to build complex reusable objects in JavaScript, you are probably going to have to deal with this and some point. And don't feel tempted to think "It's probably not that bad; I'll just ignore it" -- neither Internet Explorer nor Mozilla free these objects even after a page is unloaded, so the browser will just blow more and more memory. In fact, I first noticed this problem in my own work when I saw IE blowing around 150 megabytes of memory!

The only real option I know of is to be extremely careful to clean up potential circular references. This can be a little tricky if you're writing components for others to use, because you have to ensure that they call some cleanup method in the 'onunload' event. But at least by understanding the root cause of the problem, you have at least some hope of getting your leaks cleaned up before your users start complaining!

One Further Note

When I said at the beginning of this article that the design of most web browsers necessarily leaks, I was probably making too strong a statement. While their reference-counting and mark-and-sweep garbage collection implementations do not "play well" together, there is lots of research on this subject out there, and I'm sure a way could be found to fix this problem without throwing away most of the implementation.

The Insanity of HTTP Compression

2004-12-20T16:39:00.003-05:00

If you've dealt with HTTP much, you've probably at least heard that it supports gzip compression. And under some circumstances, this even turns out to be true! You might think that supporting something as simple as decoding gzip-encoded content would be simple and straightforward, and you'd be right (especially given that gzip code has been available freely since, well, about forever).

It seems, however, that people working on most major browsers at various points found ways to make this difficult. It would be one thing (albeit a silly thing) if they simply didn't support gzip encoding, but it's another matter entirely that a number of browsers request encoded content which they then proceed to barf on. There are lots of articles out there describing, in varying degrees of detail, the mess that is HTTP compression. IBM has a good one.

The Specific Problem

Myself, I don't have much cause to worry about this, except for one very specific scenario: various difficult-to-discern versions and patches of Internet Explorer do not cache compressed content correctly. Case in point: if you reference an external .js file that IE then caches, it will usually screw it up the second time you hit the page. It appears that what's happening is that it somehow forgets the full size of the compressed .js file in its cache, truncating the decompressed .js file to its compressed size. Needless to say, this is not exactly conducive to your script actually working at all.

I don't know about you, but I've seen some pretty damned big external scripts out there (think hundreds of kilobytes, uncompressed), and it would be a real waste to not be able to compress these things. But no matter how hard I tried, I was never able to reliably detect the versions of IE that do and do not handle this correctly (and to make matters worse, the most commonly deployed versions don't, so it's kind of moot if you want to see any real-world benefit).

My Wacky Solution

But I'm going to share a trick with you. It's really not pretty, but quite functional in practice. If you want to compress external scripts reliably, what you need to do is wrap 'em up in HTML and shove 'em into an IFrame. I see by that incredulous look on your face that you think this is a strange idea. Doesn't this mess with my window references? You bet it does, but if you make them all parent references, then everything works out just fine.

Basically, all you have to do is embed an IFrame in your HTML, like so:

<iframe id="__scriptFrame" style="display: none;" src="bigAssScript.js">

Then you can access functions in your IFrame like so:

var scriptFrame = document.getElementById('__scriptFrame');
scriptFrame.contentWindow.foo();

There are two caveats that spring to mind when doing this. First, you can't set your parent window's event handlers from within the external script. However, this is easily fixed by creating a method within the outer HTML that allows the external script to set these handlers:

function setWindowOnResize(handler) {
  window.onresize = handler;
}

The other caveat is that you need to ensure that the IFrame is done loading before you try to access any methods within it. This is also relatively easy to fix: use the IFrame's onload handler to handle any startup code you need to run. This simply avoids the problem, because this event will not fire until the IFrame is done loading -- and the IFrame won't finish loading until after the outer window is done loading.

I do realize that this is a really strange solution, but once you implement it, it's pretty easy to maintain, and most importantly it lets you compress those giant scripts, usually to about 1/5 of their original size. That can be a pretty significant bandwidth savings!

To give you an idea of the kinds of savings we're talking about, one of my own external scripts was compressed from 140,769 bytes to 29,057 bytes, for a compression ratio of nearly 80%. If you consider the fact that external .js files almost never get compressed normally, this will add up quickly.