GWT HashMap: FastStringMap No More

June 5th, 2009 Damon Lundin Posted in GWT | 2 Comments »

In my last post about using HashMaps in GWT, I concluded that you would be better of using the FastStringMap that is part of GWT.  I decided to re-run my tests now that GWT 1.6 has been released to see what we get.  The bottom line is that you can now use a HashMap and stop using the FastStringMap.

First, a note: I actually re-run my tests against GWT 1.5 and for some reason I was unable to reproduce the numbers I had previously obtained.  I used the same hardware and the same version of GWT, but my browser versions have been updated since then.  Perhaps something has changed since then or perhaps there was an error in my tests, but I’m afraid I can’t explain it.

But on to my new tests…

I wrote a test that does 10,000 puts and gets (of 100 different keys) for each of 7 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.  We also have a LonNoPreviousFastStringMap which re-implements put and remove so that they always return null; this avoids the need for the code to execute another get to fetch the previous value which is usually not used by the caller.

The seven 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<Object> map3 = new LonFastStringMap<Object>();

4) Using FastStringMap but use the Map<Object, Object> interface.  This will cause the code to execute a type check to make sure you’re passing in a String.

Map map4 = new LonFastStringMap();

5) Using FastStringMap but use the Map<String, Object> interface

Map<String, Object> map5 = new LonFastStringMap<Object>();

6) Using a FastStringMap that does not return the previous value when doing a put.

LonNoPreviousFastStringMap<Object> map6 = new LonNoPreviousFastStringMap<Object>();

7) Using a FastStringMap that does not return the previous value when doing a put, but using the Map<String, Object> interface.

Map<String, Object> map7 = new LonNoPreviousFastStringMap<Object>();

The results for each of these are (all in ms):

(IE6)
1) 452
2) 466
3) 407
4) 1064
5) 1059
6) 255
7) 890

(IE7)
1) 499
2) 468
3) 407
4) 1141
5) 1126
6) 233
7) 938

(FF3)
1) 186
2) 187
3) 158
4) 573
5) 613
6) 82
7) 901

As you can see, using the FastStringMap (Test 3) does still perform marginally better than a HashMap (Tests 1 and 2) but nowhere like the numbers I received previously.  I think the difference is small enough that it is no longer worth the extra code required.  Using the generic Map<Object, Object> interface is still the slowest option which incurs the type check on the FastStringMap.  I was surprised by Tests 5 and 7 which use the Map<String, Object> interface against a FastStringMap, but it seems that even though the type indicates it’s a String map, it’s still incurring the type check of the FastStringMap.  This means that if you want to use a FastStringMap, you should use the FastStringMap interface and never a Map interface.

The one test that still shows that the FastStringMap is significantly faster (almost twice as fast as the HashMap) is Test 6 where we have an implementation that does not return the previous value when calling put or remove.  If you have an application that does a lot of puts and removes, then you might wish to consider continuing to use the FastStringMap.  If your app does mostly gets, than I think the difference is small enough that it’s worth sticking with the standard HashMap.  And of course, as GWT gets faster, I’m sure using a HashMap will get faster too.

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;
    double elapsed6 = 0;
    double elapsed7 = 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<String, Object> map1 = new HashMap<String, Object>();
    Map map2 = new HashMap();
    LonFastStringMap<Object> map3 = new LonFastStringMap<Object>();
    Map map4 = new LonFastStringMap();
    Map<String, Object> map5 = new LonFastStringMap<Object>();
    LonNoPreviousFastStringMap<Object> map6 = new LonNoPreviousFastStringMap<Object>();
    Map<String, Object> map7 = new LonNoPreviousFastStringMap<Object>();

    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.put(s, someObject);
            map5.get(s);
        }
        elapsed5 += (Duration.currentTimeMillis() - start);

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

        start = Duration.currentTimeMillis();
        for (int count = 0; count < 10000; count++) {
            String s = strings[count % 100];
            map7.put(s, someObject);
            map7.get(s);
        }
        elapsed7 += (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);
   JSConsole.writeMessage("elapsed6=" + elapsed6);
   JSConsole.writeMessage("elapsed7=" + elapsed7);