GWT Collections emulation library performance pitfall

Update : check also this question on StackOverflow for a discussion on GWT performance practices and this very nice post summing things up in regards to GWT performance tuning

Intro

Lately we've been using GWT (Google Web Toolkit) at Rento for a hot new project and at some point we came across a performance bottleneck on a specific function. This function had to be called from every 200ms to every 1s and it was taking from 20ms in Chrome and Safari (totally acceptable) to 1200ms in IE7 & IE8 (orders of magnitude beyond unacceptable!).

At first, when we saw these numbers we started pulling our hair out (once again) with IE's amazing performance, but then, what the heck, this graph says it all and we were ready to pay the price of supporting IE once again. So we just had to optimize this code somehow. With a first glimpse the bottleneck was a for loop with about 1000 iterations. Makes sense...

CS basics

Computation time is one of the two main criteria when measuring algorithm complexity (the other being space, aka memory). Definition :

It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm.

When you want to reduce the computation time for an algorithm (that contains iterations, as is usually the case) you have the following options :

• Reduce the number of iterations
• Reduce the computation time inside every iteration

Step 1: Reducing the number of iterations

For the given problem that the algorithm was trying to solve the number of iterations could not be easily*  reduced (where easily means implementing an optimal algorithm in a small amount of time and without bloating the code base). We did some best-case-scenario optimizations but most of the time we didn't actually hit it and additionally the worst one was still unacceptable. There were one or two possible solutions though in case part two (see below) wouldn't work.

Step 2: Reducing the computation time inside the loop

Inside each iteration (among other stuff) a normalization of a string was taking place. This computation looked pretty innocent since it was taking usually less than one ms (we couldn't get an exact value since it was too small) each time it was called. The problem though with repetition is that this phenomenally small amount of time adds up on big iterations and thus by simply caching the result of the normalization and re-using it on future calls, saved us about 500ms on IE (Chrome, Safari and Firefox didn't have a problem anyway). Not bad at all! But still we had about 700ms to cut!

Not enough! Digging deeper

At this point we started scratching our heads and thinking that maybe we should go back to step 1 and actually implement the aforementioned complex algorithms but the gut feeling was "no, there's something else wrong here". After all what was happening inside each iteration step was the normalization (which was out of the game now) and 2-3 checks (conditions, regular expressions and so forth) that shouldn't be that complex anyway.

What a better place to start than the profiler on the "javascript vm" that the code was actually running : Internet Explorer 8. Thank God, IE8 comes with the best profiler out there (yes, I do prefer it among all the others like firebug's and Chrome's). You can see the call tree and since IE's JavaScript engine is the slowest one you can really nail the problems :D

So, back on the profiler and now that the normalization was out we could see more clearly that something was probably wrong with the iterations themselves. A "getIterator" (or something like that) was taking about 90% of the time. Could it be the Set we were using on the Java side? Good hypothesis, now we needed proof!

Benchmarking GWT Collections emulation

After spending some time setting up a dummy stupid-simple GWT project for benchmarking the emulation library for the Collections java api we had our results:

Results for initializing various collections with 1000 elements inside :

	Test	IE 7	Chrome	FF 3.6

Array initialization 0 ms 0 ms 0 ms ArrayList initialization with initial capacity 0 ms 0 ms 3 ms ArrayList initialization without initial capacity 0 ms 0 ms 3 ms ArrayList initialization from Arrays$ArrayList 16 ms 0 ms 0 ms ArrayList initialization from ArrayList 0 ms 0 ms 0 ms ArrayList initialization from class LinkedList 0 ms 0 ms 3 ms ArrayList initialization from HashSet 47 ms 0 ms 9 ms ArrayList initialization from LinkedHashSet 16 ms 0 ms 4 ms ArrayList initialization from TreeSet 62 ms 0 ms 7 ms LinkedList initialization from Arrays$ArrayList 31 ms 0 ms 3 ms LinkedList initialization from ArrayList 31 ms 0 ms 2 ms LinkedList initialization from LinkedList 16 ms 0 ms 2 ms LinkedList initialization from HashSet 62 ms 0 ms 8 ms LinkedList initialization from LinkedHashSet 32 ms 0 ms 4 ms LinkedList initialization from TreeSet 78 ms 2 ms 7 ms HashSet initialization with initial capacity 16 ms 0 ms 4 ms HashSet initialization without initial capacity 15 ms 1 ms 3 ms

HashSet initialization from Arrays$ArrayList 32 ms 1 ms 4 ms HashSet initialization from ArrayList 31 ms 0 ms 5 ms HashSet initialization from LinkedList 16 ms 0 ms 4 ms HashSet initialization from HashSet 110 ms 2 ms 10 ms HashSet initialization from LinkedHashSet 47 ms 1 ms 7 ms HashSet initialization from TreeSet 78 ms 2 ms 9 ms LinkedHashSet initialization from Arrays$ArrayList 63 ms 2 ms 11 ms LinkedHashSet initialization from ArrayList 78 ms 1 ms 11 ms LinkedHashSet initialization from LinkedList 62 ms 2 ms 11 ms LinkedHashSet initialization from HashSet 109 ms 2 ms 16 ms LinkedHashSet initialization from LinkedHashSet 79 ms 2 ms 12 ms LinkedHashSet initialization from TreeSet 109 ms 3 ms 15 ms TreeSet initialization from Arrays$ArrayList 563 ms 51 ms 103 ms TreeSet initialization from ArrayList 547 ms 35 ms 128 ms TreeSet initialization from LinkedList 593 ms 32 ms 118 ms TreeSet initialization from HashSet 609 ms 44 ms 94 ms TreeSet initialization from LinkedHashSet 672 ms 32 ms 742 ms TreeSet initialization from TreeSet 672 ms 37 ms 85 ms

Test IE 7 Chrome FF 3.6 Native array iteration 0 ms 0 ms 0 ms ArrayList iteration 16 ms 0 ms 2 ms LinkedList iteration 16 ms 0 ms 1 ms HashSet iteration 78 ms 1 ms 6 ms LinkedHashSet iteration 31 ms 0 ms 3 ms TreeSet iteration 62 ms 2 ms 7 ms HashMap iteration around *keys* 63 ms 0 ms 6 ms HashMap iteration around *values* 78 ms 1 ms 6 ms LinkedHashMap iteration around *keys* 15 ms 0 ms 3 ms LinkedHashMap iteration around *values* 47 ms 1 ms 5 ms

Bullseye! Using anything else other than native arrays (which translate to native JS arrays on the compiled JS source) has a tremendous overhead on IE!

Step 3: Reducing the *iterator* time!

With the results of the benchmarks at hand we refactored the code to use and iterate around old-plain-c-like arrays. Not nice in the Java world (for example you can not append things on the fly, you can not declare them final since you don't know exactly the size of them, etc, etc) but the result was worth it on speed terms : from 1200ms on IE it is now taking about 20-100ms (depending on the case). Yes, we can now move on with our lives...

Conclusions

I was rather disappointed with GWT at this point. You are supposed to be using it instead of pure JavaScript so it can be optimized on each browser and so you can use the wealth of tools in the Java ecosystem. In this particular case we had none of the two, quite the opposite I must say. From now on and until the GWT team finds a better way to implement the Collections API we should should think twice before writing List in our declarations...