[ Team LiB ] Previous Section Next Section

7.1 Loops

Programs spend most of their time in loops. There are many optimizations that can speed up loops, as detailed in the following sections.

7.1.1 Move Code Out of the Loop

Take out of the loop any code that does not need to be executed on every pass. This includes assignments, accesses, tests, and method calls that need to run only once.

Method calls are more costly than the equivalent code without the call, and by repeating method calls again and again, you just add overhead to your application. Move any method calls out of the loop, even if this requires rewriting. Inline method calls in loops when possible.

7.1.2 Use Temporary Variables

Array access (and assignment) always has more overhead than temporary variable access because the VM performs bounds-checking for array-element access. Array access is better done once (and assigned to a temporary) outside the loop rather than repeated at each iteration. For example, consider this next loop:

for(int i = 0; i < Repeat; i++)
  countArr[0]+=10;

The following loop optimizes the last loop using a temporary variable to execute the addition within the loop. The array element is updated outside the loop. This optimized loop is significantly better (twice as fast) than the original loop:

count = countArr[0];
for(int i = 0; i < Repeat; i++)
  count+=10;
countArr[0]=count;

7.1.3 Don't Terminate Loops with Method Calls

Avoid using a method call in a loop termination test; the overhead is significant. I often see loops like this when iterating through collections such as Vectors and Strings:

for(int i = 0; i < collection.size(  ); i++) //or collection.length(  )

This next loop factors out the maximum iteration value and is faster:

int max = v.size(  ); //or int max = s.length(  );
for(int i = 0; i < max; i++)

7.1.4 Use int for Index Variables

Using int data types for the index variable is faster than using any other numeric data types. The VM is optimized to use ints. Operations on bytes, shorts, and chars are normally carried out with implicit casts to and from ints. The loop:

for(int i = 0; i < Repeat; i++)

is faster than using any of the other numeric data types:

for(long i = 0; i < Repeat; i++)
for(double i = 0; i < Repeat; i++)
for(char i = 0; i < Repeat; i++)

7.1.5 Use System.arraycopy( )

System.arraycopy( ) is faster than using a loop for copying arrays in any destination VM except where you are guaranteed that the VM has a JIT. In the latter case, using your own for loop may be slightly faster. I recommend using System.arraycopy( ) in either case, since even when the for loop is executing in a JIT VM, it is only slightly faster.

7.1.6 Use Efficient Comparisons

Comparison to 0 is faster than comparisons to most other numbers. The VM has optimizations for comparisons to the integers -1, 0, 1, 2, 3, 4, and 5. So rewriting loops to make the test a comparison against 0 may be faster.[1]

[1] The latest VMs try to optimize the standard for(int i = 0; i < Repeat; i++) expression, so rewriting the loop may not produce faster code. Only non-JIT VMs and HotSpot showed improvements by rewriting the loop. Note that HotSpot does not generate native code for any method executed only once or twice.

This alteration typically reverses the iteration order of the loop from counting up (0 to max) to counting down (max to 0). For example, for loops are usually coded:

for(int i = 0; i < Repeat; i++)

Both of these functionally identical for loops are faster:

for(int i = Repeat-1; i >= 0; i--)
for(int i = Repeat; --i >= 0 ; )

When tests need to be made within a loop, try to use the fastest tests. For example, convert equality comparisons to identity comparisons whenever possible. The following uses an equality comparison:

Integer one = new Integer(1);
  ...
  for (...)
   if (integer.equals(one))

This comparison is better replaced with an identity comparison:

for (...)
   if (integer =  = CANONICALIZED_INTEGER_ONE)

Clearly, for this substitution to work correctly, the objects being compared must be matched by identity. You may be able to achieve this by canonicalizing your objects (see Section 4.2.4). You can compare Strings by identity if you String.intern( ) them to ensure you have a unique String object for every sequence of characters, but obviously there is no performance gain if you have to do the interning within the loop or in some other time-critical section of the application. Similarly, the java.util.Comparator and Comparable interfaces provide a nice generic framework. But they impose a heavy overhead in requiring a method call for every comparison and may be better avoided in special situations (see Chapter 9). One test I sometimes see is for a Class:

