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 theObject.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
andObject.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
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
, whileLinkedList
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.
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, using java -client
.
Table 1: Access times for loop types and access methods
Loop type (loop test) and access method | ArrayList java -client |
LinkedList java -client |
ArrayList java -server |
LinkedList java -server |
loop counter (i<n) and list.get() | 100% | too long | 77.5% | too long |
iterator (Iterator.hasNext()) and Iterator.next() | 141% | 219% | 109% | 213% |
iterator (i<n) and iterator.next() | 121% | 205% | 98% | 193% |
RandomAccess test with loop from row 1 or 3 | 100% | 205% | 77.5% | 193% |
Note that HotSpot is capable of optimizing away accesses that are unnecessary, so the test accessed and operated on the list elements in a way that could not eliminate the list element access. The test code is available here.
The most important results are in the last two rows of the table. The last row shows the times obtained by making full use of the RandomAccess
interface; the row before that shows the most optimal general technique for iterating lists, if RandomAccess
were 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 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.
Forward and backward compatibility
What should you do if you are implementing code now? Obviously, you can start developing with a 1.4 (beta) release, but this is not an option everywhere. There are three aspects to using RandomAccess
if you are developing code now:
- You may want to include code referencing
RandomAccess
without moving to 1.4; many development environments cannot be upgraded rapidly or to a beta release. - Many projects need their code to be able to run in any JVM, so the code needs to be backwards-compatible to run in JVMs using releases earlier than 1.4, where
RandomAccess
does not exist. - You will want to make your code forward-compatible so that it will automatically take advantage of
RandomAccess
when running in a 1.4+ JVM.
Making RandomAccess
available to your development environment is the first issue, and 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 {}
This interface can be created using javac
, as follows:
- Create a directory called
temp
- In
temp
, create a directory calledjava
- In
java
, create a directory calledutil
- In
util
, create a file calledRandomAccess.java
, containing the definition just given - Compile
RandomAccess.java
, usingjavac
:javac RandomAccess.java
Now including temp
in your classpath should enable classes that refer to RandomAccess
to be compiled.
Some Java integrated development environments (IDEs) can make it difficult to add a class to the core SDK packages. If this is the case for your IDE, your only hope is that it accepts an external classpath for compilation purposes, in which case the custom-generated RandomAccess
class will need to be held in that external classpath.
We also need to handle RandomAccess
in the runtime environment. For pre-1.4 environments, the test if (listObject instanceof RandomAccess)
will generate 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 only executed if RandomAccess
is available. The simplest way to do this is to check if 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; }
Then, finally, we will need to change our instanceof
tests to use the RandomAccessExists
variable as a guard:
if (RandomAccessExists && (listObject instanceof RandomAccess) )
Now we have the solution for all three aspects mentioned at the beginning of this section:
- The
RandomAccess
interface can be created and compiled easily with any SDK, and this manually-compiled version can be used at compilation time as a stand-in, to compile any code which refers toRandomAccess
. - The guarded
instanceof
test will automatically revert to the Iterator loop ifRandomAccess
does not exist, and should avoid throwing aNoClassDefFoundError
in pre-1.4 JVMs. - The guarded
instanceof
test will also automatically use the faster loop branch whenRandomAccess
does exist and the list object implements it.