Faster List Iteration with RandomAccess Interface

10/24/2001

Java SDK version 1.4, due out later this year, introduces a new java.util.RandomAccess interface that has no methods. What is the purpose of this interface?

What does RandomAccess mean?

RandomAccess is a marker interface, like the Serializable and Cloneable interfaces. All of these marker interfaces do not define methods; instead, they identify a class as having a particular capability.

In the case of Serializable, the interface specifies that if the class is serialized using the serialization I/O classes, then a NotSerializableException will not be thrown (unless the object contains some other class that cannot be serialized). Cloneable similarly indicates that the use of the Object.clone() method for a Cloneable class will not throw a CloneNotSupportedException.

The RandomAccess interface identifies that a particular java.util.List implementation has fast random access. A more accurate name for the interface would have been FastRandomAccess. This interface tries to define an imprecise concept: how fast is fast? The documentation provides a simple guide: if repeated access using the List.get() method is faster than repeated access using the Iterator.next() method, then the List has fast random access. The two types of access are shown in the following code examples:

Object o;
for (int i=0, n=list.size(); i < n; i++)
  o = list.get(i);
Object o;
for (Iterator itr=list.iterator(); itr.hasNext(); )
  o = itr.next();

There is a third loop that combines the previous two loops to avoid the repeated Iterator.hasNext() test on each loop iteration.

Object o;
Iterator itr=list.iterator();
for (int i=0, n=list.size(); i < n;!
 i++)
  o = itr.next();

This last loop relies on the normal situation, where List objects cannot change in size while they are being run without an exception of some sort occuring. So, since the loop size remains the same, you can simply count the accessed elements without testing at each iteration whether the end of the list has been reached. This last loop is generally faster than the one in Example 2. In the context of the RandomAccess interface, the first loop using List.get() should be faster than both of the loops that use Iterator.next() for a list to implement RandomAccess.

How is RandomAccess used?

So now that we know what RandomAccess means, how do we use it? With the other two marker interfaces, Serializable and Cloneable, there are two aspects to using them:

• Defining classes which implement them, and
• Using their capabilities via ObjectInput/ObjectOutput and Object.clone().

RandomAccess is a little different. Of course, we still need to decide whether any particular class implements it, but the possible classes are severely restricted: RandomAccess should only be implemented in java.util.List classes. And most such classes are created outside of projects; e.g., the SDK provides the most frequently used implementations, and subclasses of the SDK classes do not need to implement RandomAccess, as they will automatically inherit the capability where appropriate.

The second aspect, using the RandomAccess capability, is also different. Whether a class is Serializable or Cloneable is automatically detected when you use ObjectInput/ObjectOutput and Object.clone(). But RandomAccess has no such automatic support. You need to explicitly check whether a class implements RandomAccess using the instanceof operator:

if (listObject instanceof RandomAccess)

Then you must explicitly choose the appropriate access method, List.get() or Iterator.next(). Clearly, if we test for RandomAccess on every loop iteration, we would be making a lot of redundant calls, and probably losing the benefit of RandomAccess as well. So the pattern to follow in using RandomAccess makes the test outside the loop. The canonical pattern looks like:

Object o;
if (listObject instanceof RandomAccess)
{
  for (int i=0, n=list.size(); i < n; i++)
  {
    o = list.get(i);
    //do something with object o
  }

}
else
{
  Iterator itr = list.iterator();
  for (int i=0, n=list.size(); i < n; i++)
  {
    o = itr.next();
    //do something with object o

  }
}

The speedup from using RandomAccess

Related Reading Java Performance Tuning By Jack Shirazi Table of Contents Index Sample Chapter Full Description Read Online -- Safari

I tested the four code loops shown in this article, using the 1.4 beta release, separately testing the -client and -server options. To test the effect of the RandomAccess interface, I used the java.util.ArrayList and java.util.LinkedList classes. ArrayList implements RandomAccess, while LinkedList does not. ArrayList has an underlying implementation consisting of an array with constant access time for any element, so using the ArrayList iterator is equivalent to using the ArrayList.get() method, but with some additional overhead. LinkedList has an underlying implementation consisting of linked node objects, so it has access time proportional to the shortest distance of the element from either end of the list; iterating sequentially through the list can shortcut the access time by traversing one node after another.

Pages: 1, 2

Next Page