11.4 Optimizing Queries

Other than accessing and updating elements of collections, the most common thing you want to do is query the collection. Let's look at some examples of tuning collection queries.

11.4.1 The Query Problem

First, we'll start with a problem. I'll use a list (indexable collection) of strings as my collection. For the query I'll use a simple test that checks whether any particular string includes one of a set of specified substrings, and the query will simply return the count of how many strings include those substrings. For example, the list might be:

"code"
"rode"
"load"
"toad"
"road"

and the query might be, "How many strings in the list contain the substrings "od" or "lo"?" (The answer for that particular query would be 3 for this example list.)

For my actual collection, I'll generate multicharacter strings using the lowercase characters of the Latin alphabet (a to z). For example, a collection of all four-character strings generated in this way would produce a collection of 26 x 26 x 26 x 26 = 456,976 four-character strings. I'll simply query this collection for the count of strings that contain any of the substrings "ie" or "xy" or "pq". I've elected to use a Vector object to hold the collection for the start of the tests; I've also 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 tuning. The query is representative of the types I've seen in applications.

The simple, straightforward version of the query is:

    int count = 0;
    for(int i = 0; i < collection.size(  ); i++)
    {
      if(    ( ((String) collection.get(i)).indexOf("ie") != -1 )
           | ( ((String) collection.get(i)).indexOf("xy") != -1 )
           | ( ((String) collection.get(i)).indexOf("pq") != -1 ) )
        count++;
    }
    return count;

Several standard optimizations immediately leap out at me. There's the unnecessarily repeated method call in the loop test (collection.size( )); the use of the normal boolean-OR operator (|) rather than the shortcircuit boolean-OR operator (||); and the repeated String cast in the query. All of these are standard targets for optimization in loops (see Chapter 7). However, just because they are "standard" optimizations doesn't mean we should apply them all immediately without testing their effects. So let's test them.

11.4.1.1 Applying the Boolean-OR operator optimization

Shortcircuit boolean operators are discussed in more detail in Chapter 7. Basically, these operators avoid evaluating their right-hand side if their left-hand side provides a conclusive result. I change the query block to use the shortcut operator:

      if(     ( ((String) collection.get(i)).indexOf("ie") != -1 )
           || ( ((String) collection.get(i)).indexOf("xy") != -1 )
           || ( ((String) collection.get(i)).indexOf("pq") != -1 ) )

The shortcircuit booleans speed up the test slightly in most cases (see test2 in Table 11-2).

11.4.1.2 Eliminating the unnecessarily repeated method call

To avoid repeating the method call in the loop test, we can simply replace:

    for(int i = 0; i < collection.size(  ); i++)

with:

    int max = collection.size(  );
    for(int i = 0; i < max; i++)

Again, this optimization speeds up the test slightly in most cases (see test3 in Table 11-2). Combining the two optimizations gives the best results for most of the VMs (see test4 in Table 11-2).

11.4.1.3 Eliminating casts and extra access calls

Let's push on and try eliminating the unnecessary String casts. This is done simply by holding the first casted object in a variable of the appropriate type:

    String s;
    for(int i = 0; i < max; i++)
    {
      if(     ( (s = (String) collection.get(i)).indexOf("ie") != -1 )
           || (                                s.indexOf("xy") != -1 )
           || (                                s.indexOf("pq") != -1 ) )

Eliminating the cast also naturally eliminates the associated get( ) access call, as the object is held in the extra variable. With this change, all the VMs show their best times yet with significant speedups. I've included the results of testing with all the optimizations together (test5 of Table 11-2) and also without the size( ) call elimination (test6), as that optimization proved ineffective for the 1.2.2 VM.

11.4.1.4 Avoiding synchronization

We have been using a Vector object to hold the collection so far. 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 using an ArrayList object instead of the Vector object we initially used. The code does not otherwise change. The results of testing the optimizations so far, together with the change to an ArrayList collection object, are listed in test7 of Table 11-2. Once again, we see the best times yet for all the VMs.

11.4.1.5 Avoiding the method accessor

Another standard optimization is to avoid repeatedly using a method accessor to access elements of a collection if it is possible to access the elements directly in some way. For collection queries, this can be achieved simply by implementing the query in the collection class. For the example here, we could manage this by implementing our own java.util.List class and implementing the query in that class, thus gaining access to the internal collection. There is, however, a quicker possibility. Vector is implemented with its internal element collection defined as protected, so we can subclass Vector to gain access to the internal element collection and implement the query in our subclass as in the following code.

class TestList
  extends Vector
{
  public int customQuery(  )
  {
    int count = 0;
    String s;
    for(int i = 0; i < elementCount; i++)
    {
      if(     ( (s = (String) elementData[i]).indexOf("ie") != -1 )
           || (                       s.indexOf("xy") != -1 )
           || (                       s.indexOf("pq") != -1 ) )
        count++;
    }
    return count;
  }
}

The equivalent of the original test is now:

    return collection.customQuery(  );

The results of this test are shown in test9 of Table 11-2. Almost all the VMs show this is now the fastest test.

11.4.1.6 Tighter typing of the collection elements

Another fairly obvious optimization is to reimplement the collection using an underlying String[ ] array to hold the elements (see the Section 6.4 in Chapter 6 and the Section 11.1 earlier in this chapter). The results for this are listed in test12 of Table 11-2, showing the fastest query times for all the VMs.

11.4.1.7 Optimizing map queries

I've performed a similar optimization exercise for Maps (see http://www.javaworld.com/javaworld/jw-11-2000/jw-1117-optimize.html). The results were very similar. Perhaps the only surprise was that the Enumeration implementation for Hashtable was more efficient than the Iterator implementation. Remember, also, that you can iterate the elements just as in this exercise by using a counter loop instead of asking the Enumeration/Iterator whether there are more elements on each loop iteration:

  Enumeration enumeration = map.keys(  );
  Object o;
  //no need to call Enumeration.hasMoreElements(  ) in each iteration
  //since we can get the size of the map and use that value to count.
  for (int size = map.size(  ); size > 0; size--)
  {
      o = enumeration.nextElement(  );
      ...
  }

^[8] Note that some intermediate tests (test8, test10, and test11) are included in the example code but not included in this table.