JDK-5103956 : (coll) Suggested improvement to speed up ArrayList get and set calls
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 1.4.2,6
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2004-09-17
  • Updated: 2012-10-08
  • Resolved: 2011-05-17
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 7
7 b10Fixed
Related Reports
Relates :  
Relates :  
Relates :  
Relates :  
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
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
13-02-2007

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.
13-02-2007

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);}} + ); + } +}
13-02-2007

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.
25-07-2006

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; }
30-09-2004

PUBLIC COMMENTS .
30-09-2004

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
17-09-2004