Testing manual optimisation

19 August 2008

I have just made a few simple tests to see how much code movement of the sort performed by my optimisation stage actually helps Java programs’ run time, and the results are fairly disappointing.

First, I tried moving calls to Array.length, using this code:

public class ManualArray {
public static void main(String[] args) {
char[] array = new char[10000000];

long startTime = System.currentTimeMillis();
for (int i = 0; i < array.length * 100; ++i) {
}
long normalTime = System.currentTimeMillis() - startTime;

startTime = System.currentTimeMillis();
int length = array.length;
for (int i = 0; i < length * 100; ++i) {
}
long factoredTime = System.currentTimeMillis() - startTime;

startTime = System.currentTimeMillis();
for (int i = 0; i < array.length * 100; ++i) {
}
long normalTime2 = System.currentTimeMillis() - startTime;

System.out.println("Normal: " + normalTime + " ms");
System.out.println("Factored: " + factoredTime + " ms");
System.out.println("Normal: " + normalTime2 + " ms");
}
}

The output from running this (compiled with javac 1.6.0_03-p3, running with java 1.6.0_03-p3, both from Sun) looks something like this:

$ java ManualArray
Normal: 2172 ms
Factored: 730 ms
Normal: 726 ms

Running with java -server to use the Java HotSpot Server VM, the results are not promising either:

$ java -server ManualArray
Normal: 9 ms
Factored: 0 ms
Normal: 0 ms

I then tested moving a simple method call:

public class ManualMethod {
public static void main(String[] args) {
TestCollection list = new TestCollection(1000000000);

long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); ++i) {
}
long normalTime = System.currentTimeMillis() - startTime;

startTime = System.currentTimeMillis();
int length = list.size();
for (int i = 0; i < length; ++i) {
}
long factoredTime = System.currentTimeMillis() - startTime;

startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); ++i) {
}
long normalTime2 = System.currentTimeMillis() - startTime;

System.out.println("Normal: " + normalTime + " ms");
System.out.println("Factored: " + factoredTime + " ms");
System.out.println("Normal: " + normalTime2 + " ms");
}
}

And the results this time:

$ java ManualMethod
Normal: 1451 ms
Factored: 725 ms
Normal: 724 ms
$ java -server ManualMethod
Normal: 4 ms
Factored: 0 ms
Normal: 0 ms

This is rather disappointing, as it suggests that my optimisations will not actually help much. I am inclined to suspect that the reason the code movement does not help is that the JIT compiler in the JVM already does some optimisation of this sort (perhaps by inlining short methods), though it is also possible that the method call overhead is really low.

If I make TestCollection.size() slower by adding some useless code to it, then the optimisation makes a lot more difference:

$ java ManualMethod
Normal: 11253 ms
Factored: 835 ms
Normal: 11134 ms

If we use the server VM, the results are very strange:

$ java -server ManualMethod
Normal: 7 ms
Factored: 0 ms
Normal: 5773 ms

I cannot see why the first normal run should be so much quicker than the second: the reverse was observed in all the other tests before this, which was presumably due to the JVM doing some JIT compilation once it decided that this would be worthwhile.

Advertisements

Optimisations in SimpleLisp

27 July 2008

