RFR 7131192: BigInteger.doubleValue() is depressingly slow (original) (raw)

Brian Burkhalter brian.burkhalter at oracle.com
Mon Jun 17 18:25:33 UTC 2013

• Previous message: hg: jdk8/tl: 8016572: Pass CONCURRENCY=$(JOBS) to test/Makefile
• Next message: RFR 7131192: BigInteger.doubleValue() is depressingly slow
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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🔞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 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.");

•    }

• }

+}

• Previous message: hg: jdk8/tl: 8016572: Pass CONCURRENCY=$(JOBS) to test/Makefile
• Next message: RFR 7131192: BigInteger.doubleValue() is depressingly slow
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the core-libs-dev mailing list