7.3 Exception-Terminated Loops

This is a technique for squeezing out the very last driblet of performance from loops. With this technique, instead of testing on each loop iteration to see whether the loop has reached its normal termination point, you use an exception generated at the end of the loop to halt the loop, thus avoiding the extra test on each run through the loop.

I include this technique here mainly because it is a known performance-tuning technique, but I do not recommend it as I feel it is bad programming practice (the phrase "enough rope to hang yourself" springs to mind). I'll illustrate the technique with some straightforward examples. The full class for testing the examples is listed later, after I discuss the test results. The tests themselves are very simple. Basically, each test runs two varieties of loops. The first variety runs a standard for loop as you normally write it:

for (int loopvar = 0; loopvar < someMax; loopvar++)

The second variety leaves out the termination test in the for loop, thus making the loop infinite. But these latter loops are put inside a try-catch block so an exception terminates the loop:

try
{
  for (int loopvar = 0; ; loopvar++)
  ... //exception is thrown when loop needs to terminate
}
catch(Exception e) {  }

The three tests I use are:

• A loop that executes integer divisions. The unterminated variety throws an ArithmeticException when a division by zero occurs to terminate the loop.

• A loop that initializes an array of integers. The unterminated variety throws an ArrayIndexOutOfBoundsException when the index of the array grows too large.

• A loop that enumerates a Vector. The unterminated variety throws a NoSuchElementException when there are no more elements to enumerate.

The results of my test runs (summarized in Table 7-1) were variable due to differences in memory allocation, disk paging, and garbage collection. The VMs using HotSpot technology could show quite variable behavior. The plain JDK 1.2 VM had a huge amount of trouble reclaiming memory for the later tests, even when I put in pauses and ran explicit garbage-collection calls more than once. For each set of tests, I tried to increase the number of loop iterations until the timings were over one second. For the memory-based tests, it was not always possible to achieve times of over a second: paging or out-of-memory errors were encountered.

Table 7-1. Speedup using exception-driven loop termination

Speedups	1.1.8	1.2.2	1.3.1	1.3.1-server	1.4	1.4-server	1.4 -Xint
Integer division	~2%	~2%	None	~20%	~2%	None	~40%
Assignment to loop	None	None	~15%	None	~20%	~5%	~50%
Vector enumeration	~5%	~7%	~25%	~20%	~25%	~30%	~50%

The 1.3 and 1.4 server-mode VMs were variable, sometimes showing slightly slower times using this technique. In all test cases, I found that the number of iterations for each test was quite important. When I could run the test consistently, there was usually a loop iteration value above which the exception-terminated loop ran faster. One test run output (without JIT) follows:

Division loop with no exceptions took 2714 milliseconds
Division loop with an exception took 2604 milliseconds
Division loop with an exception took 2574 milliseconds
Division loop with no exceptions took 2714 milliseconds
Assignment loop with no exceptions took 1622 milliseconds
Assignment loop with an exception took 1242 milliseconds
Assignment loop with an exception took 1222 milliseconds
Assignment loop with no exceptions took 1622 milliseconds
Enumeration loop with no exceptions took 42632 milliseconds
Enumeration loop with an exception took 32386 milliseconds
Enumeration loop with an exception took 31536 milliseconds
Enumeration loop with no exceptions took 43162 milliseconds

It is completely conceivable (and greatly preferable) that a compiler or runtime system automatically optimizes loops like this to give the fastest alternative. On some Java systems, try-catch blocks may have enough extra cost associated with them to make this technique slower. Because of the differences in systems, and also because I believe exception-terminated code is difficult to read and likely to lead to bugs and maintenance problems if it proliferates, I prefer to steer clear of this technique.

The actual improvement (if any) in performance depends on the test case that runs in the loop and the code that is run in the body of the loop. The basic consideration is the ratio of the time taken in the loop test compared to the time taken in the body of the loop. The simpler the loop-body execution is compared to the termination test, the more likely that this technique will give a useful effect. This technique works because the termination test iterated many times can have a higher cost than producing and catching an Exception once. Here is the class used for testing, with comments. It is very simple, and the exception-terminated loop technique used is clearly illustrated. Look for the differences between the no_exception methods and the with_exception methods:

package tuning.loop;
  
public class ExceptionDriven
{
  //Use a default size for the number of iterations
  static int SIZE = 1000000;
  
