Posts Tagged ‘loop invariant code movement’

A more successful test

24 August 2008

Talking to a friend this afternoon, I thought of another case that might be relatively common where my optimisation would apply and potentially save a fair bit of time. The situation is where two nested loops are used to loop through different arrays or lists, and then inside the inner loop are expressions that reference particular values from the collections indexed by their respective loop variables. To look at it another way, this sort of pattern is working with the Cartesian product of the two arrays.

Here is a simple example:

@Unique int[] a = new int[10000];
@Unique int[] b = new int[20000];

int sum = 0;

for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < b.length; ++j) {
sum += a[i] * b[j];

System.out.println("Sum: " + sum);

My optimisations move 3 expressions: a.length and b.length can be moved out of both loops, while a[i] can be moved out of the inner loop. It is this latter optimisation that is the most helpful.

Compiling this with JKit with and without my optimisations and then running with Sun Java 1.6.0 gives these times:
Without optimisation:

$ time java NestedProduct
Sum: 0

real 0m0.923s
user 0m0.829s
sys 0m0.051s

With optimisation:

$ time java NestedProduct
Sum: 0

real 0m0.724s
user 0m0.657s
sys 0m0.019s

Supporting code movement in this case required a few changes to my JKit stage, so it will be interesting to see if this allows any more optimisation in my evaluation programs as well.