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 using 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 misses out the termination test in the
for
loop, thus making the loop infinite. But these
latter loops are put inside a try-catch
block to
catch an exception that 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.
I found the results of my test runs (summarized in Table 7-1) to be variable due to variations 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.2 |
1.2 no JIT |
1.3 |
HotSpot 1.0 |
1.1.6 |
---|---|---|---|---|---|
Integer division |
~2% |
~5% |
None[a] |
~10% |
~2% |
Assignment to loop |
None |
~75% |
~10% |
~30% |
None |
|
None |
~10% |
~20% |
None[b] |
~10% |
[a] The timings varied enormously as the test was repeated within a VM. There was no consistent speedup. [b] The exception-driven case was 40% faster initially. After the first test, HotSpot successfully optimized the normal loop to make it much faster, but failed to optimize the exception-driven loop. |
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( ); } }
18.216.83.240