Transcript PowerPoint

Optimization
Introduction
• Optimization has goals that may appear to run counter to good
software engineering practices.
• The goal of optimization is to generate code that is highly
efficient in terms of:
– Space usage
– Execution time.
• There are means to produce code that is efficient that still
satisfies the desirable properties of well engineered software:
– Maintainable
– Modular
– Well structured
– Etc
CS352 - Software Engineering (AY2005)
Slide 2
The basics
•
•
•
•
•
•
•
While is may seem obvious, the first step in producing efficient and
optimized code is to be familiar with the programming language you are
using.
Take time to browse the API to find out what it provides.
Take time to read a textbook (or two) to see what advice more expert
users may have to pass on.
Take time to read other people’s code.
Take time to search the web for helpful advice
– Remember to test the advice! Just because you found the
information on the web (or in a textbook for that matter), does not
mean it is correct.
Take time to gain experience.
– It is estimated that it takes about 10 years to gain all the necessary
experience to be an expert programmer.
– Consider a graduate degree.
Take time to learn multiple languages and paradigms (even if we do not
teach them to you).
CS352 - Software Engineering (AY2005)
Slide 3
Software engineering
•
•
Software engineering teaches us to:
1. Comment code.
2. Adhere to code conventions (standards).
3. Make use of libraries.
4. Provide small working examples illustrating how your code
should be used.
5. Thoroughly test your code.
6. Back up your code.
7. Use tools to make our life easier.
None of these (with the exception of point 3 sometimes) needs
to be sacrificed in order to write efficient, correct and optimized
code.
CS352 - Software Engineering (AY2005)
Slide 4
Software engineering
• The software engineering lifecycle teaches us that there is more
to more producing a program than writing the code.
• We need to:
– Understand the problem/requirements.
– Design a solution
– Document our actions and our code.
– Fully test the implementation to ensure that it meets the
requirements (quality assurance).
– Maintain the system.
CS352 - Software Engineering (AY2005)
Slide 5
Requirements gathering
•
•
•
•
•
•
•
This is the first place we start when we want to produce optimized
code.
We need to understand precisely what the problem is and design a
solution to deliver exactly what is needed.
– If we believe that the system will be reused and a more general
solution is necessary, then that forms part of the requirements on
the software.
Determine the criteria that decides the solution is efficient:
– Fast execution?
– Minimized space utilization?
– Remember the space/time tradeoff.
Select appropriate data structures.
Select appropriate algorithms.
Test your hypothesis.
Measure your success – hw else will you know you have succeeded?
CS352 - Software Engineering (AY2005)
Slide 6
Data structures and algorithms
• We will look at some examples in the near future.
• We will see that understanding the problem is important and that
we do not always have to produce the most general code to
produce a solution that satisfies the requirements.
• Exercise:
– Imagine you want to build a spell checker and that you have
only limited memory available.
– Think about how you will store the words so that you
minimize space utilization.
– Think about how you will store the words to ensure fast and
efficient look-up.
– Estimate how many words you would need in your dictionary
for it to be effective and how much space your data structure
would use to do this.
• We will examine this problem later.
CS352 - Software Engineering (AY2005)
Slide 7
Understand your compiler
• Compilers for languages usually come with a collection of
switches.
• These are flags that you set to influence of the behavior of the
compiler (e.g., -o on the javac command under unix).
– Use the man command on unix to find out more about the
compiler flags available for javac.
– Note that javac –O can has some bugs and sometimes
generates incorrect bytecode!!!!!
• These flags often allow programmers to set the amount of
optimization that the compiler performs on your behalf as it
generates the bytecode.
– These optimizations, such as loop unrolling etc, are
performed by the compiler to decrease execution speed, or
minimize space used (e.g., the size of the bytecode).
• These work with (are not a replacement for) careful selection of
data structures and algorithms.
CS352 - Software Engineering (AY2005)
Slide 8
Your code
•
Loop invariant code motion:
– If an expression inside a loop doesn't change after the loop
is entered (i.e. it's invariant), calculate the value of the
expression outside the loop and assign it to a temporary
variable. Then use the temporary variable within the loop.
– Note that we could also treat a.length as a loop invariant-Speed improvments of 7-11% in tight loops have been
observed, in both interpreted and JIT-compiled VMs.
for (i = 0; i < a.length; i++) {
float tmp = c * d;
b[i] = a[i] + c * d;
for (i = 0; i < a.length; i++) {
}
b[i] = a[i] + tmp;
}
– Don’t rely on the compiler to do the optimization for you –
do is explicitly yourself.
CS352 - Software Engineering (AY2005)
Slide 9
Your code
• Common subexpression elimination:
– If an expensive expression (for example, the result of a
method call) is used more than once within a block of code,
calculate it once and put it into a temporary variable for
subsequent reuse.
double d = a * Math.sqrt (c);
double tmp = Math.sqrt (c);
double e = b * Math.sqrt (c);
double d = a * tmp;
double e = b * tmp;
CS352 - Software Engineering (AY2005)
Slide 10
Your code
•
strength reduction:
– Use cheaper operations in place of expensive ones. For example, use
compound assignment operators such as += instead of ...=...+..., since they
result in fewer bytecode instructions.
– You can also use shifts instead of multiplication by powers of two,
multiplication instead of exponentiation, etc, although mathematical
optimizations of this type generally have little benefit unless you're using a
just-in-time compiler.
for (i = 0; i < a.length; i++) {
for (i = 0; i < a.length; i++) {
a[i] = a[i] + x;
a[i] += x;
}
}
– Adding extra reference variables to allow the compiler to eliminate opcodes
or use faster bytecodes can also be considered a case of strength
reduction.
• For example, if you're repeatedly accessing elements in a single row of
a 2D array, make a 1D array variable that points to that row.
• Similarly, if you have a subclass that performs lots of operations on an
object defined in its superclass, making a reference to the object in the
subclass with super and then using that reference directly will enable
the compiler to replace getfield opcodes with aload opcodes (FASTER).
CS352 - Software Engineering (AY2005)
Slide 11
Your code
•
Variable allocation:
– For desperate optimizers only. The first four numeric variables or
arguments in a method are accessed using via shorter bytecode
instructions, although only three are usable in non-static methods.
– If you declare your most frequently-used variables first (e.g., loop
indices), the inner bytecode loops of your methods will be
marginally shorter and possibly faster.
– Note that although the number of bytecodes for the inner loop is the
same, the length of the bytecode has decreased.
int[] a = (int[]) pop ();
int i;
int[] b = (int[]) pop ();
int[] a = (int[]) pop ();
int[] dst = new int[a.length];
int[] b = (int[]) pop ();
int i;
int[] dst = new int[a.length];
for (i = 0; i < a.length; i++) {
for (i = 0; i < a.length; i++) {
dst[i] = a[i] + b[i];
dst[i] = a[i] + b[i];
}
}
CS352 - Software Engineering (AY2005)
Slide 12
Your code
• Just-in-time compilers:
– Make sure your users have a just-in-time compiler instead of
a standard interpreted Java VM. JIT compilers typically
improve the performance of non-graphical Java primitives by
10-30 times. Browsers with JIT compilers include the Win32
and Mac versions of Netscape Navigator 3.0 and Internet
Explorer 3.0.
CS352 - Software Engineering (AY2005)
Slide 13
Your code
•
•
•
Exploiting multiprocessors:
– If you have a multiprocessor and a Java VM that can spread
threads across processors (and currently these are big ifs), you can
improve performance by multithreading, either manually or through
the use of a restructuring compiler such as JAVAR.
Native methods:
– If you're don't care about cross-platform portability, native methods
will get you the speed of raw C (or Fortran, or C++, or...). Fallback
code lets your program continue even if native methods aren't
available.
Translation into C:
– There are currently four freely-available tools to translate Java into
C: j2c from Japan, JCC from Nik Shaylor, Toba (formerly Juice)
from Arizona, and Harissa (formally Salsa) from France. Toba and
Harissa are both products of active research groups.
CS352 - Software Engineering (AY2005)
Slide 14
Your code
• Graphics:
– Use clipping to reduce the amount of work done in repaint(),
double buffering to improve perceived speed, and image
strips or compression to speed up downloading times.
Animation in Java Applets from JavaWorld and Performing
Animation from Sun are two good tutorials. Remember to
use high-level primitives; it's much faster to call
drawPolygon() on a bunch of points than looping with
drawLine(). And if you have to draw a single pixel drawLine
(x,y,x,y) may be faster than fillRect (x,y,1,1).
CS352 - Software Engineering (AY2005)
Slide 15
Your code
• Input/output:
– Use BufferedInputStream and BufferedOutputStream or
equivalent buffered methods wherever possible; doing I/O a
single byte at a time is generally too slow to be practical.
Note that the JDK 1.0.2 I/O classes use lots of
synchronization, so you might get better performance by
using a single "bulk" call such as readFully and then
interpreting the data yourself.
CS352 - Software Engineering (AY2005)
Slide 16
Your code
• Synchronization:
– In the JDK interpreter, calling a synchronized method is
typically 10 times slower than calling an unsynchronized
method. With JIT compilers, this performance gap has
increased to 50-100 times. Avoid synchronized methods if
you can -- if you can't, synchronizing on methods rather than
on code blocks is slightly faster.
CS352 - Software Engineering (AY2005)
Slide 17
Your code
• Exceptions:
– You should only use exceptions where you really need them-- not only do they have a high basic cost, but their presence
can hurt compiler analysis.
• The costs of Strings:
– The String concatenation operator + looks innocent but
involves a lot of work: a new StringBuffer is created, the two
arguments are added to it with append(), and the final result
is converted back with a toString(). This costs both space
and time. In particular, if you're appending more than one
String, consider using a StringBuffer directly instead.
CS352 - Software Engineering (AY2005)
Slide 18
Your code
• Using API classes:
– Use classes from the Java API when they offer native
machine performance that you can't match using Java. For
example, arraycopy() is much faster than using a loop to
copy an array of any significant size.
• Replacing API classes:
– Sometimes API classes do more than you need, with a
corresponding increase in execution time; for these you can
write specialized versions that do less but run faster. For
example, in one application where I needed a container to
store lots of arrays I replaced the original Vector with a faster
dynamic array of objects. As another example, Paul Houle
has produced a set of random-number generators that are
much faster than Math.random() (and have quality
guarantees too).
CS352 - Software Engineering (AY2005)
Slide 19
Your code
• Overriding API methods:
– If you're using a class from the Java API and are seeing
performance problems with one method, try defining a
subclass which overrides that method with your own
(hopefully more efficient) version.
• Avoiding expensive constructs:
– Sometimes Java constructs are so expensive that it can be
worth making your data structures or code a little more
complex to work around the problem. For example, you can
add a type id number to objects to avoid paying the cost of
an instanceof (this also allows you to use the result in a
switch). Similarly, in a long inheritance tree you can avoid
casting by including a method that returns a value of the type
you would otherwise cast to.
CS352 - Software Engineering (AY2005)
Slide 20
Your code
• Avoiding expensive data structures:
– In a similar manner to the constructs above, expensive Java
data structures can be replaced with simpler ones at the cost
of some extra code complexity. For example, it can be up to
twice as expensive to access a two-dimensional array as a
one-dimensional array, due to the extra indirections.
• Know your switches:
– A switch statement is compiled into one of two bytecodes,
depending on the sparsity of the cases you're switching on.
The first, where the numbers are close together, uses a fast
direct lookup. The second, where the numbers are further
apart, uses a slower search through a table. Look at the
bytecode your code is compiled into to find which you're
using. This is particularly important if you're trying to replace
a sequence of if statements with a switch.
CS352 - Software Engineering (AY2005)
Slide 21
Your code
• Function inlining:
– Java compilers can only inline a method if it is final, private,
or static (It has been noted that javac will only inline if a
method has no local variables). If your code spends lots of
time calling a method that has none of these modifiers,
consider writing a version that is final.
CS352 - Software Engineering (AY2005)
Slide 22
Your code
•
•
Reusing objects:
– It takes a long time to create an object (see Java microbenchmarks
for exactly how long), so it's often worth updating the fields of an
old object and reusing it rather than creating a new object. For
example, rather than creating a new Font object in your paint
method you can declare it as an instance object, initialize it once,
and then just update it when necessary in paint. Similarly, rather
than allowing the garbage collector to deal with objects you've
removed from a linked list, you can store them in a free list, to be
reused the next time you need to add a new object. This can be
particularly important for graphics objects like Rectangles, Points
and Fonts. See also "Not using garbage collection", from
JavaWorld.
High-level optimizations:
– For a higher-level approach to optimizing the structure of objectoriented code, the online book "Object-Oriented System
Development" has a chapter on performance optimization.
CS352 - Software Engineering (AY2005)
Slide 23
Tools
• Profiling:
– To profile a (single-threaded) application, use java -prof. To
profile an applet, use java -prof sun.applet.AppletViewer
myfile.html. The profile file can then be analyzed using a tool
such as Profile Viewer or HyperProf. You can also use the
profiling tools built into an IDE such as VisionSoft Note that
commercial profilers such as Optimize It! can profile both
time and memory.
CS352 - Software Engineering (AY2005)
Slide 24
Tools
• Disassembly:
– Use javap -c to see the bytecode that your Java is compiled
into: javac -O test.java javap -c test | more To understand
the bytecode, read the Java VM spec.
CS352 - Software Engineering (AY2005)
Slide 25
Tools
• Timing:
– Write a timing harness to wrap around code fragments so
that you can benchmark them. You can either adapt the old
thread-based HotJava Performance Tests, or just use a
simple loop. Note that system.currentTimeMillis() returns the
time of day, not the process time, so all benchmarking
should be done on an idle machine. Call system.gc() before
every timing run to minimize inconsistent results due to
garbage collection in the middle of a run. On systems with
sub-millisecond clocks you can use native methods to
access them (e.g., gettimeofday() or getrusage() on Unix
systems).
CS352 - Software Engineering (AY2005)
Slide 26
Tools
• Memory use:
– You can write a memory-use harness in just the same way
you'd write a timing harness, replacing calls to
system.currentTimeMillis() with calls to:
long freemem () {
System.gc();
return Runtime.getRuntime().freeMemory();
}
CS352 - Software Engineering (AY2005)
Slide 27
Optimizing for space
• Reducing code size is particularly important for Java applets,
since it directly affects the time taken to download an applet.
• Use JAR (or zip, or CAB) files:
– To avoid the overhead of loading individual class and data
files, JDK 1.1 supports Java archive (JAR) files. Previously,
JDK 1.02 and Netscape Navigator 3.0 supported zip files,
while Microsoft Internet Explorer 3.0 supported CAB files.
• Don't reinvent API classes:
– Use or extend a class from the Java API wherever possible.
Sun has written the classes so that you don't have to.
CS352 - Software Engineering (AY2005)
Slide 28
Optimizing for space
• Exploit inheritance:
– Use inheritance in your own code: the more methods you
can inherit, the less code you have to write.
• Turn on compiler optimization:
– Use javac -O. This inlines functions (which makes the
bytecode bigger) and removes line numbers (which makes it
smaller). Unless you use lots of inlinable functions, the
removal of line numbers will dominate and your bytecode will
get smaller. However, note that things can sometimes be
inlined when they shouldn't!!
CS352 - Software Engineering (AY2005)
Slide 29
Optimizing for space
• Separate out common code:
– Put code that is used in several different places into its own
method (the reverse of inlining code for speed).
• Don't initialize big arrays:
– Although array initialization is a single statement in Java, the
generated bytecode inserts one element at a time. If you've
got a big array, this requires a lot of bytecode. You can save
space by storing your data in a String and then parsing it into
your array at runtime.
CS352 - Software Engineering (AY2005)
Slide 30
Optimizing for space
• Dates are big (not just broken)
– Date objects take a surprising amount of space for
something with such limited functionality. If you're storing a
lot of them, considering using longs instead, and recreating
Date objects from them as necessary.
• Use short names:
– The names of visible entities (i.e., class, method and
instance variable names) are listed in full in the class file, so
using short names actually saves space. Code obfuscators
such as Hashjava, Jobe, Obfuscate and Jshrink will rewrite
your class files to use shorter (and incomprehensible)
names.
CS352 - Software Engineering (AY2005)
Slide 31
Optimizing for space
• Put static final constants in interfaces:
– Constants defined using static final are included in the class
file as well as being inlined. If you instead define them in an
interface that you then implement, you can avoid this extra
space overhead.
CS352 - Software Engineering (AY2005)
Slide 32
Optimizing for space
•
Watch for string concatenation:
– Using + as a string concatenation operator will result in a method
call if the operands are not compile-time constants. Unrolling a loop
to eliminate string concatenation can therefore save space. Again,
this might not be worth the effort. For example, the following loop is
compiled into 48 bytes of bytecode:
for (int i = 0; i < 3; i++){
imgs[i] = getImage (getCodeBase(), "G" + i + ".gif");
}
– By unrolling the loop we eliminate the runtime concatenations and
reduce the size of the bytecode to 39 bytes:
imgs[0] = getImage (getCodeBase(), "G0.gif");
imgs[1] = getImage (getCodeBase(), "G1.gif");
imgs[2] = getImage (getCodeBase(), "G2.gif");
– Note that the three instances of getCodeBase() are a good
candidate for common subexpression elimination.
CS352 - Software Engineering (AY2005)
Slide 33
Discussion
• You were asked to think about the space and time needs for a
spelling checker.
• The ability to estimate with a reasonable degree of accuracy is
an essential skill.
• These “back of an envelope” calculations will give you a guide to
the expected performance or resource needs of your proposed
solution BEFORE you implement it and discover that it doesn’t
work.
• Lets discuss the expected space and time needs of the various
approaches that the class has considered for the
implementation of a spelling checker (which is really just a
searching algorithm…).
CS352 - Software Engineering (AY2005)
Slide 34