if (obj.getClass(  ).getName(  ).equals("foo.bar.ClassName"))

It is more efficient to store an instance of the class in a static variable and test directly against that instance (there is only one instance of any class):

//In class initialization
public static final Class FOO_BAR_CLASSNAME = Class.forName("foo.bar.ClassName");
...
//and in the method
if (obj.getClass(  ) =  = FOO_BAR_CLASSNAME)

Note that foo.bar.ClassName.class is a valid construct to refer to the foo.bar.ClassName class object. However, the compiler generates a static method that calls Class.forName( ) and replaces the foo.bar.ClassName.class construct with a call to that static method. So it is better to use the FOO_BAR_CLASSNAME static variable as suggested, rather than:

if (obj.getClass(  ) =  = foo.bar.ClassName.class)

7.1.7 Put the Most Common Case First

When several boolean tests are made together in one expression in the loop, try to phrase the expression so that it " short-circuits" as soon as possible by putting the most likely case first (see the sidebar Short-Circuit Operators). Ensure that by satisfying earlier parts of the expression, you do not cause the later expressions to be evaluated. For example, the following expression tests whether an integer is in the range 4 to 8 or is the smallest integer:

if (someInt =  = Integer.MIN_VALUE || (someInt > 3 && someInt < 9))
  ... //condition1
else
  ... //condition2

Short-Circuit Operators

The || and && boolean operators are "short-circuit" operators. Their left side is evaluated first, and their right side is not evaluated at all if the result of the left side produces a conclusive result for the expression. Specifically, the conditional-And operator, &&, evaluates its right side only if the result of its left operand is true. The conditional-Or operator, ||, evaluates its right side only if the result of its left operand is false.

These operators differ from the logical And and Or operators, & and |, in that these latter logical boolean operators always evaluate both of their arguments. The following example illustrates the differences between these two types of logical operators by testing both boolean And operators:

boolean b, c;
  b = c = true;
  //Left hand side makes the expression true
  if( (b=true) || (c=false) ) //is always true
    System.out.println(b + " " + c);
  b = c = true;
  if( (b=true) | (c=false) ) //is always true
    System.out.println(b + " " + c);

Here is the output this code produces:

true true
true false

The first test evaluates only the left side; the second test evaluates both sides even though the result of the right side is not needed to determine the result of the full boolean expression.

Suppose that the integers passed to this expression are normally in the range of 4 to 8. Suppose also that if they are not in that range, the integers passed are most likely to be values larger than 8. In this case, the given ordering of tests is the worst possible ordering for the expression. As the expression stands, the most likely result (integer in the 4 to 8 range) and the second most likely result (integer larger than 8) both require all three boolean tests in the expression to be evaluated. Let's try an alternative phrasing of the test:

if (someInt > 8 || (someInt < 4 && someInt != Integer.MIN_VALUE))
... //condition2
else
... //condition1

This rephrasing is functionally identical to the original. But it requires only two tests to be evaluated to process the most likely case, where the integer is in the 4 to 8 range, and only one test to be evaluated for the second most likely case, where the integer is larger than 8.

7.1.8 Avoid Reflection

Avoid the use of reflection within loops (i.e., methods and objects in the java.lang.reflect package). Using reflection to execute a method is much slower than direct execution (as well as being bad style). When reflection functionality is necessary within a loop, change any implementation so that you can achieve the same effect using interfaces and type overloading. For the 1.4 VMs, Sun targeted reflection as one of the areas to be speeded up. Some reflection operations are significantly faster than before 1.4, but reflection is still slower than using an interface to call a method. Note that it is not just the resolution of a method that causes overhead when using reflection. Invoking method calls using Method.invoke( ) is also more expensive than using the plain method call. Handling method references can be complicated, especially with VMs supporting natively compiled code. It can be necessary to manage artificial stack frames that impose overhead to the method calls.
    Previous Section Next Section