26 September 2010

GWT ArrayList, HashSet and JsArray Benchmark

The performance of GWT applications varies quite a bit between the developer (hosted) mode and the compiled JavaScript code, as well as between different browsers. This blog post describes a benchmark [ Run Benchmark, Source Code ] of two different collection classes (ArrayList, HashSet) in three different environments (Chrome 6, Firefox 3.5, Dev Mode). It tests the add, contains and iterator methods, and also compares the collection classes to a lightweight JavaScript array wrapper.

The three benchmarks do basically the following:
  • The add benchmark adds 100 items to an empty collection.
  • The iterator benchmark iterates over an collection of 100 items.
  • The contains benchmark checks if 20 items are contained in a collection of 100 items. 10 of those items are contained in the collection, and another 10 are not.
Each benchmark is run 2500 times (see GWTBenchmark class).

The results I report here are rough averages from repeated measurements (~20 times) on a Core 2 Duo 2.4 GHz machine with 4GB ram, running Windows 7 64bit and GWT 2.0.3. They should be accurate with about +/- 10% error.
6.0.472.63 beta
Dev Mode
(FF 3.5.13)
add - ArrayList19 ms550 ms14 ms
add - HashSet200 ms680 ms30 ms
add - JsArray14 ms540 ms142000 ms
iterator - ArrayList44 ms395 ms12 ms
iterator - HashSet138 ms1220 ms8 ms
contains - ArrayList4700 ms8500 ms37 ms
contains - HashSet23 ms110 ms6 ms
contains - JsArray8 ms36 ms26500 ms

Several things can be observed based on these results:

Measuring and optimizing performance in the developer mode is useless and can be dangerous. The developer mode is very different from running compiled GWT code in the browser. Code that is executed only within the Java VM tends to be a lot faster. Manipulation of the DOM and calling JavaScript using JSNI, however, is much slower (see also GWT developer guide). I was surprised by the extent of this effect, for example that Java collections are up to 125 times faster than GWT compiled code on Chrome 6 (ArrayList.contains), or that JsArray.contains is 736 times faster when compiled and run on Firefox 3.5 vs. in the developer mode on Firefox 3.5.

Chrome 6 is much faster than Firefox 3.5. This result is pretty obvious given recent browser benchmarks. However, the differences vary depending on the collection type and operation. ArrayList.contains is surprisingly slow on Chrome 6.

The different collection classes have different advantages. This is also pretty obvious given their different requirements and algorithms. The HashSet is slow for add and iterate, but fast for checking the containment of items. It also assures that each element is only contained once. The ArrayList is much faster than the HashSet when calling add and iterate, but also 200 times (Chrome 6) / 77 times (Firefox 3.6) slower when it comes to containment checks, which was surprising.

Potential speed gains when using handcrafted collection classes. The results for the JsArray class indicate that there is a potential for speed improvements by using lightweight collection classes. This finding is different from a benchmark that used bubble sort. The difference might be related to the overhead added by the GWT cross-compilation of ArrayList and HashSet.

In conclusion, when having performance issues in GWT applications that use a large number of collection instances, it might be worth looking at using optimized collection classes that reduce the overhead introduced by ArrayList and HashSet.


Poetro said...

Don't know the reason for comparing an old version of Firefox with the most recent version of Chrome. It doesn't seem fair. It would even be better with the most recent stable version of Firefox which is 3.6.10

lgrammel said...

@Poetro This is a good point. The original goal of the benchmark was to carve out the magnitude of the differences between HashSet, ArrayList and a lightweight implementation. I still use FF 3.5 because I had some issues with the Google plugin on FF 3.6 when it originally came out, which might be resolved by now. You can get the values for any browser by going to the page linked above ("run benchmark") with that browser and running the benchmark for yourself. Be aware, however, that this might cause some browsers (e.g. IE8) to freeze.

Paul said...

Thinkpad T400s

Chrome 6.0.472.63:
ArrayList.add = 49.25ms
HashSet.add = 201.75ms
JsArray.add = 36.14ms
ArrayList.iterator = 75.5ms
HashSet.iterator = 167ms
ArrayList.contains = 6270ms
HashSet.contains = 24ms
JsArray.contains = 27ms

Firefox 3.6.10:
ArrayList.add = 387.25ms
HashSet.add = 648ms
JsArray.add = 454.75ms
ArrayList.iterator = 336ms
HashSet.iterator = 1097.5ms
ArrayList.contains = 7430ms
HashSet.contains = 119ms
JsArray.contains = 56.25ms

Iexplorer9 beta
ArrayList.add = 142.25ms
HashSet.add = 553ms
JsArray.add = 222ms
ArrayList.iterator = 353.5ms
HashSet.iterator = 1203.25ms
ArrayList.contains = 4275.25ms
HashSet.contains = 117.25ms
JsArray.contains = 48ms

All these numbers are averages of 4-10 measurements for each test

lgrammel said...

Thanks Paul, that's awesome!

FF 3.6 seems to quite a bit faster than 3.5 (when taking the Chrome 6 results to adjust for the differences between my T61p to your T400s), and that IE9 is roughly in between Chrome 6 and FF 3.6, with some tests running faster than on Chrome 6 (e.g. ArrayList.contains).

Looking at all those results, I am wondering why ArrayList.contains is so slow across browsers, and if there are other methods like that.

Daniel Kurka said...

Nice blogpost about the performance of GWT Collections. I was on the way to do this myself. Saved me some time there :)

id said...

> I am wondering why ArrayList.contains is so slow across browsers

Easy answer: As every Collection ArrayList uses equals() to test.
This can be pretty expensive depending on the object.
So for primitive types where using === in js is sufficient your code will be faster while it will break for other types.
HashSet.contains is faster than ArrayList.contains because ... it is optimized for it.

lgrammel said...

@id I agree that this will definitely explain some of the differences. However, given that ArrayList.contains is 6 times slower than HashSet.contains in a JVM, but 40-80 times slower in a browser, I would not jump to the conclusion that the poor performance of ArrayList.contains can solely be explained by the equals method without looking at it more closely.

Atul Sharma said...

I don't know enough about GWT but why not use 'return new Array()' or just 'return []' instead of 'return new Object();'
The 'length' can not be correct if 'Object' is used.

Lars Grammel said...

Nice catch - yes it should be 'return [];' in JsArray.create().