RFR 4641897: Faster string conversion of large integers

[Dmitry Nadezhin]

Below are the results of performance evaluation:
1) Performance improvement of specialized method bi.toHexString() against
general bi.toString(16).
2) Code ot hypothetical BigInteger.toHexString();
3) Code of benchmark.

  -Dima

=== b.bitLength(); b.toString(16); b.toHexString();
bitLength=2047;    0.001458205 sec    3.11251E-4 sec
bitLength=4095;    0.003836644 sec    6.14027E-4 sec
bitLength=8191;    0.01112082 sec    0.001148153 sec
bitLength=16383;    0.009785916 sec    0.00256648 sec
bitLength=32767;    0.024226532 sec    0.005104734 sec
bitLength=65535;    0.040899736 sec    0.001239427 sec
bitLength=131071;    0.057398824 sec    0.002302767 sec
bitLength=262143;    0.13263946 sec    0.004272388 sec
bitLength=524287;    0.44488142 sec    8.64876E-4 sec
bitLength=1048575;    1.628629919 sec    0.001423972 sec
bitLength=2097151;    6.399754105 sec    0.002084977 sec
bitLength=4194303;    25.052650526 sec    0.004460035 sec
bitLength=8388607;    100.974373978 sec    0.009238686 sec
bitLength=16777215;    407.2107094 sec    0.018795085 sec
===

=== The code of BigInteger.toHexString()
    public String toHexString() {
        if (signum == 0) {
            return "0";
        }
        int highestLimb = mag[0];
        int digitsInHigherLimb = 8 -
Integer.numberOfLeadingZeros(highestLimb) / 4;
        int len = (mag.length - 1) * 8 + digitsInHigherLimb;
        if (signum < 0)
            len++;
        StringBuilder buf = new StringBuilder(len);
        if (signum<0)
            buf.append('-');
        for (int i = digitsInHigherLimb - 1; i >= 0; i--) {
            buf.append(Character.forDigit((highestLimb >> (i * 4)) & 0xF,
16));
        }
        for (int i = 1; i < mag.length; i++) {
            int m = mag[i];
            buf.append(Character.forDigit((m >> 28) & 0xF, 16));
            buf.append(Character.forDigit((m >> 24) & 0xF, 16));
            buf.append(Character.forDigit((m >> 20) & 0xF, 16));
            buf.append(Character.forDigit((m >> 16) & 0xF, 16));
            buf.append(Character.forDigit((m >> 12) & 0xF, 16));
            buf.append(Character.forDigit((m >> 8) & 0xF, 16));
            buf.append(Character.forDigit((m >> 4) & 0xF, 16));
            buf.append(Character.forDigit(m & 0xF, 16));
        }
        return buf.toString();
    }
===

=== The benchmark program
public class TestToString {

    public static void main(String[] args) {
        int n = 1;
        BigInteger bi = BigInteger.ONE;
        System.out.println("b.bitLength(); b.toString(16);
b.toHexString();");
        for (int i = 0; i <= 23; i++) {
            long time0 = System.nanoTime();
            String s1 = bi.toString(16);
            long time1 = System.nanoTime();
            String s2 = bi.toHexString();
            long time2 = System.nanoTime();
            assert s1.equals(s2);
            if (i >= 10) {
                System.out.println("bitLength=" + bi.bitLength() + ";\t" +
(time1 - time0) / 1e9 + " sec\t" + (time2 - time1) / 1e9 + " sec");
            }
            n *= 2;
            bi = bi.shiftLeft(n).add(bi);
        }
    }
}
====

On Sat, Jun 22, 2013 at 8:37 AM, Alan Eliasen <eliasen at mindspring.com>wrote:

> On 06/21/2013 10:23 PM, Dmitry Nadezhin wrote:
> > Brian,
> >
> > This patch significally enhances performance of string conversion  for
> > large numbers.
> >
> > I suggest to create also a fast path for power-of-two radices: 2, 4, 8,
> 16,
> > 32 .
> > It is a simple linear algorithm that is suitable both for large and small
> > numbers.
> > Can it be attached to this bug activity ?
> > Or should it be filed as another bug ?
>
>    I'd file it as another bug.
>
>    As you'll see if you run profiling tests, and the power-of-two
> radices are already *much* faster than the other powers, as would be
> expected.  It's possible to do the power-of-two conversions completely
> with bit operations in BigInteger and not relying on Long, but the
> improvement may be small as these cases are already relatively fast.
>
> --
>   Alan Eliasen
>   eliasen at mindspring.com
>   http://futureboy.us/
>