Posts Tagged ‘loops’

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.



26 March 2008

I have come to realise that there will be more problems than I had initially thought. In particular, it seems that working out whether a given object is guaranteed to remain constant throughout a loop is difficult, as any other object could potentially hold a reference to it through which to change it opaquely. Even if we assume that there is no concurrency, any call within the loop to a non-pure method on any object could change it.

Presumably people have realised this problem and others before, so I am trying to find out what work has already been done in the area. I have looked at a number of compilers textbooks (listed below) and found some general information about code motion, induction variable elimination, strength reduction and factoring along with lots of data flow analysis to support these, but nothing about the problems with my approach.