Speedup techniques

To
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

Using
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.

Here
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 any power of 2)	Uses faster hardware instructions

The
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:

System.out.println("heading"
+ s + "trailer" + t);

this
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.

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.

Reusing
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].

Exceptions:
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.

Hashing:
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.

Method
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.

I/O:
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.

Casts
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.

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 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).

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, one application that needed a container to store many
arrays was speeded by replacing the original
Vector
with a faster dynamic array of objects.