JDK-6366780 : A big win for concrete class inference
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 5.0,9,10
  • Priority: P3
  • Status: Closed
  • Resolution: Won't Fix
  • OS: generic
  • CPU: generic
  • Submitted: 2005-12-22
  • Updated: 2017-04-07
  • Resolved: 2017-04-07
Related Reports
Relates :  
Description
FULL PRODUCT VERSION :
java version "1.5.0_05"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_05-b05)
Java HotSpot(TM) Client VM (build 1.5.0_05-b05, mixed mode)

FULL OPERATING SYSTEM VERSION :
SunOS s0046mqa 5.7 Generic_106541-15 sun4us sparc FJSV,GPUS

A DESCRIPTION OF THE PROBLEM :
Summing up the elements of an int[] array using interfaces
for both the Iterator and the int wrapper Object takes 10
times(!) longer than using the concrete classes (on Solaris
7/SPARC, on Linux/Intel 2.3x, on WindowsNT 2.5x).

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
for a in 0 1 2 3 4 5 6
do
  java -server SlowInterface 1000000 20 20 $a
done


ACTUAL BEHAVIOR :
Linux on Pentium 4 mobile, 1.6 GHz, -server VM:
0: 215ms
1: 1715ms
2: 983ms
3: 1004ms
4: 264ms
5: 311ms
6: 160ms

Windows XP on Pentium 4, 2.4 GHz, 1Gb RAM, -server VM:
0: 94ms
1: 609ms
2: 594ms
3: 594ms
4: 188ms
5: 203ms
6: 78ms

This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;

public class SlowInterface {
    //----------------------------------------------------------------------
    // int wrapper
    //----------------------------------------------------------------------
    private interface intReadRef {
	int get ();
    }

    private interface intWriteRef {
	void set (int value);
    }

    private interface intRef extends intReadRef, intWriteRef { }

    private static final class MutableInt implements intRef {
	private int value;
	public MutableInt (int value) { this.value = value; }
	public MutableInt () { }
	public int get () { return value; }
	public void set (int value) { this.value = value; }
    }

    //----------------------------------------------------------------------
    // int[] iterators
    //----------------------------------------------------------------------
    private static abstract class IntArrayIterator implements Iterator {
	protected final int[] a;
	protected final int   length;
	protected       int   i;
	protected       int   lastI = -1;
	protected IntArrayIterator (int[] a, int i) { this.a = a; this.i = i;
length = a.length; }
	public IntArrayIterator (int[] a) { this (a, 0); }
	public final boolean hasNext () { return length > i; }
	public final Object next () {
	    try {
		return getUnchecked (lastI = i++);
	    } catch (ArrayIndexOutOfBoundsException e) {
		throw new NoSuchElementException ("index: " + (lastI = --i)
+ ", length: " + length);
	    }
	}
	public final void remove () { throw new UnsupportedOperationException
(); }
	protected abstract Object getUnchecked (int i);
    }

    private static final class MutableIterator extends IntArrayIterator {
	private final MutableInt result = new MutableInt ();
	public MutableIterator (int[] a) { super (a); }
	protected Object getUnchecked (int i) { result.set (a [i]); return
result; }
    }

    //----------------------------------------------------------------------
    private static final long run (int alg, int[] a, long expectedSum, int n) {
	long start = System.currentTimeMillis ();
	for (int r = 0; r < n; ++r) {
	    long s = 0;

	    switch (alg) {
		case 0: {
		    for (int i = 0; i < a.length; ++i) {
			s += a [i];
		    }
		} break;
		
		case 1: {
		    for (Iterator i = new MutableIterator (a); i.hasNext (); ) {
			s += ((intReadRef)i.next ()).get ();
		    }
		} break;

		case 2: {
		    for (Iterator i = new MutableIterator (a); i.hasNext (); ) {
			s += ((intRef)i.next ()).get ();
		    }
		} break;

		case 3: {
		    for (Iterator i = new MutableIterator (a); i.hasNext (); ) {
			s += ((MutableInt)i.next ()).get ();
		    }
		} break;

		case 4: {
		    for (MutableIterator i = new MutableIterator (a); i.hasNext
(); ) {
			s += ((intReadRef)i.next ()).get ();
		    }
		} break;

		case 5: {
		    for (MutableIterator i = new MutableIterator (a); i.hasNext
(); ) {
			s += ((intRef)i.next ()).get ();
		    }
		} break;

		case 6: {
		    for (MutableIterator i = new MutableIterator (a); i.hasNext
(); ) {
			s += ((MutableInt)i.next ()).get ();
		    }
		} break;
		
	    }

	    if (s != expectedSum) {
		throw new IllegalStateException ("wrong sum (expected: " +
expectedSum + "; actual: " + s + ")");
	    }
	}
	return System.currentTimeMillis () - start;
    }

    public static void main (String[] args) {
	int   length  	  = Integer.parseInt (args [0]);
	int   warmup  	  = Integer.parseInt (args [1]);
	int   measure 	  = Integer.parseInt (args [2]);
	int   alg 	  = Integer.parseInt (args [3]);
	int[] a       	  = new int [length];
	long  expectedSum = (length / 2L) * (length + 1L);

	// fill
	for (int i = 0; i < length; ++i) {
	    a [ i] =  i + 1;
	}

	run (alg, a, expectedSum, warmup);
	System.out.println (alg + ": " + run (alg, a, expectedSum, warmup)
+ "ms");
    }
}

---------- END SOURCE ----------

CUSTOMER WORKAROUND :
Cast down to the concrete classes (not possible if concrete
classes are private inner classes).

Comments
EVALUATION The server compiler should be able to use CHA to determine if an invokeinterface has a single concrete implementor, such as in the test case. Specifically, ciMethod::find_monomorphic_target() can be changed to do this once interfaces can be "trusted". See 6312651 for a description of the prep work needed before this bug can be fixed.
04-01-2006

