Optimize a query on a Map

Comparing techniques for performance tuning a query on a Map class

In "Optimizing a query on a collection", I considered how to optimize a query on an indexable collection. However, optimizing queries on Map classes turns out to be more complicated. In this article, I'll provide an example of how you can speed up bottlenecks consisting of Map queries.

The query

First I'll start with the problem. I'll use strings as keys for my collection. For their corresponding values, I'll simply use integer objects to indicate some value object. For the query, I'll use a simple test that checks whether any particular string key includes one of a specified substrings set, and the query will simply return the summation of the integer values for those string keys, which include the substrings. For example, the Map might be:

  • key -> value
  • "code" -> 1
  • "rode" -> 2
  • "load" -> 3
  • "toad" -> 4
  • "road" -> 5

The query in that case might be "sum of the values for those string keys in the map that contain the substrings od or lo" (the answer would be 1+2+3=6 for this example list).

For my actual keys, I'll generate multicharacter strings by using lowercase letters (a to z). For example, a collection of all four-character strings would generate a collection of 26 x 26 x 26 x 26 = 456976 four-character strings. The values will simply be an integer counter that increments by one as each string is added to the Map. I'll query that Map for the summation of integer values for those strings that contain any of the substrings ie, xy, or pq. I've elected to use a Hashtable object to hold the collection for the start of the tests.

I've chosen to use an easily generated collection for the data and a straightforward query to avoid any application-specific distractions. I want to focus on the tuning here. The query represents many query types I've seen in applications, though a more representative test would return the value collection for the keys that satisfy the query. I've opted for the summation to avoid generating too many collections in my tests.

The simple straightforward version of the query is:

    int count = 0;
    Enumeration enumeration = map.keys();
    String s;
    while(enumeration.hasMoreElements())
    {
      s = (String) enumeration.nextElement();
      if(     ( s.indexOf("ie") != -1 )
           || ( s.indexOf("xy") != -1 )
           || ( s.indexOf("pq") != -1 ) )
      {
        count += ((Integer) this.get(s)).intValue();
      }
    }
    return count;

For the tests, I'll use the Sun virtual machines (VMs) from the Java SDK 1.2 and 1.3. In addition, I'll test with the HotSpot VMs delivered with those two SDKs -- HotSpot 1.0 and 2.0. I'll also test one non-JIT VM, which in this case will be the 1.2 VM with the JIT turned off. You can easily turn off the JIT by setting the java.compiler property to NONE:

  java "-Djava.compiler=NONE" ...

Avoid synchronization

As I said earlier, I started by using a Hashtable object to hold the map. In most applications, bottleneck queries tend to be read-only or single-threaded. In either case, you can normally use a nonsynchronized object to hold the collection. To do so here requires a simple change to using a HashMap object instead of the Hashtable object I initially used. In addition, I need to change the code to use an iterator, as HashMap does not support an enumerator. In fact, I really shouldn't have used the enumerator in the original query since the Map interface does not support its use.

The query now reads as the following:

    int count = 0;
    Iterator iterator = map.keySet().iterator();
    String s;
    while(iterator.hasNext())
    {
      s = (String) iterator.next();
      if(     ( s.indexOf("ie") != -1 )
           || ( s.indexOf("xy") != -1 )
           || ( s.indexOf("pq") != -1 ) )
      {
        count += ((Integer) this.get(s)).intValue();
      }
    }
    return count;

However, the test (test2 in Table 1 below) does not change the query time very much. A couple of the VMs even register slower times. That looks slightly odd to me and, looking back at what I've done, I noticed that I've been a little naughty. I made two changes to the code and tested those changes together without determining whether either change individually speeds up the query time. I changed the class and changed the enumerator to an iterator. I should really check each change separately.

My first concern is that the iterator is accessed via a Set of Map elements. I would have a real performance problem if the Set were a whole new collection with all the elements copied from Map. But the Set implementations of the JDK Map classes are actually alternate views of the underlying collection, and so they should not cause any adverse performance impact for this query.

Table 1: Percentage of Speed Increase in Query Time for Each Optimization Test, Relative to the 1.2 JIT VM Test
Test1.2 JIT VMHotSpot 1.0 2nd run*1.3 JIT VMHotSpot 2.0 2nd run*1.2 non-JITTest details
test1100%129%134%125%985%Hashtable with enumerator
test298.1%129%135%124%1104%HashMap with iterator
test3108%131%138%125%1187%Hashtable with iterator
test491.5%125%124%118%1001%replaced .hasNext() call in test2
test5120%131%134%126%1009%use Map.Entry Set view
test683.0%107%102%99.1%727%query in Map class
test778.1%103%105%102%720%specialized Map class of String keys and int values
test877.7%73.3%104%69.7%697%specialized Map class of char[] keys and int values
test919.4%18.7%22%18.5%111%specialized Map class of four-char keys and int values
test108.7%12.0%11.4%10%82.3%perfect minimum hashing on four-char keys and int values

NOTE: HotSpot VMs run methods in interpreted mode until the HotSpot VM profiler decides that the method is better run natively compiled. The method is then natively compiled with extensive optimizations applied to it. For the test runs here, some methods were optimized by the second test run, but not until the third test run were the HotSpot optimizations fully applied to the test by the VM. Consequently, I show the results of the first and third test runs in the HotSpot VMs.

The process of testing the two changes individually is straightforward: simply use a Hashtable with the iterator. The test result (test3 in Table 1) is very illuminating. Test3 clearly shows that enumerators are faster than iterators for the Maps I've reviewed here, and that is probably true for other JDK classes. The slower iterators combined with the faster nonsynchronized HashMap class balanced each other out to give test2's mixed results. Unfortunately, we don't have the option of using the faster nonsynchronized HashMap together with the faster enumerators.

