More efficient Int64 parsing and printing.

pkg/fixnum/lib/src/int64.dart

Index: pkg/fixnum/lib/src/int64.dart
diff --git a/pkg/fixnum/lib/src/int64.dart b/pkg/fixnum/lib/src/int64.dart
index 1a9d73a71bd0524da5fde22536144cba1c70c59c..4ef25248afa33dc99d7da91a124f70bd909d28d3 100644
--- a/pkg/fixnum/lib/src/int64.dart
+++ b/pkg/fixnum/lib/src/int64.dart
@@ -37,27 +37,6 @@ class Int64 implements IntX {
   static Int64 _ONE;
   static Int64 _TWO;
 
-  // Precompute the radix strings for MIN_VALUE to avoid the problem
-  // of overflow of -MIN_VALUE.
-  static List<String> _minValues = const <String>[
-      null, null,
-      "-1000000000000000000000000000000000000000000000000000000000000000", // 2
-      "-2021110011022210012102010021220101220222", // base 3
-      "-20000000000000000000000000000000", // base 4
-      "-1104332401304422434310311213", // base 5
-      "-1540241003031030222122212", // base 6
-      "-22341010611245052052301", // base 7
-      "-1000000000000000000000", // base 8
-      "-67404283172107811828", // base 9
-      "-9223372036854775808", // base 10
-      "-1728002635214590698", // base 11
-      "-41A792678515120368", // base 12
-      "-10B269549075433C38", // base 13
-      "-4340724C6C71DC7A8", // base 14
-      "-160E2AD3246366808", // base 15
-      "-8000000000000000" // base 16
-  ];
-
   // The remainder of the last divide operation.
   static Int64 _remainder;
 
@@ -114,41 +93,67 @@ class Int64 implements IntX {
   }
 
   /**
-   * Parses a [String] in a given [radix] between 2 and 16 and returns an
+   * Parses a [String] in a given [radix] between 2 and 36 and returns an
    * [Int64].
    */
-  // TODO(rice) - make this faster by converting several digits at once.
   static Int64 parseRadix(String s, int radix) {
-    if ((radix <= 1) || (radix > 16)) {
+    if ((radix <= 1) || (radix > 36)) {
       throw new ArgumentError("Bad radix: $radix");
     }
-    Int64 x = ZERO;
+    return _parseRadix(s, radix);
+  }
+
+  static Int64 _parseRadix(String s, int radix) {
     int i = 0;
     bool negative = false;
     if (s[0] == '-') {
       negative = true;
       i++;
     }
+    int d0 = 0, d1 = 0, d2 = 0;  //  low, middle, high components.
     for (; i < s.length; i++) {
       int c = s.codeUnitAt(i);
       int digit = Int32._decodeHex(c);

[Chris Bracken, 2013/08/27 21:36:02]

Wasn't introduced by this CL, but might be a good opportunity to rename this to
_decode(c) or something similarly non-hex-y.

[sra1, 2013/08/27 22:26:22]

Done.

       if (digit < 0 || digit >= radix) {
         throw new Exception("Non-radix char code: $c");
       }
-      x = (x * radix) + digit;
+
+      // [radix] and [digit] are at most 6 bits, component is 22, so we can
+      // multiply and add within 30 bit temporary values.
+      d0 = d0 * radix + digit;
+      int carry = d0 >> _BITS;
+      d0 &= _MASK;
+
+      d1 = d1 * radix + carry;
+      carry = d1 >> _BITS;
+      d1 &= _MASK;
+
+      d2 = d2 * radix + carry;
+      d2 &= _MASK_2;

[Chris Bracken, 2013/08/27 21:36:02]

Wasn't introduced by this CL, but might not be bad to rename this to _MASK2 to
be consistent with _BITS2.

[sra1, 2013/08/27 22:26:22]

Done.

     }
-    return negative ? -x : x;
+
+    if (negative) {
+      d0 = 0 - d0;

[Chris Bracken, 2013/08/27 21:36:02]

Is there a reason for preferring the binary - to a unary -? Perhaps
VM/dart2js/V8 optimizes this out anyway? Granted, it's negligible if anything :)

[sra1, 2013/08/27 22:26:22]

It helps type inference since the receiver is a constant.

I will be changing  d0 &= _MASK;  to  d0 = _MASK & d0;  for the same reason.

+      int borrow = (d0 >> _BITS) & 1;

[Chris Bracken, 2013/08/27 21:36:02]

Is there any case in which d0 >> _BITS would be anything other than 0 or 1?

[sra1, 2013/08/27 22:26:22]

There is a history of flip-flopping between >> returning a signed or unsigned
result.  In the unsigned world, the value is usually (1<<10)-1.
Selecting the low bit means I don't have to call the slow _shiftRight helper.

+      d0 &= _MASK;
+      d1 = 0 - d1 - borrow;
+      borrow = (d1 >> _BITS) & 1;
+      d1 &= _MASK;
+      d2 = 0 - d2 - borrow;
+      d2 &= _MASK_2;
+    }
+    return new Int64._bits(d0, d1, d2);
   }
 
   /**
    * Parses a decimal [String] and returns an [Int64].
    */
-  static Int64 parseInt(String s) => parseRadix(s, 10);
+  static Int64 parseInt(String s) => _parseRadix(s, 10);
 
   /**
    * Parses a hexadecimal [String] and returns an [Int64].
    */
-  static Int64 parseHex(String s) => parseRadix(s, 16);
+  static Int64 parseHex(String s) => _parseRadix(s, 16);
 
   //
   // Public constructors
@@ -232,12 +237,13 @@ class Int64 implements IntX {
    * Constructs an [Int64] from a pair of 32-bit integers having the value
    * [:((top & 0xffffffff) << 32) | (bottom & 0xffffffff):].
    */
-  Int64.fromInts(int top, int bottom) {
+  factory Int64.fromInts(int top, int bottom) {
     top &= 0xffffffff;
     bottom &= 0xffffffff;
-    _l = bottom & _MASK;
-    _m = ((top & 0xfff) << 10) | ((bottom >> _BITS) & 0x3ff);
-    _h = (top >> 12) & _MASK_2;
+    int d0 = bottom & _MASK;
+    int d1 = ((top & 0xfff) << 10) | ((bottom >> _BITS) & 0x3ff);
+    int d2 = (top >> 12) & _MASK_2;
+    return new Int64._bits(d0, d1, d2);
   }
 
   // Returns the [Int64] representation of the specified value. Throws
@@ -679,33 +685,7 @@ class Int64 implements IntX {
   /**
    * Returns the value of this [Int64] as a decimal [String].
    */
-  // TODO(rice) - Make this faster by converting several digits at once.
-  String toString() {
-    Int64 a = this;
-    if (a.isZero) {
-      return "0";
-    }
-    if (a.isMinValue) {
-      return "-9223372036854775808";
-    }
-
-    String result = "";
-    bool negative = false;
-    if (a.isNegative) {
-      negative = true;
-      a = -a;
-    }
-
-    Int64 ten = new Int64._bits(10, 0, 0);
-    while (!a.isZero) {
-      a = _divMod(a, ten, true);
-      result = "${_remainder._l}$result";
-    }
-    if (negative) {
-      result = "-$result";
-    }
-    return result;
-  }
+  String toString() => _toRadixString(10);
 
   // TODO(rice) - Make this faster by avoiding arithmetic.
   String toHexString() {
@@ -724,32 +704,176 @@ class Int64 implements IntX {
   }
 
   String toRadixString(int radix) {
-    if ((radix <= 1) || (radix > 16)) {
+    if ((radix <= 1) || (radix > 36)) {
       throw new ArgumentError("Bad radix: $radix");
     }
-    Int64 a = this;
-    if (a.isZero) {
-      return "0";
-    }
-    if (a.isMinValue) {
-      return _minValues[radix];
-    }
-
-    String result = "";
-    bool negative = false;
-    if (a.isNegative) {
-      negative = true;
-      a = -a;
-    }
+    return _toRadixString(radix);
+  }
 
-    Int64 r = new Int64._bits(radix, 0, 0);
-    while (!a.isZero) {
-      a = _divMod(a, r, true);
-      result = "${_hexDigit(_remainder._l)}$result";
-    }
-    return negative ? "-$result" : result;
+  String _toRadixString(int radix) {
+    int d0 = _l;
+    int d1 = _m;
+    int d2 = _h;
+
+    if (d0 == 0 && d1 == 0 && d2 == 0) return '0';
+
+    String sign = '';
+    if ((d2 & _SIGN_BIT_VALUE) != 0) {
+      sign = '-';
+
+      // Negate in-place.
+      d0 = 0 - d0;
+      int borrow = (d0 >> _BITS) & 1;
+      d0 &= _MASK;
+      d1 = 0 - d1 - borrow;
+      borrow = (d1 >> _BITS) & 1;
+      d1 &= _MASK;
+      d2 = 0 - d2 - borrow;
+      d2 &= _MASK_2;
+      // d2, d1, d0 now are an unsigned 64 bit integer for MIN_VALUE and an
+      // unsigned 63 bit integer for other values.
+    }
+
+    // Rearrange components into five components where all but the most
+    // significant are 10 bits wide.
+    //
+    //     d4, d3, d4, d1, d0:  24 + 10 + 10 + 10 + 10 bits
+    //
+    // The choice of 10 bits allows a remainder of 20 bits to be scaled by 10
+    // bits and added during division while keeping all intermediate values
+    // within 30 bits (unsigned small integer range for 32 bit implementations
+    // of Dart VM and V8).
+
+    // Which of these diagrams works best?
+
+
+    //     2222222222222222222211111111111111111111110000000000000000000000
+    //  -->
+    //     4444444444444444444444443333333333222222222211111111110000000000
+
+
+    //     22222222222222222222
+    //                         1111111111111111111111
+    //                                               0000000000000000000000
+    //  -->
+    //     444444444444444444444444
+    //                             3333333333
+    //                                       2222222222
+    //                                                 1111111111
+    //                                                           0000000000
+
+    //     22222222222222222222                      0000000000000000000000
+    //                         1111111111111111111111
+    //  -->
+    //     444444444444444444444444          2222222222          0000000000
+    //                             3333333333          1111111111
+
+    //     6  6         5         4         3         2         1
+    //     3210987654321098765432109876543210987654321098765432109876543210
+    //     [--------d2--------][---------d1---------][---------d0---------]
+    //  -->
+    //     [----------d4----------][---d3---][---d2---][---d1---][---d0---]

[Chris Bracken, 2013/08/27 21:36:02]

Personal favourite. Second place goes to the one at the top.

+
+
+    int d4 = (d2 << 4) | (d1 >> 18);
+    int d3 = (d1 >> 8) & 0x3ff;
+    d2 = ((d1 << 2) | (d0 >> 20)) & 0x3ff;
+    d1 = (d0 >> 10) & 0x3ff;
+    d0 = d0 & 0x3ff;

[Chris Bracken, 2013/08/27 21:36:02]

It's pretty clear to from the comment above that 0x3ff is a 10-bit mask, though
it might make it a tiny bit more readable to create a constant (maybe _MASK10?).
That said, I'm not entirely convinced it'd really be any better than 0x3ff.

[sra1, 2013/08/27 22:26:22]

I'm find the value of named constants dubious when the constant can't be
changed.  A name like _MASK10 might be confused with _BITS01.

+
+    int fatRadix = _fatRadixTable[radix];
+
+    // Generate chunks of digits.  In radix 10, generate 6 digits per chunk.
+    //
+    // This loop generates at most 3 chunks, so we store the chunks in locals
+    // rather than a list.  We are trying to generate digits 20 bits at a time
+    // until we have only 30 bits left.  20 + 20 + 30 > 64 would imply that we
+    // need only two chunks, but radix values 17-19 and 33-36 generate only 15
+    // or 16 bits per iteration, so sometime the third chunk is needed.
+
+    String chunk1 = "", chunk2 = "", chunk3 = "";
+
+    while (!(d4 == 0 && d3 == 0)) {

[Chris Bracken, 2013/08/27 21:36:02]

(d4 != 0 || d3 != 0) saves an operation, though the VM/dart2js might optimize
this away anyway. Depending on mindset it might be more readable.

+      int q = d4 ~/ fatRadix;
+      int r = d4 - q * fatRadix;

[Chris Bracken, 2013/08/27 21:36:02]

Is this more efficient than that modulo operator?

[sra1, 2013/08/27 22:26:22]

I don't know.  It really depends if the JS or VM jit can generate a fused
divmod.  If it can't, this is faster since the repeated hardware DIV instruction
is usually slower than MUL and if the jit can't tell everything is a SMI and
non-negative, % often needs a bunch sign checks.

+      d4 = q;
+      d3 += r * 1024;

[Chris Bracken, 2013/08/27 21:36:02]

d3 += r << 10 might be more indicative of the general tactic here. Not sure if
it's any more efficient; ideally the VM should be smart enough to make the
switch if so.

[sra1, 2013/08/27 22:26:22]

Done.

+
+      q = d3 ~/ fatRadix;
+      r = d3 - q * fatRadix;
+      d3 = q;
+      d2 += r * 1024;
+
+      q = d2 ~/ fatRadix;
+      r = d2 - q * fatRadix;
+      d2 = q;
+      d1 += r * 1024;
+
+      q = d1 ~/ fatRadix;
+      r = d1 - q * fatRadix;
+      d1 = q;
+      d0 += r * 1024;
+
+      q = d0 ~/ fatRadix;
+      r = d0 - q * fatRadix;
+      d0 = q;
+
+      assert(chunk2 == "");
+      chunk3 = chunk2;
+      chunk2 = chunk1;
+      // Adding [fatRadix] Forces an extra digit which we discard to get a fixed
+      // width.  E.g.  (1000000 + 123) -> "1000123" -> "000123".  An alternative
+      // would be to pad to the left with zeroes.
+      chunk1 = (fatRadix + r).toRadixString(radix).substring(1);
+    }
+    int residue = 1024 * 1024 * d2 + 1024 * d1 + d0;
+    String leadingDigits = residue == 0 ? '' : residue.toRadixString(radix);
+    return '$sign$leadingDigits$chunk1$chunk2$chunk3';
   }
 
+  // Table of 'fat' radix values.  Each entry for index `i` is the largest power
+  // of `i` whose remainder fits in 20 bits.
+  static final _fatRadixTable = const <int>[
+      0,
+      0,
+      2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
+        * 2,
+      3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3,
+      4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4,
+      5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+      6 * 6 * 6 * 6 * 6 * 6 * 6,
+      7 * 7 * 7 * 7 * 7 * 7 * 7,
+      8 * 8 * 8 * 8 * 8 * 8,
+      9 * 9 * 9 * 9 * 9 * 9,
+      10 * 10 * 10 * 10 * 10 * 10,
+      11 * 11 * 11 * 11 * 11,
+      12 * 12 * 12 * 12 * 12,
+      13 * 13 * 13 * 13 * 13,
+      14 * 14 * 14 * 14 * 14,
+      15 * 15 * 15 * 15 * 15,
+      16 * 16 * 16 * 16 * 16,
+      17 * 17 * 17 * 17,
+      18 * 18 * 18 * 18,
+      19 * 19 * 19 * 19,
+      20 * 20 * 20 * 20,
+      21 * 21 * 21 * 21,
+      22 * 22 * 22 * 22,
+      23 * 23 * 23 * 23,
+      24 * 24 * 24 * 24,
+      25 * 25 * 25 * 25,
+      26 * 26 * 26 * 26,
+      27 * 27 * 27 * 27,
+      28 * 28 * 28 * 28,
+      29 * 29 * 29 * 29,
+      30 * 30 * 30 * 30,
+      31 * 31 * 31 * 31,
+      32 * 32 * 32 * 32,
+      33 * 33 * 33,
+      34 * 34 * 34,
+      35 * 35 * 35,
+      36 * 36 * 36
+  ];
+
   String toDebugString() {
     return "Int64[_l=$_l, _m=$_m, _h=$_h]";
   }
@@ -763,11 +887,10 @@ class Int64 implements IntX {
   /**
    * Constructs an [Int64] with the same value as an existing [Int64].
    */
-  Int64._copy(Int64 other) {
-    _l = other._l;
-    _m = other._m;
-    _h = other._h;
-  }
+  Int64._copy(Int64 other)
+      : _l = other._l,
+        _m = other._m,
+        _h = other._h;
 
   // Determine whether the platform supports ints greater than 2^53
   // without loss of precision.