EVALUATION I'm not a hotspot engineer, but... I've done some microbenchmarking work that may be relevant here. The server compiler does an excellent job (vs. client) of optimizing for (MutableIterator i = new MutableIterator(a); i.hasNext();) s += ((MutableInt)i.next()).get(); but a relatively lousy job of optimizing for (Iterator i = new MutableIterator(a); i.hasNext();) s += ((MutableInt)i.next()).get(); even though, with just a little more work, hotspot could "know" that i is always a MutableIterator, and so could optimize the code in exactly the same way as the code above. Since the biggest win appears to be with server, I'm redispatching to compiler2 There is a possible factor of 5 to be won with what would appear to be a relatively simple optimization, so I'm raising the priority to P3. Here's the benchmark: --------------------------------------------- import java.util.*; public class IteratorMicroBenchmark { abstract static class Job { private final String name; public Job(String name) { this.name = name; } public String name() { return name; } public abstract void work() throws Throwable; } private static final long SECOND = 1000L*1000L*1000L; 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 at least 10 seconds. * Returns array of average times per job per run. */ private static long[] time0(Job ... jobs) throws Throwable { 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) < 10L * SECOND); 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(int s) { if (s == -927442) throw new Error(); } private interface intReadRef { int get(); } private interface intWriteRef { void set(int value); } private interface intRef extends intReadRef, intWriteRef {} private static final class MutableInt implements intRef { private int value; public MutableInt(int value) { this.value = value; } public MutableInt() {} public int get() { return value; } public void set(int value) { this.value = value; } } private static abstract class IntArrayIterator implements Iterator { protected final int[] a; protected final int length; protected int i; protected int lastI = -1; protected IntArrayIterator(int[] a, int i) { this.a = a; this.i = i; length = a.length; } public IntArrayIterator(int[] a) { this(a, 0); } public final boolean hasNext() { return length > i; } public final Object next() { try { return getUnchecked(lastI = i++); } catch (ArrayIndexOutOfBoundsException e) { throw new NoSuchElementException( "index: " + (lastI = --i) + ", length: " + length); } } public final void remove() { throw new UnsupportedOperationException(); } protected abstract Object getUnchecked(int i); } private static final class MutableIterator extends IntArrayIterator { private final MutableInt result = new MutableInt(); public MutableIterator(int[] a) { super(a); } protected Object getUnchecked(int i) { result.set(a[i]); return result; } } public static void main(String[] args) throws Throwable { final int iterations = intArg(args, 0, 40); final int size = intArg(args, 1, 1000000); final int[] a = new int[size]; final Random rnd = new Random(); for (int i = 0; i < a.length; i++) a[i] = rnd.nextInt(size); time( new Job("native") { public void work() throws Throwable { int s = 0; for (int j = 0; j < iterations; j++) for (int i = 0; i < a.length; ++i) s += a[i]; deoptimize(s);}}, new Job("cast Iterator.next()->intReadRef") { public void work() throws Throwable { int s = 0; for (int j = 0; j < iterations; j++) for (Iterator i = new MutableIterator(a); i.hasNext();) s += ((intReadRef)i.next()).get(); deoptimize(s);}}, new Job("cast Iterator.next()->intRef") { public void work() throws Throwable { int s = 0; for (int j = 0; j < iterations; j++) for (Iterator i = new MutableIterator(a); i.hasNext();) s += ((intRef)i.next()).get(); deoptimize(s);}}, new Job("cast Iterator.next()->MutableInt") { public void work() throws Throwable { int s = 0; for (int j = 0; j < iterations; j++) for (Iterator i = new MutableIterator(a); i.hasNext();) s += ((MutableInt)i.next()).get(); deoptimize(s);}}, new Job("cast MutableIterator.next()->intReadRef") { public void work() throws Throwable { int s = 0; for (int j = 0; j < iterations; j++) for (MutableIterator i = new MutableIterator(a); i.hasNext();) s += ((intReadRef)i.next()).get(); deoptimize(s);}}, new Job("cast MutableIterator.next()->intRef") { public void work() throws Throwable { int s = 0; for (int j = 0; j < iterations; j++) for (MutableIterator i = new MutableIterator(a); i.hasNext();) s += ((intRef)i.next()).get(); deoptimize(s);}}, new Job("cast MutableIterator.next()->MutableInt") { public void work() throws Throwable { int s = 0; for (int j = 0; j < iterations; j++) for (MutableIterator i = new MutableIterator(a); i.hasNext();) s += ((MutableInt)i.next()).get(); deoptimize(s);}}); } } --------------------------------------------- and here's a run on solaris-sparc: (mb29450@suttles) ~/src/toy/Imbusch $ jver 6.0 javac IteratorMicroBenchmark.java && for f in -server -client; do echo $f; jver 6.0 java $f IteratorMicroBenchmark; done -server Method Millis Ratio native 189 1.000 cast Iterator.next()->intReadRef 3156 16.637 cast Iterator.next()->intRef 3205 16.895 cast Iterator.next()->MutableInt 2993 15.782 cast MutableIterator.next()->intReadRef 1322 6.974 cast MutableIterator.next()->intRef 1344 7.086 cast MutableIterator.next()->MutableInt 547 2.887 -client Method Millis Ratio native 637 1.000 cast Iterator.next()->intReadRef 3370 5.292 cast Iterator.next()->intRef 3297 5.177 cast Iterator.next()->MutableInt 3046 4.782 cast MutableIterator.next()->intReadRef 2657 4.172 cast MutableIterator.next()->intRef 2688 4.221 cast MutableIterator.next()->MutableInt 2337 3.670
24-12-2005