Java Program Performance Tuning
( )
n (Primes0) static List primes(int n) { List primes = new ArrayList(n); outer: for (int candidate = 2; n > 0; candidate++) { Iterator iter = primes.iterator(); while (iter.hasnext()) { int aprime = ((Integer)iter.next()).intValue(); if (candidate%aprime == 0) continue outer; } primes.add(new Integer(candidate)); n--; } return primes; }
System.currentTimeMillis() long starttime = System.currentTimeMillis(); //... long duration = System.currentTimeMillis() - starttime; java Primes0 count count? 100: 0 ms count = 1,000: 170 ms count = 10,000: 15,320 ms count = 100,000: 5,850,320 ms
java -verbosegc [GC 511K->158K(1984K), 0.0061533 secs] [GC 670K->190K(1984K), 0.0030096 secs] [GC 702K->220K(1984K), 0.0023509 secs] [GC 732K->249K(1984K), 0.0040178 secs] [GC 761K->278K(1984K), 0.0033440 secs]...
( ) java -Xbootclasspath/p:object.jar Primes0 10000 java.lang.integer 10,000 java.util.arraylist 1 java.util.abstractlist$itr 104,728
( ) Runtime totalmemory(), freememory()
java Xrunhprof:cpu=samples CPU SAMPLES BEGIN (total = 659) Sun Jan 20 20:23:05 2002 rank self accum count trace method 1 49.01% 49.01% 323 13 Primes0.primes 2 21.55% 70.56% 142 12 java.util.abstractlist$itr.next 3 7.74% 78.30% 51 11 java.util.arraylist.get 4 7.44% 85.74% 49 14 Primes0.primes 5 7.28% 93.02% 48 9 Primes0.primes 6 4.55% 97.57% 30 15 java.util.abstractlist$itr.hasnext 7 1.06% 98.63% 7 10 java.util.abstractlist.iterator 8 0.15% 98.79% 1 16 Primes0.primes 2 70%
( ) TRACE 13 //while (iter.hasnext())... Primes0.primes(Primes0.java:22) Primes0.main(Primes0.java:9) TRACE 12 //int aprime = ((Integer)iter.next()).intValue(); java.util.abstractlist$itr.next(<unknown>:unknown line) Primes0.primes(Primes0.java:23) Primes0.main(Primes0.java:9)
Primes0 while. Primes0 if (aprime*aprime > candidate) break; [Not if (aprime > (int)math.sqrt(candidate)) break;]
n (Primes1) static List primes(int n) { List primes = new ArrayList(n); outer: for (int candidate = 2; n > 0; candidate++) { Iterator iter = primes.iterator(); while (iter.hasnext()) { int aprime = ((Integer)iter.next()).intValue(); //Applying better algorithm if (aprime*aprime > candidate) break; if (candidate % k == 0) continue outer; } primes.add(new Integer(candidate)); n--; } return primes; }
Primes1 (java Primes1 count) count? 100: 0 ms (vs. 0 ms) count = 1,000: 50 ms (vs. 170 ms) count = 10,000: 220 ms (vs. 15,320 ms) count = 100,000: 4,450 ms (vs. 5,850,320 ms) Primes0 Integer, Iterator(Itr)
HotSpot VM ( ), (adaptive optimization) JIT JIT
javac javac String final (= ) : HotSpot VM -O
,,!
(strength reduction) : 0 for (int i = 0; i < size; i++) for (int i = size-1; i >= 0; i--) (code motion) : llist l.size() for (int i = 0; i < l.size(); i++) for (int i = 0, lsize = l.size(); i < lsize; i++)
( ) int max_a = 100; final int max_a = 100; int max_b = 200; final int max_b = 200; for (int i = arr.length 1; i >= 0; i--) arr[i] = max_a + max_b; final arr[i] = max_a + max_b; arr[i] = 300;
class Poor { int field = 0; public Poor() { field = 0; } } //field is initialized 3 times! data = new int[items]; for (int i = 0; i < items; i++) data[i] = 0; //redundant initialization
( ) MyData data[]; data[m+n].doit(a+1); data[m+n].doit(a+2); MyData dmn = data[m+n]; dmn.doit(a+1); dmn.doit(a+2); data[m+n].doit(a+1).doit(a+2);
( ) ArrayList.get(int index) rangecheck(index); return elementdata[index]; ArrayList.rangeCheck(int index) if (index >= size index < 0) //check once throw new IndexOutOfBoundsException( ); //redundant check
( ) API new Integer( 100 ).intvalue() Integer.parseInt( 100 ) // /
StringStringBuffer! String str = Hello + world! ; String str = Hello world! ; //!
StringStringBuffer ( ) String str = a + b; // String str =new StringBuffer(). append(a).append(b).tostring(); String str = ; StringBuffer sbuf = for ( ) new StringBuffer( ); str += ; for ( ) sbuf.append( ); String str = sbuf.tostring(); StringBuffer
StringStringBuffer 0;1;2...;n (ms) n <=100 1,000 10,000 100,000 String 0 280 26,530 6,833,940 StringBuffer 0 50 110 1,150 String: 3*n +? vs. StringBuffer: n +?
fillinstacktrace() if ( ) Exception EXCEPTION = throw new Exception( ); new Exception( ); if ( ) if ( ) throw EXCEPTION; throw new Exception( ); if ( ) throw EXCEPTION;
((HasXYZ)obj).x + ((HasXYZ)obj).y + ((HasXYZ)obj).z HasXYZ xyz = (HasXYZ)obj; xyz.x + xyz.y + xyz.z
/ null, for (int i = 0; i < REPEAT; i++) counts[0] += i; int acount = counts[0]; for (int i = 0; i < REPEAT; i++) acount += i; counts[0] = acount;
n (Primes2) //Using specialized collection static intlist primes(int n) { intlist primes = new intlist(n); outer: for (int candidate = 2; n > 0; candidate++) { final int size = primes.size(); //Indexing r.t. Enumeration for (int i = 0; i < size; i++) { int aprime = primes.get(i);//no cast if (aprime * aprime > candidate) break; if (candidate % k == 0) continue outer; } primes.add(candidate);//no object creation n--; } return primes; }
n (Primes2 ) class intlist { private int[] data; private int size, capacity; } public intlist(int capacity) { data = new int[capacity]; this.capacity = capacity; } public int get(int index) { //No redundant checks, no cast return data[index]; } public int size() { return size; } public void add(int value) { data[size++] = value; }
n (Primes3) //Using array instead of collection static int[] primes(int n) { int[] primes = new int[n]; int spot = 0; outer: for (int candidate = 2; n > 0; candidate++) { for (int i = 0; i < spot; i++) { int k = primes[i]; //No method calls, no indirection if (k * k > candidate) break; if (candidate % k == 0) continue outer; } primes[spot++] = candidate; n--; } return primes; }
Primes0-3 100,000 (ms)
Primes1-3 100,000 (ms)
Primes0-3 Primes0, Primes1 java.lang.integer 100,000 java.util.arraylist 1 java.util.abstractlist$itr 1,299,708 Primes2 intlist 1 Primes3 None! --Hurrah!
Primes0-3