Performance of the GWT 1.5 HashMap

October 10th, 2008 Damon Lundin Posted in GWT | 10 Comments »

In my recent presentation at the Google I/O conference on writing high performance GWT code, I mentioned that for improved performance, you should consider replacing all usages of a HashMap with String keys with the GWT FastStringMap instead since the FastStringMap performs better.  Well, I recently decided to rerun my analysis on the new release of GWT 1.5 to see if the new compiler was able to make the same optimizing when you use generics to indicate the map contains String keys.  In short, it does not and using the FastStringMap is still much faster.

I wrote a test that does 10,000 puts and gets (of 100 different keys) for each of 5 cases and then repeated that 10 times to avoid any bias where the first case might run faster than a later one.

Before I list the cases, two notes: the LonFastStringMap in my examples below is just a class that extends FastStringMap to make it public.  It also adds a putNoPrevious method that returns void and executes a put just like the FastStringMap does but then doesn’t execute the get to return the previous value (since in most cases, the return value gets thrown away).

The five cases I tried are:
1) Java 1.5 generic version

Map<String, Object> map1 = new HashMap<String, Object>();

2) Java 1.4 version using HashMap but no generics

Map map2 = new HashMap();

3) Using FastStringMap

LonFastStringMap map3 = new LonFastStringMap();

4) Using FastStringMap, but using the Map interface instead of the FastStringMap interface.  This causes each put and get to execute the (Object, Object) methods which incur a type check before calling the (String, Object) methods.

Map map4 = new LonFastStringMap();

5) This one is the same as 3, but it calls putNoPrevious instead of put.

LonFastStringMap map5 = new LonFastStringMap();

The results for each of these are:

(IE6)
1) 2265ms
2) 2250ms
3) 577ms
4) 1596ms
5) 327ms

(IE7)
1) 2247ms
2) 2221ms
3) 547ms
4) 1591ms
5) 285ms

(FF3)
1) 715ms
2) 821ms
3) 138ms
4) 1142ms
5) 85ms

As you can see, using the FastStringMap is dramatically faster than a HashMap.  Using the Map interface (which incurs that type check) is quite a bit slower but still faster than the HashMap.  And finally, there’s a moderate advantage to using putNoPrevious instead of put.

Here’s the code I used to do the test.

        double elapsed1 = 0;
        double elapsed2 = 0;
        double elapsed3 = 0;
        double elapsed4 = 0;
        double elapsed5 = 0;

        String[] strings = new String[100];
        Object someObject = new Object();

        double start = Duration.currentTimeMillis();
        for (int index = 0, len = strings.length; index < len; index++) {
            strings[index] = "Test " + index + " Value";
        }
        double init = (Duration.currentTimeMillis() - start);

        Map map1 = new HashMap();
        Map map2 = new HashMap();
        LonFastStringMap map3 = new LonFastStringMap();
        Map map4 = new LonFastStringMap();
        LonFastStringMap map5 = new LonFastStringMap();

        for (int iter = 0; iter < 10; iter++) {
            start = Duration.currentTimeMillis();
            for (int count = 0; count < 10000; count++) {
                String s = strings[count % 100];
                map1.put(s, someObject);
                map1.get(s);
            }
            elapsed1 += (Duration.currentTimeMillis() - start);

            start = Duration.currentTimeMillis();
            for (int count = 0; count < 10000; count++) {
                String s = strings[count % 100];
                map2.put(s, someObject);
                map2.get(s);
            }
            elapsed2 += (Duration.currentTimeMillis() - start);

            start = Duration.currentTimeMillis();
            for (int count = 0; count < 10000; count++) {
                String s = strings[count % 100];
                map3.put(s, someObject);
                map3.get(s);
            }
            elapsed3 += (Duration.currentTimeMillis() - start);

            start = Duration.currentTimeMillis();
            for (int count = 0; count < 10000; count++) {
                String s = strings[count % 100];
                map4.put(s, someObject);
                map4.get(s);
            }
            elapsed4 += (Duration.currentTimeMillis() - start);

            start = Duration.currentTimeMillis();
            for (int count = 0; count < 10000; count++) {
                String s = strings[count % 100];
                map5.putNoPrevious(s, someObject);
                map5.get(s);
            }
            elapsed5 += (Duration.currentTimeMillis() - start);
        }

        JSConsole.writeMessage("init=" + init);
        JSConsole.writeMessage("elapsed1=" + elapsed1);
        JSConsole.writeMessage("elapsed2=" + elapsed2);
        JSConsole.writeMessage("elapsed3=" + elapsed3);
        JSConsole.writeMessage("elapsed4=" + elapsed4);
        JSConsole.writeMessage("elapsed5=" + elapsed5);