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

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/viewbug.do?bugid=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.MAXEXPONENT) { + return signum > 0 ? Float.POSITIVEINFINITY : Float.NEGATIVEINFINITY; + } + + /* + * We need the top SIGNIFICANDBITS + 1 bits, including the "implicit" + * one bit. To make rounding easier, we pick out the top + * SIGNIFICANDBITS + 2 bits, so we have one to help us round up or + * down. twiceSignifFloor will contain the top SIGNIFICANDBITS + 2 + * bits, and signifFloor the top SIGNIFICANDBITS + 1. + * + * It helps to consider the real number signif = abs(this) * + * 2^(SIGNIFICANDBITS - exponent). + */ + int shift = exponent - FloatConsts.SIGNIFICANDWIDTH; + + 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.SIGNIFBITMASK; // 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 HALFEVEN rounding. + */ + boolean increment = (twiceSignifFloor & 1) != 0 + && ((signifFloor & 1) != 0 || abs().getLowestSetBit() <_ _shift);_ _+ int signifRounded = increment ? signifFloor + 1 : signifFloor;_ _+ int bits = ((exponent + FloatConsts.EXPBIAS))_ _+ << (FloatConsts.SIGNIFICANDWIDTH - 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.MAXEXPONENT, we round up (correctly) to_ _+ * Float.POSITIVEINFINITY._ _+ */_ _+ bits |= signum & FloatConsts.SIGNBITMASK;_ _+ 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.MAXEXPONENT) { + return signum > 0 ? Double.POSITIVEINFINITY : Double.NEGATIVEINFINITY; + } + + /* + * We need the top SIGNIFICANDBITS + 1 bits, including the "implicit" + * one bit. To make rounding easier, we pick out the top + * SIGNIFICANDBITS + 2 bits, so we have one to help us round up or + * down. twiceSignifFloor will contain the top SIGNIFICANDBITS + 2 + * bits, and signifFloor the top SIGNIFICANDBITS + 1. + * + * It helps to consider the real number signif = abs(this) * + * 2^(SIGNIFICANDBITS - exponent). + */ + int shift = exponent - DoubleConsts.SIGNIFICANDWIDTH; + + 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 & LONGMASK) << 32)_ _+ | (lowBits & LONGMASK);_ _+_ _+ long signifFloor = twiceSignifFloor >> 1; + signifFloor &= DoubleConsts.SIGNIFBITMASK; // 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 HALFEVEN rounding. + */ + boolean increment = (twiceSignifFloor & 1) != 0 + && ((signifFloor & 1) != 0 || abs().getLowestSetBit() <_ _shift);_ _+ long signifRounded = increment ? signifFloor + 1 : signifFloor;_ _+ long bits = (long) ((exponent + DoubleConsts.EXPBIAS))_ _+ << (DoubleConsts.SIGNIFICANDWIDTH - 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.MAXEXPONENT, we round up (correctly) to_ _+ * Double.POSITIVEINFINITY._ _+ */_ _+ bits |= signum & DoubleConsts.SIGNBITMASK;_ _+ 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 ALLBIGINTEGERCANDIDATES; + + static { + List 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.MAXEXPONENT - 1, Double.MAXEXPONENT, + Double.MAXEXPONENT + 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));_ _+ }_ _+_ _+ ALLBIGINTEGERCANDIDATES = Collections.unmodifiableList(samples);_ _+ }_ _+_ _+ public static int testDoubleValue() {_ _+ int failures = 0;_ _+ for (BigInteger big : ALLBIGINTEGERCANDIDATES) {_ _+ 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 : ALLBIGINTEGERCANDIDATES) {_ _+ 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