Now, after a bit more work since my last post, when I compile the SimpleLisp interpreter, I get the following optimisations applied:

Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '161l[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '161l[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '("type error in ""[java.lang.String] ++ (fn[java.lang.String] ++ """[java.lang.String])[java.lang.String])[java.lang.String]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression 'cs[java.lang.Class[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'cs[java.lang.Class[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '(!true[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '(1[int] + this[org.simplelisp.interpreter.LispFunction].numEval[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '(1[int] + this[org.simplelisp.interpreter.LispFunction].numEval[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '5es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '5es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.

Note that these include some traditional loop invariant code movement optimisations as well as my particular optimisation of pure method calls, as allowed by the more general approach I mentioned recently.

A little refactoring generalises to allow a little more optimisation

24 July 2008

Up till now, my optimisation stage would only move expressions out of loops if they were exactly one of the cases discussed (Array.length or call to a pure method meeting various conditions). In doing the checking required to detect when such movement was safe, however, I had a method in my code called isInvariantReference which checks whether a given expression can be guaranteed not to change within the loop, such as if it is a constant, a local variable which is not assigned to in the loop, an arithmetic expression with all parts meeting the same condition, or various other types of expression which will not change value. This is needed, for example, as part of the condition imposed on arguments to the pure method call for it to be able to be moved out of the loop.

I realised that this isInvariantReference method was in fact doing a very similar thing to my checks for expressions that can be moved out of the loop. By combining the two, I can move compound expressions rather than just the actual method calls or field dereferences, and so make the optimisation slightly more effective. The change I made was to have isInvariantReference also detect the Array.length and pure method call cases, and then replace the part that previously detected these cases with a call to isInvariantReference (and some other simple checks, to prevent infinite recursion). This means that the usual loop invariant code motion optimisations can be made in addition to my new optimisations. This refactoring also results in a little less code duplication in my compiler stage.

For example, take the code snippet below:

for (int i = 0; i < listA.size() * listB.size(); ++i) {
System.out.println(listA.getWith(i, listB));
}

Assuming the appropriate conditions are met, this code would before have been optimised to something like this:

int $invariant0 = listA.size();
int $invariant1 = listB.size();
for (int i = 0; i < $invariant0 * $invariant1; ++i) {
System.out.println(listA.getWith(i, listB));
}

It will now be transformed into something like this:

int $invariant0 = listA.size() * listB.size();
for (int i = 0; i < $invariant0; ++i) {
System.out.println(listA.getWith(i, listB));
}

This saves a local variable and a multiplication each time through the loop.

Many other examples are possible. To be honest this is not likely to be a big improvement over the optimisation as it stood before, but it still seems worth doing, even if only because it makes the code nicer.

Milestone 2

22 July 2008

I submitted my milestone 2 report a few of days ago. You can read it here.

Annotating SimpleLisp

16 July 2008

I have now added a fair number of annotations to Dave’s SimpleLisp interpreter, and tested compiling it with my loop invariant code movement optimisations. Results were moderately encouraging: there were a fair number of cases where the Array.length optimisation could be applied, and a few for pure methods (all of which were lengths of collection types).

Writing milestone 2 report…

12 July 2008

I have been spending the last several days writing my second milestone report. I hope to have a mostly complete draft ready soon, so that I can send it to my supervisor and others for review and comments. It is due on Sunday 2008-07-20.

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.

Progress

10 June 2008

Wow, it has been a while since I posted here. I have been really busy with other projects, assignments and the COMP413 exam, but now I have a few days to work on this project and have made some progress.

I now have my optimiser actually moving method calls out of loops, in a (relatively) simple but still useful case. It is possible to safely move a method call if the method is annotated as @pure and for each argument to the method call (including the target object):

  • The variable (primitive value or reference) is invariant within the loop, i.e. it always has the same value or points to the same object, and
  • either:
    • It is of a primitive type, or
    • the class type is immutable (annotated as @immutable at the class declaration)

I have successfully implemented the code to check for this case and factor the method call out of the loop (as I earlier did for @moveable methods and dereferences of Array.length under certain conditions).

The more general case is when, rather than the class being immutable, the compiler can check that

  • The reference (variable) is annotated as @unique, meaning that there are guaranteed to be no aliases, and
  • there are no statements in the loop which change the object via the reference (i.e. no calls to non-@const methods), and
  • there is nothing to change objects referenced within the object.

It is fairly clear how to check the first two parts, but I cannot yet see how to check the third condition.

I probably have not described this very well. Oh well. I will have to write a full report eventually.

Presentation

16 May 2008

Today (in less than two hours, in fact) I give a short presentation to ELVIS of my work so far. Here are the slides I have put together. They are mostly code examples and diagrams; for the actual content you should read my milestone report.

If nothing else I learnt the basics of Beamer.