Posts Tagged ‘optimisations’

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

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.

Reading

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.