11.6 The RandomAccess Interface

SDK 1.4 introduced a java.util.RandomAccess interface for optimizing List performance, but it has no methods. What is the purpose of this interface?

11.6.1 What Does RandomAccess Mean?

RandomAccess is a marker interface, like the Serializable and Cloneable interfaces. All 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, 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: what exactly 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.

Repeated access using List.get( ):

Object o;
for (int i=0, n=list.size(  ); i < n; i++)
  o = list.get(i);

Repeated access using Iterator.next( ):

Object o;
for (Iterator itr=list.iterator(  ); itr.hasNext(  ); )
  o = itr.next(  );

A third loop 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 iterated through without an exception of some sort occurring. So, because 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 previous loop with the Iterator.hasNext( ) test. In the context of the RandomAccess interface, the first loop using List.get( ) should be faster than both the other loops that use Iterator.next( ) for a list to implement RandomAccess.

11.6.2 How Is RandomAccess Used?

So now that we know what RandomAccess means, how do we use it? There are two aspects to using the other marker interfaces, Serializable and Cloneable: defining classes that implement them and using their capabilities via ObjectInput /ObjectOutput and Object.clone( ), respectively. 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 be implemented only in java.util.List classes. And most such classes are created outside of projects. The SDK provides the most frequently used implementations, and subclasses of the SDK classes do not need to implement RandomAccess because they 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. Instead, you need to explicitly check whether a class implements RandomAccess using the instanceof operator:

if (listObject instanceof RandomAccess)
  ...

You must then 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 this:

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
   
  }
}

11.6.3 Speedup from RandomAccess

I tested the four code loops shown in this section, using the 1.4 release, separately testing the -client (default) 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 with access time proportional to the shortest distance of the element from either end of the list, whereas iterating sequentially through the list can shortcut the access time by traversing one node after another.

Times shown are the average of three runs, and all times have been normalized to the first table cell, i.e., the time taken by the ArrayList to iterate the list using the List.get( ) method in client mode.

The most important results are in the last two rows. The last line shows the times obtained by making full use of the RandomAccess interface, and the line before that shows the most optimal general technique for iterating lists if RandomAccess is not available. The size of the lists I used for the test (and consequently the number of loop iterations required to access every element) was sufficiently large that the instanceof test had no measurable cost in comparison to the time taken to run the loop. Consequently, we can see that there was no cost (but also no benefit) in adding the instanceof RandomAccess test when iterating the LinkedList, whereas the ArrayList was iterated more than 20% quicker when the instanceof test was included.

11.6.4 Forward and Backward Compatibility

Can you use RandomAccess and maintain backward compatibility with VM versions prior to 1.4? There are three aspects to using RandomAccess:

• You may want to include code referencing RandomAccess without moving to 1.4.

• Many projects need their code to be able to run in any VM, so the code needs to be backward-compatible to run in VMs using releases earlier than 1.4, where RandomAccess does not exist.

• You will want to make your code forward-compatible so that it automatically takes advantage of RandomAccess when running in a 1.4+ JVM.

Making RandomAccess available to your development environment is the first issue, and if you are using an environment prior to 1.4, this can be as simple as adding the RandomAccess interface to your classpath. Any version of the SDK can create the RandomAccess interface. The definition for RandomAccess is:

package java.util;
public interface RandomAccess {  }

We also need to handle RandomAccess in the runtime environment. For pre-1.4 environments, the test:

if (listObject instanceof RandomAccess)

generates a NoClassDefFoundError at runtime when the JVM tries to load the RandomAccess class (for the instanceof test to be evaluated, the class has to be loaded). However, we can guard the test so that it is executed only if RandomAccess is available. The simplest way to do this is to check whether RandomAccess exists, setting a boolean guard as the outcome of that test:

static boolean RandomAccessExists;
...
   
  //execute this as early as possible after the application starts
  try
  {
    Class c =  Class.forName("java.util.RandomAccess");
    RandomAccessExists = true;
  }
  catch (ClassNotFoundException e)
  {
    RandomAccessExists = false;
  }

Finally, we need to change our instanceof tests to use the RandomAccessExists variable as a guard:

if (RandomAccessExists && (listObject instanceof RandomAccess) )

With the guarded instanceof test, the code automatically reverts to the Iterator loop if RandomAccess does not exist and should avoid throwing a NoClassDefFoundError in pre-1.4 JVMs. And, of course, the guarded instanceof test also automatically uses the faster loop branch when RandomAccess does exist and the list object implements it.