Posts Tagged ‘compiler’

What I have been doing

12 September 2008

Since my last post, I have made another version of the IntersectSquares test, this one using a list class rather than just an array. There were again speed improvements found, but not quite so striking.

Other than that, I have started to prepare my poster (which is due Sunday week, 2008-09-21). Alex gave a talk yesterday with some general advice on how to make good posters, and I talked a bit to my supervisors today about it. I am getting some conflicting advice, though, about how to structure the poster, which parts to emphasise more, where to include examples, and so on.

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

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.

Non-immutable classes, and edge expressions

23 June 2008

I finally have a reasonable version of the optimisation I planned at the beginning of this project working well. Rather than requiring all the classes passed as arguments to pure methods to be immutable, I can do sufficient analysis (along with yet more annotations) to satisfy a weaker requirement. Pure method calls can safely be moved out of loops if (as before) each argument is an invariant reference and either a primitive type or an immutable class type (marked by the @Immutable annotation), but I can now detect a third case, where the following three conditions are all met:

  1. The reference is unique; specifically, it is a local variable annotated @Unique.
  2. There are no statements in the loop which change the object via the reference (i.e. no calls to const methods that are neither @Pure nor @Const).
  3. There is nothing to change objects referenced within the object (the class is marked as @Encapsulated)

The extra annotations (@Unique and @Encapsulated) absolve me from having to solve the aliasing problem, passing the problem onto the programmer (who hopefully understands how eir program works and where aliasing can happen) instead. The @Encapsulated annotation in the last condition is defined to mean that there are guaranteed not to be any references into the internal structure of objects of the class, so the only way to change the state of the object is by calling methods on it.

While I was testing this, I realised that my optimiser did not consider expressions on flow graph edges (which is how JKit expresses conditions in its intermediate representation) at all, neither trying to factor them nor checking them when it looks for statements that might modify an object. To rectify this I had to first compute the set of relevant edges by finding all edges in the flow graph having both source and destination within the set of points in the LoopBody region. I then used this edge set as well as the Point set when factoring expressions and when looking for expressions that might change an object.

Corpus

16 June 2008

So I need to evaluate the optimisations I have so far. It has been suggested by Dave that his SimpleLisp interpreter and the JKit parser might make good tests.

I have had a look through SimpleLisp, and though there are a number of places where methods like List.size() are called inside loops, none of the classes in question are immutable. It thus seems that it will be necessary to implement the next stage of the optimiser (checking whether anything in the loop body will change the object in question) before any useful optimisation can be performed, in this program at least. This is fairly much what I expected, and likely to be the case in many programs.

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);