Inlining heuristic trouble

Rémi Forax forax at univ-mlv.fr
Wed Jun 15 08:26:12 PDT 2011


I've just finished to code a sample for the cookbook that does
integer operation (+ and -) with overflow (to BigInteger).

https://code.google.com/p/jsr292-cookbook/source/browse/#svn%2Ftrunk%2Fbinary-operation%2Fsrc%2Fjsr292%2Fcookbook%2Fbinop

For a code like this one:
max = ...
for(i=0; i<max; i = i + 1) {
   // do nothing
}

i + 1 is transformed to:

if (i.getClass() == Integer.class) {
   int j = i.intValue();
   if (j != MAXINT) {
     i = Integer.valueOf(j + 1);
   } else {
      fallback();
   }
} else {
   fallback();
}

but there is a bad news, perf of  i + 1 considering 1 as a constant
are *worst* (2 or 3 times !!) that using the double xor trick.

// with the optimization
[forax at localhost binary-operation]$ time java -cp .:classes PerfOpt
real    0m0.954s
user    0m1.030s
sys    0m0.087s

// without
[forax at localhost binary-operation]$ time java -cp .:classes Perf
real    0m0.378s
user    0m0.407s
sys    0m0.081s

Knowing that the double xor trick does 4 comparisons and
the constant trick only two, the problem comes from either
my code or the way the VM inlines the method handles.

I've found no problem in my code so ... :)
Playing with the VM logs, the method containing (j != MAXINT) is not inlined
because it hits the maximum depth (as far as I remember this problem
is new, the older algorithm, the one that didn't propagate MDO, didn't 
exhibit this problem).
Moreover, the VM tries to inline some parts of the fallback method 
(twice :( )
even if this code never called.

The way the VM decides to inline method handles in this case is not good 
at all.

Rémi



More information about the mlvm-dev mailing list