Iterator Invocation Reordering
13 November 2009
We implemented a RECODER source to source transformation that intercepts calls to iterator() and replaces the default iterator with one that reverses the order of iteration.
FunctionalAnalyzer only has one call to iterator() and reverse it causes unit tests to fail.
Of the DaCapo 2006 benchmarks, only bloat and eclipse use java.util iterators (although antlr defines its own completely independent iterator and uses that).
On bloat, we found 416 iterator invocations.
191 of these are used on the default input. 7 of these call remove (which our instrumentation can't handle), and of the remaining 184, 175 (95%) behave the same when reversed.
The invocations that have different behavior appear to mostly be using iterator to find the first item in collection that satisfies some criteria and do something with it.
I don't have an idea of how many items these iterators have in their underlying collection -- if most of the collections only have one item then reversing it has no effect. I need to write some instrumentation to get data on this.
We need to get a sense of whether this 95% number holds up over more benchmarks. DaCapo 2009 (beta version) appears to use more iterators. However, doing a source to source transformation on DaCapo 2009 is going to be a lot of work.
I would recommend rewriting the iterator invocation rewriting transformation to be at the binary level. We might also pull in some other java projects with unit tests and run on those.
I still need to add an option to the iterator invocation reordering that we have to choose a random iteration order rather than a reverse order -- it will be interesting to see if this has an effect.
Method Argument Reordering
16 October 2009
We implemented a RECODER source to source transformation that reorders method parameters (on a per-method basis).
There is a combinatorial explosion of possibilities here (even on a per-method basis) so running these is quite computation time intensive.
We ran all possibilities (where reordering parameters could have side effects) for FunctionalAnalyzer and found one method whose reordering changed behavior -- however, this turned to be a bug (as yet unfixed) in the transformation code.
We're looking at several weeks of computer time to do this for antlr, and probably much more for other dacapo 2006 benchmarks. Once Todd defends and finishes his PLDI paper, we should have enough computer time to look at this again.
There are also some more tricks we can play to remove permutations, but it is fairly important that we get this right, so I've been sticking to simpler ones.
Array Acccess Index Instrumentation
21 September 2009
We instrumented all array loads and stores (at the binary level using BCEL) on dacapo 2006 default and noted if the access would fail due to an out of bound index.
dacapo_antlr: 45671306 accesses of which 0 failed.
dacapo_bloat: 3975726 accesses of which 0 failed.
dacapo_chart: 47499882 accesses of which 0 failed.
dacapo_eclipse: 1581311344 accesses of which 19587 failed.
dacapo_fop: No results: instrumented code is too long in org/apache/fop/render/pdf/CodePointMapping
dacapo_hsqldb: 86852684 accesses of which 0 failed.
dacapo_jython: 110266869 accesses of which 0 failed.
dacapo_luindex: 680194988 accesses of which 0 failed.
dacapo_lusearch: 139348538 accesses of which 0 failed.
dacapo_pmd: 38370104 accesses of which 0 failed.
dacapo_xalan: 145797605 accesses of which 0 failed.
Later investigation (25 September 2009) showed that all of the failures for eclipse were reads off the end of a character array in:
org.eclipse.jdt.internal.compiler.parser.Scanner.getNextToken(Scanner.java:899)
In this case, the scanner is using the out of bounds exception to manage its control flow when it runs out of available input rather than doing so explicitly. There are other methods in the class that appear to use that same technique -- however, they don't appear to be exercised in the benchmark.
Checkcast Instrumentation
19 September 2009
We instrumented all casts (at the binary level using BCEL) on dacapo 2006 default and noted if the cast would fail. At first we tried static instrumentation with BCEL -- we later had to move to applying BCEL dynamically with java.lang.Instrument because there was so much dynamic class loading going on.
dacapo_antlr: 1623328 casts of which 0 failed.
dacapo_bloat: 81124115 casts of which 0 failed.
dacapo_chart: 28727851 casts of which 0 failed.
dacapo_eclipse: 37370991 casts of which 0 failed.
dacapo_fop:4793541 casts of which 0 failed.
dacapo_hsqldb: 26166579 casts of which 0 failed.
dacapo_jython: 29731017 casts of which 0 failed.
dacapo_luindex: 13403798 casts of which 0 failed.
dacapo_lusearch: 10342019 casts of which 0 failed.
dacapo_pmd: 16060843 casts of which 0 failed.
dacapo_xalan: 16704143 casts of which 0 failed.