RFR 7131192: BigInteger.doubleValue() is depressingly slow
Brian Burkhalter
brian.burkhalter at oracle.com
Mon Jun 17 18:25:33 UTC 2013
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.");
+ }
+ }
+}
More information about the core-libs-dev
mailing list