Bruce Eckel’s Thinking in Java | Contents | Prev | Next |
that the critical region has been isolated, you can apply two types of optimizations:
generic
techniques and those specific to Java.
Generic
approaches
effective generic speedup is to redefine the program in a more practical way.
For example, in
Programming
Pearls
[14], Bentley describes Doug McIlroy’s representation of the English
language with a novel data depiction that enabled him to produce a remarkably
fast, compact spelling checker. In addition, choosing a better algorithm will
probably give a bigger performance gain than any other approach, particularly
as the size of the data set increases. For more of these generic approaches,
see the general book listings [12-19] at the end of this appendix.
Language
dependent approaches
put things in perspective, it’s useful to look at the time it takes to
perform various operations. So that the results are relatively independent of
the computer being used, they have been normalized by dividing by the time it
takes to make a local assignment.
Operation
|
Example
|
Normalized
time |
Local
assignment |
i
= n; |
1.0
|
Instance
assignment |
this.i
= n; |
1.2
|
int
increment |
i++;
|
1.5
|
byte
increment |
b++;
|
2.0
|
short
increment |
s++;
|
2.0
|
float
increment |
f++;
|
2.0
|
double
increment |
d++;
|
2.0
|
Empty
loop |
while(true)
n++; |
2.0
|
Ternary
expression |
(x<0)
? -x : x |
2.2
|
Math
call |
Math.abs(x);
|
2.5
|
Array
assignment |
a[0]
= n; |
2.7
|
long
increment |
l++;
|
3.5
|
Method
call |
funct( );
|
5.9
|
throw
and catch exception |
try{
throw e; } catch(e){} |
320
|
synchronized
method call |
synchMethod( );
|
570
|
New
Object |
new
Object( ); |
980
|
New
array |
new
int[10]; |
3100
|
present systems (such as Pentium 200 pro, Netscape 3, and JDK 1.1.5), these
relative times show the extraordinary cost of new objects and arrays, the heavy
cost of synchronization, and the modest cost of an unsynchronized method call.
References [5] and [6] give the Web address of measurement applets you can run
on your own machine.
are some modifications that you can make to speed up time-critical parts of
your Java program. (Be sure to test the performance before and after you try
them.)
Replace
|
With
|
Why
|
Interface
|
Abstract
Class (when only one parent is needed) |
Multiple
inheritance of interfaces prevents some optimizations. |
Non-local
or array loop variable |
Local
loop variable |
Time
(above) shows an instance integer assignment is 1.2 local integer assignments, but an array assignment is 2.7 local integer assignments. |
Linked
list (fixed size) |
Saving
discarded link items or replacing the list with a circular array (in which approximate size is known) |
Each
new object takes 980 local assignments. See Reusing Objects (below), Van Wyk [12] p. 87 and Bentley[15] p. 81 |
x/2
(or any power of 2) |
X
>> 2 (or |
Uses
faster hardware instructions |
Specific
situations
cost of Strings
:
The
String
concatenation operator + looks innocent but involves a lot of work. The
compiler can efficiently concatenate constant strings, but a variable string
requires considerable processing. For example, if
s
and
t
are
String
variables:
+ s + "trailer" + t);
requires a new
StringBuffer,
appending arguments, and converting the result back to a
String
with
toString( ).
This costs both space and time. If you’re appending more than one
String,
consider using a
StringBuffer
directly, especially if you can repeatedly reuse it in a loop. Preventing the
creation of a new
StringBuffer
on each iteration saves the object creation time of 980 seen earlier. Using
substring( )
and the other
String
methods is usually an improvement. When feasible, character arrays are even
faster. Also notice that
StringTokenizer
is costly because of 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 to 100 times (notice
the timing above shows it to be 97 times slower). Avoid
synchronized
methods if you can – if you can’t, synchronizing on methods rather
than on code blocks is slightly faster.
objects
:
It takes a long time to create an object (the timing above shows 980 assignment
times for a new
Object,
and 3100 assignment times for a small new array), so it’s often worth
saving and updating the fields of an old object instead of creating a new
object. For example, rather than creating a new
Font
object in your
paint( )
method, you can declare it an instance object, initialize it once, and then
just update it when necessary in
paint( ).
See also Bentley,
Programming
Pearls
p. 81 [15].
You should only throw exceptions in abnormal situations, which are usually
cases in which performance is not an issue since the program has run into a
problem that it doesn’t normally expect. When optimizing, combine small
try–catch
blocks, which thwart compiler optimization by breaking the code into small
independent sections. On the other hand, be careful of sacrificing the
robustness of your code by over-zealous removal of exception handling.
The
standard
Hashtable
class in Java 1.0 and 1.1 requires casting and costly synchronization (570
assignment times). Furthermore, the early JDK library doesn’t
deliberately choose prime number table sizes. Finally, a hashing function
should be designed for the particular characteristics of the keys actually
used. For all these reasons, the generic
Hashtable
can be improved by designing a hash class that fits a particular application
.
Note that the
HashMap
in the Java 1.2 collections library has much greater flexibility and
isn’t automatically
synchronized.
inlining:
Java compilers can inline a method only if it is
final,
private,
or
static,
and in some cases it must have no local variables. If your code spends a lot of
time calling a method that has none of these modifiers, consider writing a
version that is
final.
Use buffers wherever possible, otherwise you can end up doing I/O a single byte
at a time. Note that the JDK 1.0 I/O classes use a lot of synchronization, so
you might get better performance by using a single “bulk” call such
as
readFully( )
and then interpreting the data yourself. Also notice that the Java 1.1
“reader” and “writer” classes were designed for
improved performance.
and instanceof
:
Casts
take from 2 to 200 assignment times. The more costly ones require travel up the
inheritance hierarchy. Other costly operations lose and restore capabilities of
the lower level constructs.
Use clipping to reduce the amount of work done in
repaint( ),
double buffering to improve perceived speed, and image strips or compression to
speed 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( ).
If you must draw a one-pixel-wide line,
drawLine(x,y,x,y)
is faster than
fillRect(x,y,1,1).
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.
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, one application that needed a container to store many
arrays was speeded by replacing the original
Vector
with a faster dynamic array of objects.
- Move
repeated constant calculations out of a critical loop, for example, computing
buffer.length
for a constant-size
buffer. - static
final
constants
can help the compiler optimize the program. - Unroll
fixed length loops. - Use
javac’s optimization option,
-O,
which optimizes compiled code by inlining
static,
final,
and
private
methods. Note that your classes may get larger in size (JDK 1.1 or later only
– earlier versions might not perform byte verification). Newer
just-in-time (JIT) compilers will dramatically speed the code. - Count
down to zero whenever possible – this uses a special JVM byte code.