Posts Tagged ‘code movement’

More testing

3 September 2008

I wrote a slightly more interesting program called IntersectSquares, which generates an array of a large number of rectangles, then counts how many times they intersect each other. This is written in a fairly naive way, so there are a fair few expression for the optimiser to move out of the loop. I tried it here with 100,000 rectangles:

With jkit:

andrew@rise:test cases$ time java IntersectSquares; time java IntersectSquares
3290 intersections

real 0m58.843s
user 0m58.470s
sys 0m0.020s
3290 intersections

real 0m58.918s
user 0m58.491s
sys 0m0.040s

With javac:

andrew@rise:test cases$ time java IntersectSquares; time java IntersectSquares; time java IntersectSquares
3290 intersections

real 1m4.690s
user 1m3.783s
sys 0m0.030s
3290 intersections

real 1m4.908s
user 1m3.805s
sys 0m0.051s
3290 intersections

real 1m4.209s
user 1m3.695s
sys 0m0.041s

Advertisements

A first simple optimisation

25 April 2008

As a very simple but safe code-movement optimisation, I have made my stage move calls to Array.length where the Array in question is stored in a final local variable out of loops. This is safe because once an array has been created its length cannot change, even though its contents may. As the reference is in a final local variable we are also guaranteed that the same array is indeed being referred to each time around the loop.

I have just realised that this is still not quite safe, as there could be a final local variable declared inside the scope of the loop, in which case it would be re-initialised (possibly to a different value) each time through the loop.

For example:

int j = 0;
while (j < 5) {
final int[] innerArray = new int[j];
System.out.println("innerArray length " + innerArray.length);
++j;
}

Here the value of innerArray.length will change on each iteration of the loop, even though innerArray is final.

Constant folding etc.

17 April 2008

To make a start with writing optimisation stages in JKit I have written a simple constant folding optimisation stage. This will do some simple compile-time evaluation of arithmetic expressions, for example turning int x = 1 + 2; into int x = 3;.

After talking to Lindsay yesterday we have decided that the next step is for me to write some code to traverse the flow graph to find loops, in particular to identify which vertices are the tops of loops. I still need to work out where this and other information discovered during the traversal should be stored: perhaps in the flow graph somehow, perhaps in separate data structures kept locally, or maybe somewhere else.

As a first step to doing the actual code movement of loop invariants I will probably add an annotation for certain method calls to say that they certainly can be moved (e.g. if they just return a constant value and have no side-effects). The next step will probably be more annotations for objects which the programmer guarantees will have no aliases (somewhat like ownership, I think), or perhaps some sort of immutability.

Lindsay suggested that another possible direction is to do some sort of constant folding / propagation for immutable objects like Strings (for the length() method, for example), or partially immutable objects like arrays where the length cannot change. The length could be found once and cached in a local variable, or it might be possible to infer the length from how the array is constructed. For example, it would be nice if the following code:

int[] a = new int[n];
System.out.println(a.length);

could be transformed to

int[] a = new int[n];
System.out.println(n);