  public static void main(String args[  ])
  {
    //Allow an argument to set the size of the loop.
    if (args.length != 0)
      SIZE = Integer.parseInt(args[0]);
  
    //Run the two tests twice each to ensure there were no
    //initialization effects, reversing the order on the second
    //run to make sure one test does not affect the other.
    no_exception1(  ); with_exception1(  );
    with_exception1(  ); no_exception1(  );
  
    //Execute the array assignment tests only if there is no second
    //argument to allow for large SIZE values on the first test
    //that would give out of memory errors in the second test.
    if (args.length > 1)
      return;
    no_exception2(  ); with_exception2(  );
    with_exception2(  ); no_exception2(  );
    no_exception3(  ); with_exception3(  );
    with_exception3(  ); no_exception3(  );
  }
  public static void no_exception1(  )
  {
    //Standard loop.
    int result;
    long time = System.currentTimeMillis(  );
    for (int i = SIZE; i > 0 ; i--)
      result = SIZE/i;
    System.out.println("Division loop with no exceptions took " + 
      (System.currentTimeMillis(  )-time) + " milliseconds");
  }
  public static void with_exception1(  )
  {
    //Non-standard loop with no test for termination using
    //the ArithmeticException thrown at division by zero to
    //terminate the loop.
    int result;
    long time = System.currentTimeMillis(  );
    try
    {
      for (int i = SIZE; ; i--)
      result = SIZE/i;
    }
    catch (ArithmeticException e) {  }
    System.out.println("Division loop with an exception took " + 
      (System.currentTimeMillis(  )-time) + " milliseconds");
  }
  public static void no_exception2(  )
  {
    //Create the array, get the time, and run the standard loop.
    int array[  ] = new int[SIZE];
    long time = System.currentTimeMillis(  );
    for (int i = 0; i < SIZE ; i++)
      array[i] = 3;
    System.out.println("Assignment loop with no exceptions took " + 
      (System.currentTimeMillis(  )-time) + " milliseconds");
  
    //Garbage collect so that we don't run out of memory for
    //the next test. Set the array variable to null to allow
    //the array instance to be garbage collected.
    array = null;
    System.gc(  );
  }
  public static void with_exception2(  )
  {
    //Create the array, get the time, and run a non-standard
    //loop with no test for termination using the
    //ArrayIndexOutOfBoundsException to terminate the loop.
    int array[  ] = new int[SIZE];
    long time = System.currentTimeMillis(  );
    try
    {
    for (int i = 0; ; i++)
      array[i] = 3;
    }
    catch (ArrayIndexOutOfBoundsException e) {  }
    System.out.println("Assignment loop with an exception took " + 
      (System.currentTimeMillis(  )-time) + " milliseconds");
  
    //Garbage collect so that we don't run out of memory for
    //the next test. Set the array variable to null to allow
    //the array instance to be garbage collected.
    array = null;
    System.gc(  );
  }
  public static void no_exception3(  )
  {
    //Create the Vector, get the time, and run the standard loop.
    java.util.Vector vector = new java.util.Vector(SIZE);
    vector.setSize(SIZE);
    java.util.Enumeration enum = vector.elements(  );
    Object nothing;
    long time = System.currentTimeMillis(  );
    for ( ; enum.hasMoreElements(  ); )
      nothing = enum.nextElement(  );
    System.out.println("Enumeration loop with no exceptions took " + 
      (System.currentTimeMillis(  )-time) + " milliseconds");
  
    //Garbage collect so that we don't run out of memory for
    //the next test. We need to set the variables to null to
    //allow the instances to be garbage collectable.
    enum = null;
    vector = null;
    System.gc(  );
  }
  public static void with_exception3(  )
  {
    //Create the Vector, get the time, and run a non-standard
    //loop with no termination test using the
    //java.util.NoSuchElementException to terminate the loop.
    java.util.Vector vector = new java.util.Vector(SIZE);
    vector.setSize(SIZE);
    java.util.Enumeration enum = vector.elements(  );
    Object nothing;
    long time = System.currentTimeMillis(  );
    try
    {
      for ( ; ; )
        nothing = enum.nextElement(  );
    }
    catch (java.util.NoSuchElementException e) {  }
    System.out.println("Enumeration loop with an exception took " + 
      (System.currentTimeMillis(  )-time) + " milliseconds");
  
    //Garbage collect so that we don't run out of memory for
    //the next test. We need to set the variables to null to
    //allow the instances to be garbage collectable.
    enum = null;
    vector = null;
    System.gc(  );
  }
}