United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-5103956 : (coll) Suggested improvement to speed up ArrayList get and set calls

Details
Type:
Enhancement
Submit Date:
2004-09-17
Status:
Closed
Updated Date:
2012-10-08
Project Name:
JDK
Resolved Date:
2011-05-17
Component:
core-libs
OS:
generic
Sub-Component:
java.util:collections
CPU:
generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
1.4.2,6
Fixed Versions:

Related Reports
Relates:
Relates:
Relates:
Relates:

Sub Tasks

Description
In the words of the web report submitter:

A DESCRIPTION OF THE REQUEST :
A mis-feature in ArrayList results in un-inlinable get/set methods (among others).  The methods are implemented as follows:

    private void RangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(
                "Index: "+index+", Size: "+size);
    }

    public Object get(int index) {
        RangeCheck(index);
        return elementData[index];
    }

    public Object set(int index, Object element) {
        RangeCheck(index);
        Object oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    }


This is pretty amazingly bad code.  The goal of RangeCheck is to move the exception-throwing out of the get and set methods, which I suppose was intended to make them inlineable.  Indeed, though get() is 12 bytes long (and could be inlined) and set() is 21 bytes long (and also could be inlined), they both MUST STILL CALL RangeCheck, which is 48 bytes long and too large to inline.  Thus EVERY get() and set() method call must STILL result in a full method call overhead.


JUSTIFICATION :
My fix below is over 4 times faster in my tests!

I've not delved deeply into the java.util.* code, but if this one was so easy to find, I shudder to think about how poorly the rest of the code has been written with regard to efficiency.  java.util.* is central to Java, and a small amount of work rejiggering it could result in major efficiency improvements to the system as a whole.


CUSTOMER SUBMITTED WORKAROUND :

A trivial modification of get() and set() fixes this quite handily:

    public Object get(int index) {
        if (index >= size) RangeCheck(index);
        return elementData[index];
    }

    public Object set(int index, Object element) {
        if (index >= size) RangeCheck(index);
        Object oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    }


Now RangeCheck is ONLY CALLED if we're out of bounds, a rare condition. get() is 19 bytes and set(...) is 29 bytes, both inlinable.

(Incident Review ID: 311065)

                                    

Comments
SUGGESTED FIX

Here's the proposed fix:

--- /u/martin/ws/dolphin/src/share/classes/java/util/ArrayList.java	2007-01-06 19:36:59.728334000 -0800
+++ /u/martin/ws/outline/src/share/classes/java/util/ArrayList.java	2007-02-12 21:12:05.776664000 -0800
@@ -319,7 +319,7 @@
      * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public E get(int index) {
-	RangeCheck(index);
+	rangeCheck(index);
 
 	return (E) elementData[index];
     }
