RFR 7131192: BigInteger.doubleValue() is depressingly slow
Louis Wasserman
lowasser at google.com
Mon Jun 17 18:32:11 UTC 2013
The comments mention SIGNIFICAND_BITS, which I think should probably be
SIGNIFICAND_WIDTH?
On Mon, Jun 17, 2013 at 11:25 AM, Brian Burkhalter <
brian.burkhalter at oracle.com> wrote:
> I am unable at the moment to copy anything to cr.openjdk.java.net so I am
> including the webrev as a patch below. I'll copy it to the online location
> as soon as possible.
>
> The patch included at the end of this message fixes this issue
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7131192
>
> Code review of the source and accompanying test was effected and all
> pertinent regression tests passed. Previous performance testing showed a
> massive improvement:
>
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-February/014697.html
>
> Note that as correctness testing of 7131192 depends on the patch
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/017958.html
>
> having already been applied, the present fix cannot be integrated until
> this prior patch has been applied.
>
> Thanks,
>
> Brian
>
> # HG changeset patch
> # Parent 35d5a218004fb1fc64c92fd3151d0a48d4f378e9
> 7131192: BigInteger.doubleValue() is depressingly slow.
> Summary: Replace invocations Double.parseDouble(toString()) and
> Float.parseFloat(toString()) with direct implementation of conversion from
> signum and mag.
> Reviewed-by: TBD
> Contributed-by: Louis Wasserman <lowasser at google.com>
>
> diff -r 35d5a218004f src/share/classes/java/math/BigInteger.java
> --- a/src/share/classes/java/math/BigInteger.java Thu Jun 13
> 14:18:52 2013 -0700
> +++ b/src/share/classes/java/math/BigInteger.java Fri Jun 14
> 14:10:43 2013 -0700
> @@ -33,6 +33,9 @@
> import java.io.*;
> import java.util.Arrays;
>
> +import sun.misc.DoubleConsts;
> +import sun.misc.FloatConsts;
> +
> /**
> * Immutable arbitrary-precision integers. All operations behave as if
> * BigIntegers were represented in two's-complement notation (like Java's
> @@ -2966,8 +2969,72 @@
> * @return this BigInteger converted to a {@code float}.
> */
> public float floatValue() {
> - // Somewhat inefficient, but guaranteed to work.
> - return Float.parseFloat(this.toString());
> + if (signum == 0) {
> + return 0.0f;
> + }
> +
> + int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0])
> - 1;
> +
> + // exponent == floor(log2(abs(this)))
> + if (exponent < Long.SIZE - 1) {
> + return longValue();
> + } else if (exponent > Float.MAX_EXPONENT) {
> + return signum > 0 ? Float.POSITIVE_INFINITY :
> Float.NEGATIVE_INFINITY;
> + }
> +
> + /*
> + * We need the top SIGNIFICAND_BITS + 1 bits, including the
> "implicit"
> + * one bit. To make rounding easier, we pick out the top
> + * SIGNIFICAND_BITS + 2 bits, so we have one to help us round up
> or
> + * down. twiceSignifFloor will contain the top SIGNIFICAND_BITS +
> 2
> + * bits, and signifFloor the top SIGNIFICAND_BITS + 1.
> + *
> + * It helps to consider the real number signif = abs(this) *
> + * 2^(SIGNIFICAND_BITS - exponent).
> + */
> + int shift = exponent - FloatConsts.SIGNIFICAND_WIDTH;
> +
> + int twiceSignifFloor;
> + // twiceSignifFloor will be == abs().shiftRight(shift).intValue()
> + // We do the shift into an int directly to improve performance.
> +
> + int nBits = shift & 0x1f;
> + int nBits2 = 32 - nBits;
> +
> + if (nBits == 0) {
> + twiceSignifFloor = mag[0];
> + } else {
> + twiceSignifFloor = mag[0] >>> nBits;
> + if (twiceSignifFloor == 0) {
> + twiceSignifFloor = (mag[0] << nBits2) | (mag[1] >>>
> nBits);
> + }
> + }
> +
> + int signifFloor = twiceSignifFloor >> 1;
> + signifFloor &= FloatConsts.SIGNIF_BIT_MASK; // remove the implied
> bit
> +
> + /*
> + * We round up if either the fractional part of signif is strictly
> + * greater than 0.5 (which is true if the 0.5 bit is set and any
> lower
> + * bit is set), or if the fractional part of signif is >= 0.5 and
> + * signifFloor is odd (which is true if both the 0.5 bit and the
> 1 bit
> + * are set). This is equivalent to the desired HALF_EVEN rounding.
> + */
> + boolean increment = (twiceSignifFloor & 1) != 0
> + && ((signifFloor & 1) != 0 || abs().getLowestSetBit() <
> shift);
> + int signifRounded = increment ? signifFloor + 1 : signifFloor;
> + int bits = ((exponent + FloatConsts.EXP_BIAS))
> + << (FloatConsts.SIGNIFICAND_WIDTH - 1);
> + bits += signifRounded;
> + /*
> + * If signifRounded == 2^24, we'd need to set all of the
> significand
> + * bits to zero and add 1 to the exponent. This is exactly the
> behavior
> + * we get from just adding signifRounded to bits directly. If the
> + * exponent is Float.MAX_EXPONENT, we round up (correctly) to
> + * Float.POSITIVE_INFINITY.
> + */
> + bits |= signum & FloatConsts.SIGN_BIT_MASK;
> + return Float.intBitsToFloat(bits);
> }
>
> /**
> @@ -2986,8 +3053,80 @@
> * @return this BigInteger converted to a {@code double}.
> */
> public double doubleValue() {
> - // Somewhat inefficient, but guaranteed to work.
> - return Double.parseDouble(this.toString());
> + if (signum == 0) {
> + return 0.0;
> + }
> +
> + int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0])
> - 1;
> +
> + // exponent == floor(log2(abs(this))Double)
> + if (exponent < Long.SIZE - 1) {
> + return longValue();
> + } else if (exponent > Double.MAX_EXPONENT) {
> + return signum > 0 ? Double.POSITIVE_INFINITY :
> Double.NEGATIVE_INFINITY;
> + }
> +
> + /*
> + * We need the top SIGNIFICAND_BITS + 1 bits, including the
> "implicit"
> + * one bit. To make rounding easier, we pick out the top
> + * SIGNIFICAND_BITS + 2 bits, so we have one to help us round up
> or
> + * down. twiceSignifFloor will contain the top SIGNIFICAND_BITS +
> 2
> + * bits, and signifFloor the top SIGNIFICAND_BITS + 1.
> + *
> + * It helps to consider the real number signif = abs(this) *
> + * 2^(SIGNIFICAND_BITS - exponent).
> + */
> + int shift = exponent - DoubleConsts.SIGNIFICAND_WIDTH;
> +
> + long twiceSignifFloor;
> + // twiceSignifFloor will be == abs().shiftRight(shift).longValue()
> + // We do the shift into a long directly to improve performance.
> +
> + int nBits = shift & 0x1f;
> + int nBits2 = 32 - nBits;
> +
> + int highBits;
> + int lowBits;
> + if (nBits == 0) {
> + highBits = mag[0];
> + lowBits = mag[1];
> + } else {
> + highBits = mag[0] >>> nBits;
> + lowBits = (mag[0] << nBits2) | (mag[1] >>> nBits);
> + if (highBits == 0) {
> + highBits = lowBits;
> + lowBits = (mag[1] << nBits2) | (mag[2] >>> nBits);
> + }
> + }
> +
> + twiceSignifFloor = ((highBits & LONG_MASK) << 32)
> + | (lowBits & LONG_MASK);
> +
> + long signifFloor = twiceSignifFloor >> 1;
> + signifFloor &= DoubleConsts.SIGNIF_BIT_MASK; // remove the
> implied bit
> +
> + /*
> + * We round up if either the fractional part of signif is strictly
> + * greater than 0.5 (which is true if the 0.5 bit is set and any
> lower
> + * bit is set), or if the fractional part of signif is >= 0.5 and
> + * signifFloor is odd (which is true if both the 0.5 bit and the
> 1 bit
> + * are set). This is equivalent to the desired HALF_EVEN rounding.
> + */
> + boolean increment = (twiceSignifFloor & 1) != 0
> + && ((signifFloor & 1) != 0 || abs().getLowestSetBit() <
> shift);
> + long signifRounded = increment ? signifFloor + 1 : signifFloor;
> + long bits = (long) ((exponent + DoubleConsts.EXP_BIAS))
> + << (DoubleConsts.SIGNIFICAND_WIDTH - 1);
> + bits += signifRounded;
> + /*
> + * If signifRounded == 2^53, we'd need to set all of the
> significand
> + * bits to zero and add 1 to the exponent. This is exactly the
> behavior
> + * we get from just adding signifRounded to bits directly. If the
> + * exponent is Double.MAX_EXPONENT, we round up (correctly) to
> + * Double.POSITIVE_INFINITY.
> + */
> + bits |= signum & DoubleConsts.SIGN_BIT_MASK;
> + return Double.longBitsToDouble(bits);
> }
>
> /**
> diff -r 35d5a218004f
> test/java/math/BigInteger/PrimitiveConversionTests.java
> --- /dev/null Thu Jan 01 00:00:00 1970 +0000
> +++ b/test/java/math/BigInteger/PrimitiveConversionTests.java Fri Jun 14
> 14:10:43 2013 -0700
> @@ -0,0 +1,82 @@
> +import static java.math.BigInteger.ONE;
> +
> +import java.math.BigInteger;
> +import java.util.ArrayList;
> +import java.util.Arrays;
> +import java.util.Collections;
> +import java.util.List;
> +import java.util.Random;
> +
> +/**
> + * @test
> + * @bug 7131192
> + * @summary This test ensures that BigInteger.floatValue() and
> + * BigInteger.doubleValue() behave correctly.
> + * @author Louis Wasserman
> + */
> +public class PrimitiveConversionTests {
> + static final List<BigInteger> ALL_BIGINTEGER_CANDIDATES;
> +
> + static {
> + List<BigInteger> samples = new ArrayList<>();
> + // Now add values near 2^N for lots of values of N.
> + for (int exponent : Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 31, 32,
> 33,
> + 34, 62, 63, 64, 65, 71, 72, 73, 79, 80, 81, 255, 256,
> 257, 511,
> + 512, 513, Double.MAX_EXPONENT - 1, Double.MAX_EXPONENT,
> + Double.MAX_EXPONENT + 1, 2000, 2001, 2002)) {
> + BigInteger x = ONE.shiftLeft(exponent);
> + for (BigInteger y : Arrays.asList(x, x.add(ONE),
> x.subtract(ONE))) {
> + samples.add(y);
> + samples.add(y.negate());
> + }
> + }
> +
> + Random rng = new Random(1234567);
> + for (int i = 0; i < 2000; i++) {
> + samples.add(new BigInteger(rng.nextInt(2000), rng));
> + }
> +
> + ALL_BIGINTEGER_CANDIDATES = Collections.unmodifiableList(samples);
> + }
> +
> + public static int testDoubleValue() {
> + int failures = 0;
> + for (BigInteger big : ALL_BIGINTEGER_CANDIDATES) {
> + double expected = Double.parseDouble(big.toString());
> + double actual = big.doubleValue();
> +
> + // should be bitwise identical
> + if (Double.doubleToRawLongBits(expected) != Double
> + .doubleToRawLongBits(actual)) {
> + System.out.println(big);
> + failures++;
> + }
> + }
> + return failures;
> + }
> +
> + public static int testFloatValue() {
> + int failures = 0;
> + for (BigInteger big : ALL_BIGINTEGER_CANDIDATES) {
> + float expected = Float.parseFloat(big.toString());
> + float actual = big.floatValue();
> +
> + // should be bitwise identical
> + if (Float.floatToRawIntBits(expected) != Float
> + .floatToRawIntBits(actual)) {
> + System.out.println(big + " " + expected + " " + actual);
> + failures++;
> + }
> + }
> + return failures;
> + }
> +
> + public static void main(String[] args) {
> + int failures = testDoubleValue();
> + failures += testFloatValue();
> + if (failures > 0) {
> + throw new RuntimeException("Incurred " + failures
> + + " failures while testing primitive conversions.");
> + }
> + }
> +}
--
Louis Wasserman
More information about the core-libs-dev
mailing list