# HG changeset patch # User igerasim # Date 1566503703 25200 # Thu Aug 22 12:55:03 2019 -0700 # Node ID bb1a38448ba3abb387a5782af63c48ddf7867152 # Parent 425412369353f9fd03ff11e0619b1f50e5caca2e [mq]: 8229845-Decrease-memory-consumption-of-BigInteger-toString diff --git a/src/java.base/share/classes/java/math/BigInteger.java b/src/java.base/share/classes/java/math/BigInteger.java --- a/src/java.base/share/classes/java/math/BigInteger.java +++ b/src/java.base/share/classes/java/math/BigInteger.java @@ -1,5 +1,5 @@ /* - * Copyright (c) 1996, 2018, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1996, 2019, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -3937,35 +3937,70 @@ if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) radix = 10; - // If it's small enough, use smallToString. - if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) - return smallToString(radix); - - // Otherwise use recursive toString, which requires positive arguments. + BigInteger abs = this.abs(); + + // Ensure buffer capacity sufficient to contain string representation + // floor(bitLength*log(2)/log(radix)) + 1 + // plus an additional character for the sign if negative. + int b = abs.bitLength(); + int numChars = (int)(Math.floor(b*LOG_TWO/logCache[radix]) + 1) + + (signum < 0 ? 1 : 0); + // The results will be concatenated into this StringBuilder - StringBuilder sb = new StringBuilder(); + StringBuilder sb = new StringBuilder(numChars); + + // Put sign (if any) into result buffer if (signum < 0) { - toString(this.negate(), sb, radix, 0); - sb.insert(0, '-'); + sb.append('-'); } - else - toString(this, sb, radix, 0); - + + // Use recursive toString. + toString(abs, sb, radix, 1); return sb.toString(); } - /** This method is used to perform toString when arguments are small. */ - private String smallToString(int radix) { + /** + * If {@code numLeadingZeros > 0}, appends that many zeros to the + * specified StringBuilder. + * Otherwise, does nothing. + * + * @param sb The StringBuilder that will be appended to. + * @param numLeadingZeros The number of zeros to append. + */ + private static void padWithZeros(StringBuilder buf, int numLeadingZeros) { + while (numLeadingZeros >= NUM_ZEROS) { + buf.append(ZEROS); + numLeadingZeros -= NUM_ZEROS; + } + if (numLeadingZeros > 0) { + buf.append(ZEROS, 0, numLeadingZeros); + } + } + + /** + * This method is used to perform toString when arguments are small. + * A negative sign will be prepended if and only if {@code this < 0}. + * If {@code digits <= 0} no padding (pre-pending with zeros) will be + * effected. + * + * This method can only be called for non-negative numbers. + * + * @param radix The base to convert to. + * @param sb The StringBuilder that will be appended to in place. + * @param digits The minimum number of digits to pad to. + */ + private void smallToString(int radix, StringBuilder buf, int digits) { if (signum == 0) { - return "0"; + padWithZeros(buf, digits); + return; } // Compute upper bound on number of digit groups and allocate space int maxNumDigitGroups = (4*mag.length + 6)/7; - String digitGroup[] = new String[maxNumDigitGroups]; + long[] digitGroups = new long[maxNumDigitGroups]; // Translate number to string, a digit group at a time - BigInteger tmp = this.abs(); + BigInteger tmp = this; int numGroups = 0; while (tmp.signum != 0) { BigInteger d = longRadix[radix]; @@ -3977,33 +4012,38 @@ BigInteger q2 = q.toBigInteger(tmp.signum * d.signum); BigInteger r2 = r.toBigInteger(tmp.signum * d.signum); - digitGroup[numGroups++] = Long.toString(r2.longValue(), radix); + digitGroups[numGroups++] = r2.longValue(); tmp = q2; } - // Put sign (if any) and first digit group into result buffer - StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1); - if (signum < 0) { - buf.append('-'); - } - buf.append(digitGroup[numGroups-1]); - - // Append remaining digit groups padded with leading zeros + // Get string version of first digit group + String s = Long.toString(digitGroups[numGroups-1], radix); + + // Pad with internal zeros if necessary. + padWithZeros(buf, digits - s.length() + (numGroups - 1) * digitsPerLong[radix]); + + // Put first digit group into result buffer + buf.append(s); + + // Append remaining digit groups each padded with leading zeros for (int i=numGroups-2; i >= 0; i--) { // Prepend (any) leading zeros for this digit group - int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length(); + s = Long.toString(digitGroups[i], radix); + int numLeadingZeros = digitsPerLong[radix] - s.length(); if (numLeadingZeros != 0) { - buf.append(zeros[numLeadingZeros]); + buf.append(ZEROS, 0, numLeadingZeros); } - buf.append(digitGroup[i]); + buf.append(s); } - return buf.toString(); } /** * Converts the specified BigInteger to a string and appends to * {@code sb}. This implements the recursive Schoenhage algorithm * for base conversions. + * + * This method can only be called for non-negative numbers. + * *

