Fast string concatenation in GWT

November 15th, 2009 Alex Moffat Posted in EffectiveGWT, GWT | No Comments »

What’s the fastest way to concatenate strings in GWT? I’m interested in this question because when you really need speed the fastest way to build an HTML UI is to create all the HTML as a giant string in one go and insert it using innerHTML. We do this in Blueprint when we’re redrawing diagrams in response to user actions because we need enough time to compute the new layout as well do the actual rendering. In addition the browser we have to worry about most is IE6 as it’s the slowest. The rest of the UI is build with standard GWT widgets as they are more than fast enough.

I benchmarked three techniques for performing string concatenation using GWT.

1. Using a StringBuilder to construct the HTML for a UI “component” and then appending that to another StringBuilder to create the complete data.
2. Using a single StringBuilder and directly appending the HTML for each UI “component” to that builder.
3. A technique developed by Damon that takes advantage of knowledge about what sorts of strings we’re building.

First, GWT StringBuilder. This is a pretty cool class. If you look at the GWT 2.0 source in gwt-user-jar you’ll see that internally it uses an instance of a StringBufferImpl class to perform all of the low level operations, which are basically just append and replace. This instance is created using GWT.create so that different implementations can be provided at compile time depending on the browser. In EmulationWithUserAgent.gwt.xml a default implementation of StringBufferImplAppend is selected and this is overridden with StringBufferImplArray for IE6, 7, and 8. StringBufferImplAppend just uses += to append new data to a string and substring to implement replace. StringBufferImplArray implements append by adding to a JavaScript array containing the appended strings, this is converted to a string using the JavaScript join method. Replace is implemented by converting to a string and then using substring as StringBufferImplAppend does. I would say you’re not going to be able to beat the performance of this class for general string concatenation operations.

However, Damon’s technique is faster in some situations and those situations are interesting when building HTML. It takes advantage of the fact that the strings we’re building are of the form “constant” + “variable” + “constant” + “variable” etc. For example “<div id=” + idValue + “><img src=” + srcValue + “/></div>”. What you do is create an array containing the constant strings leaving gaps for the variable values. The array is then reused each time a string is needed by filling in the gaps with the variable values and then using join to create the string.

 // Fill out a constant array. Generally done in the constructor. array is a JavaScriptObject
 array = createArray(5) // createArray is jsni method
 int index = 0;
 setArrayValue(array, index++, "<div id="); // setArrayValue is jsni method array[index] = value;
 index++; // leave gap for idValue
 setArrayValue(array, index, "><img src=");
 index++; // leave gap for srcValue
 setArrayValue(array, index, "/></div>");

 // Later on use the array multiple times to create strings
 array[1] = idValue;
 array[3] = srcValue;
 String htmlString = arrayToString(array); // joinArray is jsni method using join to create string

For the test I used the array technique to create the HTML for a component and then appended to a StringBuilder.

And now the numbers. I measured IE6, IE7 and IE8 using Windows running as a guest in VMWare. Safari, the two versions of Firefox and Google Chrome were measured using OS X. Therefore you can’t really compare between IE and non-IE browsers using these numbers, what’s interesting is how the different techniques compare for each browser. The time taken to run each concatenate technique 2000 times was recorded. In a single test run each technique was executed 20 times with the executions of all the techniques randomly ordered. This was done to try and prevent the timing of garbage collection runs always impacting the same technique. Finally I did 10 test runs for each browser and calculated the average values. Times are in milliseconds.

For the IE line using Damon’s array technique is about twice as fast as the nearest competitor, direct append to a StringBuilder. For other browsers it’s slower so to get the best results a little GWT create magic is required to choose an appropriate class at compile time depending on the browser being targeted.