Eliminate the repeated Iterator.hasNext()

Let's move on with performance tuning. The next obvious optimization is to eliminate the repeated Iterator.hasNext() call in the for loop test. You already know how many elements there are, so you don't need to ask if there are more.

This is a simple change. You can replace:

    while(iterator.hasNext())

with:

    for (int size = map.size(); size > 0; size--)

The test results are in test4 of Table 1. I've stuck with the HashMap and the iterator for test4, so test2 is the previous directly comparable test. The results show that the optimization is unequivocally better for all VMs. But my overall tuning effort so far shows only a small improvement.

Avoid the repeated Map.get() call

As with the last optimization, you can eliminate another method call, the Map.get() call. That call is used to get the value for the keys that satisfy your query.

You can eliminate the Map.get() call because Map classes support a set view that contains key-value pairs, obtained from the Map.entrySet() method. The elements of that set are java.util.Map.Entry objects, so you can access the value objects directly after you query the keys. The query code now looks like this:

    int count = 0;
    Iterator iterator = this.entrySet().iterator();
    String s;
    Map.Entry entry;
    for (int size = this.size(); size > 0; size--)
    {
      entry = (Map.Entry) iterator.next();
      s = (String) entry.getKey();
      if(     ( s.indexOf("ie") != -1 )
           || ( s.indexOf("xy") != -1 )
           || ( s.indexOf("pq") != -1 ) )
      {
        count += ((Integer) entry.getValue()).intValue();
      }
    }
    return count;

Unfortunately, the test results (test5 in Table 1) show that change to be unambiguously bad for performance. Although the idea of replacing the Map.get() call with a quicker data member access is nominally good, you unfortunately have to replace it with two method accesses and an extra cast that swamp any advantages you may have gained. That optimization should be immediately discarded.

Avoid the method accessors

A standard optimization for queries on collections is to reimplement the query in the collection class so that you can avoid having to repeatedly access elements through accessor methods. Unfortunately, JDK Map classes that define their internal elements as protected do not exist, so you cannot just subclass an existing Map and add the query. Instead, you need to create your own Map class. But that is not a large problem since many examples of hash map classes with source code are available (from the JDK and the Web).

To define the query, you need to know how a hash map holds its elements internally. I'll use a standard implementation similar to HashMap from the JDK for my class. This element storage algorithm is not too difficult:

  1. Obtain an index from the key. The easiest way to do this is to use the key object's hashcode and modulo it by the size of the internal collection.
  2. Use the index to insert the element into the internal collection. Since the index could be the same for multiple objects, that location in the internal table is actually a node of a linked list, and the key and corresponding value is added as the last node of the list.

So the internal structure is an array of linked list nodes, with each node holding a key and value. Now you can define your query within the class:

    //hold the internal table in a local for slightly faster access
    //Test6MapEntry is the name of my linked list node class
    Test6MapEntry tab[] = table;
    int counter = 0;
    String s;
    //Run through the elements of the internal array
    for (int i = tab.length ; i-- > 0 ;)
    {
      //The current element could be null or a node. If it is a node
      //you have at least one entry at this index. There could be several
      //entries, and you need to iterate through all the nodes in the
      //list at this index.
      for (Test6MapEntry e = tab[i] ; e != null ; e = e.next)
      {
        //the key is Test6MapEntry.key
        s = (String) e.key;
        if(   ( s.indexOf("ie") != -1 )
           || ( s.indexOf("xy") != -1 )
           || ( s.indexOf("pq") != -1 ) )
        {
          //the value is Test6MapEntry.value
          counter += ((Integer) e.value).intValue();
        }
      }
    }
    return counter;

The results of the test are shown in test6 of Table 1. All the VMs show that test6 is clearly the fastest test. Implementing the query in the collection class is usually an optimization to aim for with any collection query.

Specialize your custom Map class

Now that you have your own Map implementation, you can specialize the implementation for your query. The most obvious change you can make is to move from general Object key value pairs to data types more appropriate to your problem.

In the example here, you can specialize to String keys and int values. However, that requires quite a few changes to your Map class. You can maintain backward compatibility with the Map interface if necessary by wrapping specialized methods with generalized ones.

  public Object get(Object key)
  {
    return new Integer(get((String) key));
  }
  public int get(String key) {....// the real get method

The query now has the advantage of eliminating a couple of casts and a method call:

    Test7MapEntry tab[] = table;
    int counter = 0;
    String s;
    for (int i = tab.length ; i-- > 0 ;)
    {
      for (Test7MapEntry e = tab[i] ; e != null ; e = e.next)
      {
        s = e.key;
        if(   ( s.indexOf("ie") != -1 )
           || ( s.indexOf("xy") != -1 )
           || ( s.indexOf("pq") != -1 ) )
        {
          counter += e.value;
        }
      }
    }
    return counter;

The results of the test are shown in test7 of Table 1. The HotSpot 1.3 VMs do not gain any advantage from the optimization. That may reflect the aggressive speculative optimizations that HotSpot can apply, which could have resulted in HotSpot already avoiding the casts in test6.

You can also specialize the class further to holding char[] array keys, which further improves performance times (test8 of Table 1). That optimization requires extra work since you need to implement the String methods, hashCode(), and includes() for your char[] arrays.

Further nonstandard optimizations

The previous sections showed fairly standard optimizations that you can apply to most queries on Maps. There are further nonstandard optimizations that you can apply, which are highly dependent on the nature of the map's data. I'll continue the tuning discussion to show two optimizations of that type.

1 2 Page
Recommended
Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more