High cost of failed Math.*Exact calls

[Charles Oliver Nutter]

Chen Lian wrote:
> can you showcase any related ruby behavior using this model?

The use case is normal Ruby integer math: there's only one Integer type
that is backed either by 64-bit(ish) fixnums (wrapping a Java long) and
arbitrary precision bignums (wrapping BigInteger).

The logic in JRuby is using addExact, subtractExact, and multiplyExact to
reduce the cost of repeatedly checking for fixnum overflow. If an algorithm
stays on the fixnum side, these functions perform quite well. If an
algorithm produces strictly increasing values or lives entirely outside the
64-bit long range, we stop doing these checks because we're working with
bignum the entire time. The problem arises when you have an algorithm that
dances along that edge, repeatedly overflowing and falling back on bignum
math. In this case, it is due to a prime-detection algorithm that
repeatedly fails multiplyExact overflow checks while calculating modulo
values (using a multiply and subtract algorithm from the C implementation
of Ruby that we could possibly rewrite).

The "exact or alternative value" is what would work for us here; either
that would be a sigil value represented as a 64-bit long (as I described in
my first email) or once we can guarantee that no allocation occurs, a
nullable return value where null would represent overflow. My concern with
putting this all on Valhalla's back is that we might not see a "fix" for
many more releases. The trivial "multiplyExactOrElse(long a, long b, long
sigil) would be trivial to add in the short term, other than the hidden
cost of expanding the API.

Roger Riggs wrote:
> Another API alternative would be to add a version that triggers a lambda
on overflow and allow the caller to determine the value or throw.

If the result of overflow is that we need to produce a BigInteger, though,
we'd still have to indicate that to the caller via the narrow communication
channel that is a long. I could see this going two ways: we could return a
sigil long that represents overflow; or we could raise a preallocated
exception to jump back to the call location and retry. The former is no
better than just providing an API that takes a long sigil. The latter
eliminates the cost of creating the exception but not the cost of raising
it.

I also continue to have concerns about using lambdas in megamorphic
situations, since C2 does not do any method-splitting optimizations. My
lambdas would never inline, so the cost of overflow would now increase by
the cost of a call on top of the exception unroll.

Remi Forax wrote:
> as far as i remember, c2 is alble to transform a ... to a jump on
overflow ("jo")

I don't doubt that it optimizes the operation to a jo instruction, but from
what I've seen in profiles it can't eliminate the cost of constructing and
raising the exception (I can't say I've ever seen C2 accomplish this). The
frustrating part is that I'd wager hardly anyone actually cares about the
exception or its stack trace, so it's like using a jackhammer to crack a
walnut; we just want to fall back on alternative logic on overflow, but
have to pay this tremendous cost to do it.

FWIW, JRuby implements this logic all in a single method:
https://github.com/jruby/jruby/blob/master/core/src/main/java/org/jruby/RubyFixnum.java#L603-L611

> it was better when one exception was raised to trash the generated code
and generate a new code

The challenge in JRuby is that this is all done on the other side of a
dynamic call against a Ruby "Integer". At this point we still don't support
deopt in bytecode-compiled Ruby code due to complexity (it's just little
old me here maintaining this code and trying not to break production apps)
and overhead (we already struggle with bytecode size... Ruby is very
complex). As a result, the code always will dispatch through the same
fixnum logic and continue to raise exceptions just to fall back on bignum.

Raffaelo Giulietti wrote:
> For your specific multiplication use case you might try with

Not bad! I too would hope that the either the JIT would optimize to one
instruction or the CPU would run them in parallel anyway. And if we have
already determined that the value does not overflow with multiplyHigh,
there's no need to multiplyExact. I will consider this for JRuby 10 (due
out early 2025 and which will require Java 21 mininum).

Sadly my only option for JRuby 9.4.x, which still supports Java 8, will be
to restore the old manual overflow checking and penalize fixnum-range
algorithms a bit. I guess that's motivation for uses to upgrade to 10?

On Thu, Dec 12, 2024 at 10:45 PM Chen Liang <chen.l.liang at oracle.com> wrote:

> Seems what we desire here is an "exact or alternative value" model instead
> of an "avoid overflow" model. This sounds interesting - can you showcase
> any related ruby behavior using this model?
>
> I think an alternative can be *IfExact that returns a nullable value, if
> we do not need more information about the failure. Such a model is
> flattenable in the current programming model of Valhalla and can fulfill
> some of our needs. (I actually wonder if C2 can already inline and escape
> analysis in such a scenario)
>
> Unfortunately, before stack inlining drops, we are stuck with some
> tradeoffs - for example, current APIs still stick with Optional as it
> offers fluent code, which nullable types currently lack, even when we are
> promised a more flexible nullable type in the current roadmap of Valhalla.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20241216/6344f228/attachment-0001.htm>