Optimizing arbitrary-precision integer math
Charles Oliver Nutter
safely in JRuby. Perhaps this will work for us and for other languages
attempting to do the same thing.
So the fundamental problem here is that we only get one return type,
so we have to choose either a primitive (int/long) or a reference type
(for the overflow case). That was the showstopper for me, and talking
to others doing this sort of optimization it seemed like there was no
good solution.
But then I had a "duh" moment tonight once I returned to SF: integer
math is side-effect free!
So in the following dynopt'ed code from JRuby, you can see we have a
serial number check before the direct dispatch to RubyFixnum.op_minus:
LDC 499
INVOKESTATIC
org/jruby/javasupport/util/RuntimeHelpers.isGenerationEqual
(Lorg/jruby/runtime/builtin/IRubyObject;I)Z
IFNE L26
ALOAD 11
CHECKCAST org/jruby/RubyFixnum
ALOAD 1
LDC 1
INVOKEVIRTUAL org/jruby/RubyFixnum.op_minus
(Lorg/jruby/runtime/ThreadContext;J)Lorg/jruby/runtime/builtin/IRubyObject;
So if we pass the check, we know we're invoking the builtin Fixnum#+
method that has no side effects. Since it has no side effects, we
could insert the hacker's delight overflow guard into the compiled
bytecode as a second check, and then branch to an Object version of
the same algorithm! Ideally that branch will never be followed, and
we're good to go.
Managing the stack is still tricky, but at least the return value
issue can be solved.
- Charlie
Ola Bini
> I think I just thunk up a way to optimize integer math to primitives
> safely in JRuby. Perhaps this will work for us and for other languages
> attempting to do the same thing.
>
> So the fundamental problem here is that we only get one return type,
> so we have to choose either a primitive (int/long) or a reference type
> (for the overflow case). That was the showstopper for me, and talking
> to others doing this sort of optimization it seemed like there was no
> good solution.
>
> But then I had a "duh" moment tonight once I returned to SF: integer
> math is side-effect free!
This is of course not true for division - which I guess you already
thought about.
Except for that, nice result.
Cheers
>
> So in the following dynopt'ed code from JRuby, you can see we have a
> serial number check before the direct dispatch to RubyFixnum.op_minus:
>
> LDC 499
> INVOKESTATIC
> org/jruby/javasupport/util/RuntimeHelpers.isGenerationEqual
> (Lorg/jruby/runtime/builtin/IRubyObject;I)Z
> IFNE L26
> ALOAD 11
> CHECKCAST org/jruby/RubyFixnum
> ALOAD 1
> LDC 1
> INVOKEVIRTUAL org/jruby/RubyFixnum.op_minus
> (Lorg/jruby/runtime/ThreadContext;J)Lorg/jruby/runtime/builtin/IRubyObject;
>
> So if we pass the check, we know we're invoking the builtin Fixnum#+
> method that has no side effects. Since it has no side effects, we
> could insert the hacker's delight overflow guard into the compiled
> bytecode as a second check, and then branch to an Object version of
> the same algorithm! Ideally that branch will never be followed, and
> we're good to go.
>
> Managing the stack is still tricky, but at least the return value
> issue can be solved.
>
> - Charlie
>
--
Ola Bini (http://olabini.com)
Ioke - JRuby - ThoughtWorks
"Yields falsehood when quined" yields falsehood when quined.
John Wilson
> I think I just thunk up a way to optimize integer math to primitives
> safely in JRuby. Perhaps this will work for us and for other languages
> attempting to do the same thing.
Ng has pretty much the Groovy semantics for arithmetic operators which
means that any arithmetic operation can be overridden globally or on a
per thread basis. The standard semantics are Java's but there is a
standard override which gives graceful handling of overflow.
Arithmetic operations are translated into method calls on a thread
local dispatcher.
Taking addition as an example: there is an addQuick() method with
takes two ints and returns an int and an add() method which takes two
ints and returns an Object (there are lots of flavours of addition
methods which deal with different type combinations but we can ignore
them for now).
When I know I'm adding two ints I use the addQuick(int,int) method. If
the semantics of add have been changed so that the operation no longer
returns an int the addQuick() method throws an exception. I catch this
exception and use the Object version of add() to perform the
operation.
The effect of this is to try to do the calculation using normal, fast,
operations and if any of the operations can't be performed that way
throw the entire calculation away and do it the slow, general, way.
Example
1 + a + 2 (a is known to be an int)
try {
tc.addQuick(tc.addQuick(1, a), 2)
catch(CantDoPimativeOperationException e) {
tc.add(tc.add(tc.wrap(1), tc.wrap(a)), tc.wrap(2))
}
tc is the per thread dispatch object and wrap() turns a primitive into
the appropriate object.
It seems a similar approach to the one you are suggestion and does
result in reasonable performance.
John Wilson