Java Performance Tuning

Java(TM) - see bottom of page

|home |services |training |newsletter |tuning tips |tool reports |articles |resources |about us |site map |contact us |
Tools: | GC log analysers| Multi-tenancy tools| Books| SizeOf| Thread analysers|

Our valued sponsors who help make this site possible
JProfiler: Get rid of your performance problems and memory leaks! 

Training online: Threading Essentials course 

Learning From Code: Fast Random Access, page 2 of 2

JProfiler
Get rid of your performance problems and memory leaks!


Java Performance Training Courses
COURSES AVAILABLE NOW. We can provide training courses to handle all your Java performance needs

Java Performance Tuning, 2nd ed
The classic and most comprehensive book on tuning Java

Java Performance Tuning Newsletter
Your source of Java performance news. Subscribe now!
Enter email:


Training online
Threading Essentials course


JProfiler
Get rid of your performance problems and memory leaks!


How many interfaces are there in the JDK that have no fields and no methods? What are these interfaces used for? Read on in our "Fast Random Access" article from our "Learning From Code" series.

Published February 2004, Author Jack Shirazi

Page 2 of 2
previous page: Fast Random Access

How is RandomAccess used?

So now that we know what RandomAccess means, how do we use it? Well, for the most part you will rarely need to implement the interface -- in fact only if you are implementing a List class which has fast random access. However, when you want to iterate List classes, then you can optimize the iteration speed by using RandomAccess. For an example, let's look at the java.util.Collections class. The Collections class implements many utility methods for searching and manipulating Collection objects. In order to optimize performance, many of the utility methods use a variant of an algorithm depending on whether or not the object is a RandomAccess object. For example, the Collections.binarySearch() method is defined as follows:


    public static int binarySearch(List list, Object key) {
        if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
            return indexedBinarySearch(list, key);
        else
            return iteratorBinarySearch(list, key);
    }

This method checks to see if it has been passed a RandomAccess List, and if so uses the List.get() method to access elements while iterating the List (in the indexedBinarySearch() method); otherwise the Iterator.next() method is used (in the iteratorBinarySearch() method). As you can see, that isn't quite the whole story for the binarySearch() method. There is another case where the List.get() method is also used to iterate the List: when the size of the List object is below the BINARYSEARCH_THRESHOLD value. The author of the Collections class, Joshua Bloch, noticed that for smallish collections it was faster to iterate the List using List.get() even if the List wasn't RandomAccess. The threshold value below which the List.get() iteration is used is different for the various utility methods in the Collections class, and each such utility method has it's own threshold value. This is a classic tuning technique. The actual values of the thresholds seem to have been determined by testing using LinkedList as the non-RandomAccess class, and possibly on a Solaris machine, though I would assume that the selected thresholds had been verified on a couple of architectures.

Another Collections method , the Collections.fill() method, illustrates the most common RandomAccess idiom


    public static void fill(List list, Object obj) {
        int size = list.size();

if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i< size; i++) list.set(i, obj); } else { ListIterator itr = list.listIterator(); for (int i=0; i< size; i++) { itr.next(); itr.set(obj); } } }

Backward And Forward Compatibility

Some projects may need to worry about backward compatibility, or may not yet have moved to the 1.4 SDK. Instructions for using RandomAccess with any version of the SDK are available in my earlier article "Faster List iteration using the RandomAccess interface"

Page 2 of 2
previous page: Fast Random Access


Last Updated: 2018-05-28
Copyright © 2000-2018 Fasterj.com. All Rights Reserved.
All trademarks and registered trademarks appearing on JavaPerformanceTuning.com are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries. JavaPerformanceTuning.com is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
URL: http://www.JavaPerformanceTuning.com/articles/randomaccess2.shtml
RSS Feed: http://www.JavaPerformanceTuning.com/newsletters.rss
Trouble with this page? Please contact us