@@ -334,7 +334,7 @@
      * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public E set(int index, E element) {
-	RangeCheck(index);
+	rangeCheck(index);
 
 	E oldValue = (E) elementData[index];
 	elementData[index] = element;
@@ -363,9 +363,7 @@
      * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public void add(int index, E element) {
-	if (index > size || index < 0)
-	    throw new IndexOutOfBoundsException(
-		"Index: "+index+", Size: "+size);
+	rangeCheckForAdd(index);
 
 	ensureCapacity(size+1);  // Increments modCount!!
 	System.arraycopy(elementData, index, elementData, index + 1,
@@ -384,7 +382,7 @@
      * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public E remove(int index) {
-	RangeCheck(index);
+	rangeCheck(index);
 
 	modCount++;
 	E oldValue = (E) elementData[index];
@@ -493,9 +491,7 @@
      * @throws NullPointerException if the specified collection is null
      */
     public boolean addAll(int index, Collection<? extends E> c) {
-	if (index > size || index < 0)
-	    throw new IndexOutOfBoundsException(
-		"Index: " + index + ", Size: " + size);
+	rangeCheckForAdd(index);
 
 	Object[] a = c.toArray();
 	int numNew = a.length;
@@ -542,10 +538,26 @@
      * negative: It is always used immediately prior to an array access,
      * which throws an ArrayIndexOutOfBoundsException if index is negative.
      */
-    private void RangeCheck(int index) {
+    private void rangeCheck(int index) {
 	if (index >= size)
-	    throw new IndexOutOfBoundsException(
-		"Index: "+index+", Size: "+size);
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+    }
+
+    /**
+     * A version of rangeCheck used by add and addAll.
+     */
+    public void rangeCheckForAdd(int index) {
+ 	if (index > size || index < 0)
+	    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+    }
+
+    /**
+     * Constructs an IndexOutOfBoundsException detail message.
+     * Of the many possible refactorings of the error handling code,
+     * this "outlining" performs best with both server and client VMs.
+     */
+    private String outOfBoundsMsg(int index) {
+	return "Index: "+index+", Size: "+size;
     }
 
     /**
--- /u/martin/ws/dolphin/test/java/util/ArrayList/RangeCheckMicroBenchmark.java	1969-12-31 16:00:00.000000000 -0800
+++ /u/martin/ws/outline/test/java/util/ArrayList/RangeCheckMicroBenchmark.java	2007-02-12 21:27:23.983440000 -0800
@@ -0,0 +1,135 @@
+/*
+ * This is not a regression test, but a micro-benchmark.
+ *
+ * I have run this as follows:
+ *
+ * repeat 5 for f in -client -server; do mergeBench dolphin outline jr -dsa -da $f RangeCheckMicroBenchmark.java; done
+ *
+ * @version 1.1 07/02/12
+ * @author Martin Buchholz
+ */
+
+import java.util.*;
+
+public class RangeCheckMicroBenchmark {
+    abstract static class Job {
+	private final String name;
+	Job(String name) { this.name = name; }
+	String name() { return name; }
+	abstract void work() throws Throwable;
+    }
+
+    private static void collectAllGarbage() {
+	try {
+	    for (int i = 0; i < 2; i++) {
+		System.gc(); System.runFinalization(); Thread.sleep(10);
+	    }
+	} catch (InterruptedException e) { throw new Error(e); }
+    }
+
+    /**
+     * Runs each job for long enough that all the runtime compilers
+     * have had plenty of time to warm up, i.e. get around to
+     * compiling everything worth compiling.
+     * Returns array of average times per job per run.
+     */
+    private static long[] time0(Job ... jobs) throws Throwable {
+	final long warmupNanos = 10L * 1000L * 1000L * 1000L;
+	long[] nanoss = new long[jobs.length];
+	for (int i = 0; i < jobs.length; i++) {
+	    collectAllGarbage();
+	    long t0 = System.nanoTime();
+	    long t;
+	    int j = 0;
+	    do { jobs[i].work(); j++; }
+	    while ((t = System.nanoTime() - t0) < warmupNanos);
+	    nanoss[i] = t/j;
+	}
+	return nanoss;
+    }
+
+    private static void time(Job ... jobs) throws Throwable {
+
+	long[] warmup = time0(jobs); // Warm up run
+	long[] nanoss = time0(jobs); // Real timing run
+
+	final String nameHeader = "Method";
+	int nameWidth  = nameHeader.length();
+	for (Job job : jobs)
+	    nameWidth = Math.max(nameWidth, job.name().length());
+
+	final String millisHeader = "Millis";
+	int millisWidth  = millisHeader.length();
+	for (long nanos : nanoss)
+	    millisWidth =
+		Math.max(millisWidth,
+			 String.format("%d", nanos/(1000L * 1000L)).length());
+
+	final String ratioHeader = "Ratio";
+	int ratioWidth = ratioHeader.length();
+
+	String format = String.format("%%-%ds %%%dd %%.3f%%n",
+				      nameWidth, millisWidth);
+	String headerFormat = String.format("%%-%ds %%-%ds %%-%ds%%n",
+					    nameWidth, millisWidth, ratioWidth);
+	System.out.printf(headerFormat, "Method", "Millis", "Ratio");
+
+	// Print out absolute and relative times, calibrated against first job
+	for (int i = 0; i < jobs.length; i++) {
+	    long millis = nanoss[i]/(1000L * 1000L);
+	    double ratio = (double)nanoss[i] / (double)nanoss[0];
+	    System.out.printf(format, jobs[i].name(), millis, ratio);
+	}
+    }
+
+    private static int intArg(String[] args, int i, int defaultValue) {
+	return args.length > i ? Integer.parseInt(args[i]) : defaultValue;
+    }
+
+    private static void deoptimize(ArrayList<Integer> list) {
+	for (Integer x : list)
+	    if (x == null)
+		throw new Error();
+    }
+
+    public static void main(String[] args) throws Throwable {
+	final int iterations = intArg(args, 0, 30000);
+	final int size       = intArg(args, 1, 1000);
+	final ArrayList<Integer> list = new ArrayList<Integer>();
+	final Random rnd = new Random();
+	for (int i = 0; i < size; i++)
+	    list.add(rnd.nextInt());
+
+	time(
+	    new Job("get") { void work() {
+		for (int i = 0; i < iterations; i++) {
+		    for (int k = 0; k < size; k++)
+			if (list.get(k) == 42)
+			    throw new Error();
+		}
+		deoptimize(list);}},
+	    new Job("set") { void work() {
+		Integer[] xs = list.toArray(new Integer[size]);
+		for (int i = 0; i < iterations; i++) {
+		    for (int k = 0; k < size; k++)
+			list.set(k, xs[k]);
+		}
+		deoptimize(list);}},
+	    new Job("get/set") { void work() {
+		for (int i = 0; i < iterations; i++) {
+		    for (int k = 0; k < size; k++)
+			list.set(k, list.get(size - k - 1));
+		}
+		deoptimize(list);}},
+	    new Job("add/remove at end") { void work() {
+		Integer x = rnd.nextInt();
+		for (int i = 0; i < iterations; i++) {
+		    for (int k = 0; k < size - 1; k++) {
+			list.add(size, x);
+			list.remove(size);
+		    }
+		}
+		deoptimize(list);}}
+	    );
+    }
+}
                                     
2007-02-13
EVALUATION

Benchmark results:

-client: 
==> javac -Xlint:all RangeCheckMicroBenchmark.java
==> java -dsa -da -client RangeCheckMicroBenchmark
Method            Millis Ratio vs. dolphin
get                  122 1.000 0.450
set                  257 2.111 0.673
get/set              272 2.230 0.507
add/remove at end   1644 13.461 0.663

-server, 32-bit
==> javac -Xlint:all RangeCheckMicroBenchmark.java
==> java -dsa -da -server RangeCheckMicroBenchmark
Method            Millis Ratio vs. dolphin
get                   45 1.000 0.978
set                   52 1.142 1.000
get/set              123 2.699 1.000
add/remove at end   1384 30.237 0.987
                                     
2007-02-13
SUGGESTED FIX

Software is always more difficult than it looks.

It's rather easy to get large performance gains (app. factor of two)
with the client compiler, but rather more difficult to do this while
not slowing down the server compiler, on 32 and 64-bit platforms.

Of the various alternatives, only the refactoring

-    private void RangeCheck(int index) {
+    private void rangeCheck(int index) {
        if (index >= size)
-           throw new IndexOutOfBoundsException(
-               "Index: "+index+", Size: "+size);
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+    }

appears to work.
                                     
2007-02-13
EVALUATION

From ###@###.###:

One technique, not mentioned by the submitter, is to
isolate error *handling* (not detection) code into a 
separate method to allow error detection to be inlined,
i.e.
"outline" this:

    private void RangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(
                "Index: "+index+", Size: "+size);
    }

to this:
    private void outOfBounds(int index) {
         throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: "+size);
    }

    private void RangeCheck(int index) {
        if (index >= size)
            outOfBounds(index);
    }

which should win with any kind of hotspot-aware inliner.
                                     
2006-07-25
PUBLIC COMMENTS

.
                                     
2004-09-30
SUGGESTED FIX

public Object get(int index) {
        if (index >= size) RangeCheck(index);
        return elementData[index];
    }

    public Object set(int index, Object element) {
        if (index >= size) RangeCheck(index);
        Object oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    }
                                     
2004-09-30
WORK AROUND

1) Use the "-server" runtime compiler instead of "-client".  The server
compiler will inline RangeCheck into get() and set().

2) Increase the maximum size used by the runtime compiler when considering
when to inline.

###@###.### 2004-09-17
                                     
2004-09-17



Hardware and Software, Engineered to Work Together