Wednesday, June 4, 2008

Design Patterns vs GWT Compiler: Round 1, Fight!

I've spent a lot of time maximizing performance of GWT code, and in doing so, I've tended to shy away from using too much OOP and Design Patterns, but the question is, is this fear justified? You've heard the GWT team continually tell you that you can have your abstractions without much performance loss, but is it true? It turns out, in many cases, the answer is a resounding yes.

Take for example, the Iterator pattern. I've crafted GwtQuery to iterate over native arrays, because I feared the overhead of iterators. But if you're careful in how you use the type system, the overhead turns out to be approximately, zero.

For example:


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

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

private class StringArrayIterator implements Iterator {

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();
}
}
}

used as

MyArray m = new MyArray();
for(String s : m)
Window.alert(s);

The generated Javascript is

var m, s, s$iterator;
m = $MyArray(new MyArray());
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);
}

As long as GWT can type-tighten the Iterable interface to the concrete implementing class, this output will usually hold true. The following will break the optimization and impose polymorphic dispatches:

public void onModuleLoad() {
MyArray m = new MyArray();
MyArray2 m2 = new MyArray2();
iterate(m);
iterate(m2);
}

public void iterate(Iterable m) {
for(String s : m)
Window.alert(s);
}

Here we introduce a new type, MyArray2, and we use an iterate() method which invokes the Iterable interface. Since GWT now has two classes in existence which implement Iterable<String>, it can't decide whether it has a MyArray or MyArray2, and therefore can't elide the iterator. You might ask, what happens if we remove MyArray2, but keep the iterate() method? We return to optimal code:

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);
}
}


Neat huh? If you're curious, try the same thing with Delegation, Decorator, Facade, or Flyweight, I think you'll be pleasantly surprised.

Fatality!, GWT Compiler. :)
-Ray

1 comment:

Bruce Johnson, Engineering Manager said...

Nice writeup, Ray! We want to make it ever more true that GWT rewards sound software construction with better performance.

I'm happy with where we are, to be sure, but it's also exciting to think that we're only scratching the surface with the current compiler optimizations. For example, I really hate seeing the "s$iterator.items.length" in the loop test (vs. caching it in a local var). I think we can probably generate a temporary to cache it in many cases where it can be proved safe.

More in the realm of vaporware -- but too exciting not to mention -- are a set of optimizations we've been kicking around to address the example you used of having multiple class implementing Iterable. It seems like function cloning combined with the type tightening we already do could allow us to inline the same function differently for different call sites. It's quite like C++ templates at that point, though it would just happen magically.

We also have a related idea about doing
"per-instance" optimizations, tentatively called "type sharding". This would let you optimize with the knowledge of invariants for one given class of instances of a class. It would reward you for having mostly immutable object state after construction because it could optimize methods for one particular instance with the knowledge of the immutable state. Hard to explain, but promises to be really cool. We can talk about it more on the GWT Contributors list if you're interested.