A more successful test

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.

Advertisements

Tags: , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: