Featured White Papers

• Java Web Hosting | DailyRazor.com - Over 10yrs Of Java Web Hosting Exp!

Sponsored Links

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

Optimize a query on a Map

Comparing techniques for performance tuning a query on a Map class

By Jack Shirazi, JavaWorld.com, 11/01/00

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.