* See Knuth, Donald, _The Art of Computer Programming_, Vol. 2, * Answers to Exercises (4.4) Question 14. @@ -4013,32 +4053,24 @@ * @param radix The base to convert to. * @param digits The minimum number of digits to pad to. */ - private static void toString(BigInteger u, StringBuilder sb, int radix, - int digits) { + private static void toString(BigInteger u, StringBuilder sb, + int radix, int digits) { // If we're smaller than a certain threshold, use the smallToString - // method, padding with leading zeroes when necessary. + // method, padding with leading zeroes when necessary unless we're + // at the beginning of the string or digits <= 0. As u.signum() >= 0, + // smallToString() will not prepend a negative sign. if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) { - String s = u.smallToString(radix); - - // Pad with internal zeros if necessary. - // Don't pad if we're at the beginning of the string. - if ((s.length() < digits) && (sb.length() > 0)) { - for (int i=s.length(); i < digits; i++) { - sb.append('0'); - } - } - - sb.append(s); + u.smallToString(radix, sb, digits); return; } - int b, n; - b = u.bitLength(); - // Calculate a value for n in the equation radix^(2^n) = u // and subtract 1 from that value. This is used to find the // cache index that contains the best value to divide u. - n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0); + int b = u.bitLength(); + int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / + LOG_TWO - 1.0); + BigInteger v = getRadixConversionCache(radix, n); BigInteger[] results; results = u.divideAndRemainder(v); @@ -4046,7 +4078,7 @@ int expectedDigits = 1 << n; // Now recursively build the two halves of each number. - toString(results[0], sb, radix, digits-expectedDigits); + toString(results[0], sb, radix, digits - expectedDigits); toString(results[1], sb, radix, expectedDigits); } @@ -4078,14 +4110,11 @@ return cacheLine[exponent]; } - /* zero[i] is a string of i consecutive zeros. */ - private static String zeros[] = new String[64]; - static { - zeros[63] = - "000000000000000000000000000000000000000000000000000000000000000"; - for (int i=0; i < 63; i++) - zeros[i] = zeros[63].substring(0, i); - } + /* Size of ZEROS string. */ + private static int NUM_ZEROS = 63; + + /* ZEROS is a string of NUM_ZEROS consecutive zeros. */ + private static final String ZEROS = "0".repeat(NUM_ZEROS); /** * Returns the decimal String representation of this BigInteger. diff --git a/test/jdk/java/math/BigInteger/BigIntegerTest.java b/test/jdk/java/math/BigInteger/BigIntegerTest.java --- a/test/jdk/java/math/BigInteger/BigIntegerTest.java +++ b/test/jdk/java/math/BigInteger/BigIntegerTest.java @@ -1,5 +1,5 @@ /* - * Copyright (c) 1998, 2017, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1998, 2019, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -26,7 +26,7 @@ * @library /test/lib * @build jdk.test.lib.RandomFactory * @run main BigIntegerTest - * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672 8032027 + * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672 8032027 8229845 * @summary tests methods in BigInteger (use -Dseed=X to set PRNG seed) * @run main/timeout=400 BigIntegerTest * @author madbot @@ -836,6 +836,16 @@ } } + // Check value with many trailing zeros. + String val = "123456789" + "0".repeat(200); + BigInteger b = new BigInteger(val); + String s = b.toString(); + if (!val.equals(s)) { + System.err.format("Expected length %d but got %d%n", + val.length(), s.length()); + failCount++; + } + report("String Conversion", failCount); }