Transcript Profile and optimize your Java code

Profile and optimize
your Java code
Gabriel Laden
CS 146 – Dr. Sin-Min Lee
Spring 2004
Introduction
• O(n) notation is one thing
• Performance of your coded algorithm is
another thing!!!
• This demo will use Homework #3
“ICBaseCycle” problem
Where to start testing?
• To find run-time between two sequential
lines in your code insert the following:
System.currentTimeMillis();
The 80/20 rule
• Your code spends 80% of its time in 20% of
the code, or so they say…
• How to find this hotspot in your code
without just guessing :
java –Xprof class [args]
java –Xprof class [args]
• -Xprof is a built-in profiler for your code
• It tells you what % time is spent in running
and other Java administrative tasks
• Caution: eliminate your user I/O and other
things like that which are not constant and
will throw off your testing results
Other interesting java –X options
• -Xloggc:<file> log GC status to a file with time stamps
Note: see use later in presentation
• -Xmx<size>
set maximum Java heap size
Note: 64M is default, good use is for problems of
moderately larger size, (go buy more memory at Fry’s)
• -Xss<size>
set java thread stack size
Note: good use in recursive problems
javap - The Java Class File Disassembler
javap [options] class
• The javap command disassembles a class file. Its output
depends on the options used. If no options are used, javap
prints out the package, protected, and public fields and
methods of the classes passed to it.
• -c option prints out disassembled code, i.e., the instructions
that comprise the Java bytecodes
Most Important Step!!!
• Find your inner-most loop that is in method
with largest run-time %
• Re-write this loop to be most efficient
• This is where O(n) notation theory can be
applied to your algorithm
Java handles your garbage
• So don’t forget to analyze this!!!
• java -Xloggc:<file> class
• The cost of gc also implies the cost of the allocation
• The number of lines written to filegc will be evidence of
the garbage collector activity
• Look in your code for unneccessary allocations
• Re-order processing to keep heap size to a minimum
Try a few different things
•
•
•
•
•
Is your sort algorithm really the best one?
Is your data structure really the best one?
Save your working program to a backup!!!
Compare run-times with different sorts
Do the least # operations to get your output
Summary
•
•
•
•
v1 original code
v2 inner loop re-write / algorithm design
v3 minimize allocations
v4 improved version
(…repeat (1-4) if necessary)
• v5 final version
// version 1
private boolean sumElements(int[] permutation){
//generate sumation of terms 1+2+3+...+p
int walk, sum;
int index = 0;
int[] partSums = new int[p * (p-1) + 1];
// i = length of the elements of sum
for(int i=1; i<p; i++){
//j = starting index
for(int j=0; j<p; j++){
sum = 0;
walk = j;
//k = loop for summation
for(int k=0; k<i; k++){
if(walk == p){
walk = 0;
}
sum += permutation[walk++];
}
partSums[index++] = sum;
}
}// (con’t next slide…)
// version 1 (con’t)
//add last element sum of all elements
partSums[index] = n;
//qsort rewritten from QSortAlgorithm.java in j2sdk demo directory
QSort.qsort(partSums, 0, partSums.length-1);
//step through array to verify success
int consecutive = 1;
for(int i=1; i<partSums.length; i++){
if(partSums[i] == consecutive + 1){
consecutive++;
}
else if(partSums[i] > consecutive + 1){
return false;
}
}
return true;
}
// version 5
private boolean sumElements(int[] permutation, boolean[] partIndexes){
//generate sumation of terms 1+2+3+...+p
int value, walk;
int pMinusOne = p - 1;
Arrays.fill(partIndexes, false);
for(int i=0; i<p; i++){
walk = i + 1;
partIndexes[(value = permutation[i])] = true;
for(int j=1; j<pMinusOne; j++, walk++){
partIndexes[(value += permutation[walk])] = true;
}
}
//skip over index 0, not used
//skip over index 1 & 2, always true
for(int i=3; i<partIndexes.length; i++){
if(partIndexes[i] == false){
return false;
}
}
return true;
}
C:\cs146_profiling>java hw3.v1.ICBaseCycle 8 57
Here is a set of valid arrays
1 8 11 3 18 10 2 4
1 12 2 6 3 7 22 4
1 5 15 7 16 2 8 3
1 8 2 3 21 4 12 6
1 6 17 12 2 11 5 3
1 2 10 19 4 7 9 5
# of solutions: 6
Total compute-time: 110.328 seconds
C:\cs146_profiling>java hw3.v5.ICBaseCycle 8 57
Here is a set of valid arrays
1 8 11 3 18 10 2 4
1 12 2 6 3 7 22 4
1 5 15 7 16 2 8 3
1 8 2 3 21 4 12 6
1 6 17 12 2 11 5 3
1 2 10 19 4 7 9 5
# of solutions: 6
Total compute-time: 10.078 seconds
Conclusion
• Easy to start learning how to test the
performance on our homework problems
• Later you will be running large scale
applications with multi-tier enterprise
applications with networking and database,
etc. it will be a lot harder to start learning
how to optimize then!!!
References
• Effective Java - Joshua Bloch
• Java Platform Performance – Steve Wilson
• Core Java v.2 – Cay Horstmann