I've taken the time to write a small prototype (by hand :( )
see http://www-igm.univ-mlv.fr/~forax/tmp/jsr292-deopt.zip
using Fibonacci as John suggest.
The idea is to transfer the control from fibo written using
ints to fibo written using Object (BigInteger at runtime).
If an operation overflow, an exception is thrown and
the stack is reconstructed to restart the operation on objects.
Moreover, a call can now fail because the result value is not
an int anymore, in that case, the new return value is thrown
inside an exception (one by thread), again the exception is catched
and the control flow is transfered to the version that use objects
just after the call.
To summarize, you can transfer the control flow, either because
an operation fail or because the return value of a call is not
an int anymore.
public static int fibo(int n) {
if (n < 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
In fibo, we have 5 deoptimization pointcuts, n -1 can overflow,
n - 2 can overflow, + can overflow, the first call to fibo can return
a big integer, the second call to fibo can return a big integer.
Each pointcut is encapsulated in a try catch that jump to
a specific exception handler. All exception handlers first push a constant
(corresponding to the pointcut number) and then jump to the same
code that load all variables that potentially store the stack and
do an invokedynamic
invokedynamic calls a specific function (I have called it an exit function)
which constructed from the fibonacci function but using objects.
Depending on the pointcut number, a preamble code jump before an operation
to restart it or after a function call to replace the return value stored in
the exception.
Because fibo is recursive, it can also call a plain old fibonacci
function using objects
without preamble jump code.
You can note that the exit function (and the plain function if the
function is recursive)
can be generated lazily, only if needed i.e. if an overflow occurs.
Now the bench on my laptop for fibo(45), i.e when there is no overflow:
$ time java -cp .:classes JavaFibo // classical Java, fibo(45) using ints
real0m7.393s
user0m7.238s
sys0m0.014s
$ time java -cp .:classes JavaLongFibo // classical Java, fibo (45)
using longs
real0m6.021s
user0m6.000s
sys0m0.017s
$ time java -cp .:classes Fibo// ints + overflow detecttion
real0m8.263s
user0m8.112s
sys0m0.015s
Not that bad but it's only with 5 pointcuts.
For the record, here is the time for fibo(47):
$ time java -cp .:classes Fibo
real3m21.727s
user3m22.882s
sys0m0.513s
I know that the deoptimization bootstrap method can install
a transfer method that is a little faster but I think
that either BigInteger are slow or I have made a mistake
in the deoptimization code.
Anyway, the result value is Ok.
Rémi
On 09/08/2011 09:47 PM, John Rose wrote:
On Sep 8, 2011, at 4:57 AM, Thomas Wuerthinger wrote:
Why not the following code pattern? Does it generate too many bytecodes?
That's a reasonable alternative.
It generates data movement bytecodes O(L * M), where L is the average
number of live values at deopt points and M is the number of deopt
points. The quadratic exponent on bytecode size bothers me, at least
a little.
The other pattern pins the live values into a common set of locals,
reducing data movement bytecodes (and probably compiled code data
movement).
Using Remi's trick of an invokedynamic instead of a varargs array, the
number of data movement bytecodes can be cut down about 3x (no
iconst/aastore). But it's still quadratic.
-- John
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
___
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
