Optimize int.parse with a radix.

runtime/lib/integers_patch.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 // Dart core library.
 
 // VM implementation of int.
 
 patch class int {
 
+  /* patch */ const factory int.fromEnvironment(String name,
+                                                {int defaultValue})
+      native "Integer_fromEnvironment";
+
   static bool is64Bit() => 1 << 32 is _Smi;
 
   static int _tryParseSmi(String str, int first, int last) {
     assert(first <= last);
     var ix = first;
     var sign = 1;
     var c = str.codeUnitAt(ix);
     // Check for leading '+' or '-'.
     if ((c == 0x2b) || (c == 0x2d)) {
       ix++;
@@ skipping 10 matching lines @@
     for (int i = ix; i <= last; i++) {
       var c = 0x30 ^ str.codeUnitAt(i);
       if (9 < c) {
         return null;
       }
       result = 10 * result + c;
     }
     return sign * result;
   }
 
-  static int _tryParseSmiWhitespace(String str) {
-    int first = str._firstNonWhitespace();
-    if (first < str.length) {
-      int last = str._lastNonWhitespace();
-      int res = _tryParseSmi(str, first, last);
-      if (res != null) return res;
-    }
-    return _native_parse(str);
-  }
-
-  static int _parse(String str) {
-    int res = _tryParseSmi(str, 0, str.length - 1);
-    if (res != null) return res;
-    return _tryParseSmiWhitespace(str);
-  }
-
-  static int _native_parse(String str) native "Integer_parse";
-
-  static int _throwFormatException(String source, int position) {
-    throw new FormatException("", source, position);
-  }
-
   /* patch */ static int parse(String source,
                                { int radix,
                                  int onError(String str) }) {
-    if (source == null) throw new ArgumentError(source);
-    if (radix == null) {
-      int result;
-      if (source.isNotEmpty) result = _parse(source);
-      if (result == null) {
-        if (onError == null) {
-          throw new FormatException("", source);
-        }
-        return onError(source);
-      }
-      return result;
+    if (source == null) throw new ArgumentError("The source must not be null");
+    if (source.isEmpty) return _throwFormatException(onError, source, 0, radix);
+    if (radix == null || radix == 10) {
+      // Try parsing immediately, without trimming whitespace.
+      int result = _tryParseSmi(source, 0, source.length - 1);
+      if (result != null) return result;
+    } else if (radix < 2 || radix > 36) {
+      throw new RangeError("Radix $radix not in range 2..36");
     }
-    return _slowParse(source, radix, onError);
+    // Split here so improve odds of parse being inlined and the checks omitted.
+    return _parse(source, radix, onError);
   }
 
-  /* patch */ const factory int.fromEnvironment(String name,
-                                                {int defaultValue})
-      native "Integer_fromEnvironment";
+  static int _parse(String source, int radix, onError) {
+    int end = source._lastNonWhitespace() + 1;
+    if (end == 0) {
+      return _throwFormatException(onError, source, source.length, radix);
+    }
+    int start = source._firstNonWhitespace();
 
-  static int _slowParse(String source, int radix, int onError(String str)) {
-    if (source is! String) throw new ArgumentError(source);
-    if (radix is! int) throw new ArgumentError("Radix is not an integer");
-    if (radix < 2 || radix > 36) {
-      throw new RangeError("Radix $radix not in range 2..36");
+    int first = source.codeUnitAt(start);
+    int sign = 1;
+    if (first == 0x2b /* + */ || first == 0x2d /* - */) {
+      sign = 0x2c - first;  // -1 if '-', +1 if '+'.
+      start++;
+      if (start == end) {
+        return _throwFormatException(onError, source, end, radix);
+      }
     }
-    // Remove leading and trailing white space.
-    int start = source._firstNonWhitespace();
-    int i = start;
-    if (onError == null) onError = (source) {
-      throw new FormatException("Invalid radix-$radix number", source, i);
-    };
-    if (start == source.length) return onError(source);
-    int end = source._lastNonWhitespace() + 1;
+    if (radix == null) {
+      // check for 0x prefix.
+      int index = start;
+      first = source.codeUnitAt(index);
+      if (first == 0x30 /* 0 */) {
+        index++;
+        if (index == end) return 0;
+        first = source.codeUnitAt(index);
+        if ((first | 0x20) == 0x78 /* x */) {
+          index++;
+          if (index == end) {
+            return _throwFormatException(onError, source, index, null);
+          }
+          int result = _parseRadix(source, 16, index, end, sign);
+          if (result == null) {
+            return _throwFormatException(onError, source, null, null);
+          }
+          return result;
+        }
+      }
+      radix = 10;
+    }
+    int result = _parseRadix(source, radix, start, end, sign);
+    if (result == null) {
+      return _throwFormatException(onError, source, null, radix);
+    }
+    return result;
+  }
 
-    bool negative = false;
+  static int _throwFormatException(onError, source, index, radix) {
+    if (onError != null) return onError(source);
+    if (radix == null) {
+      throw new FormatException("Invalid number", source, index);
+    }
+    throw new FormatException("Invalid radix-$radix number", source, index);
+  }
+
+  static int _parseRadix(String source, int radix,
+                         int start, int end, int sign) {
+    int tableIndex = (radix - 2) * 4 + (int.is64Bit() ? 2 : 0);
+    int blockSize = _PARSE_LIMITS[tableIndex];
+    int length = end - start;
+    if (length <= blockSize) {
+      _Smi smi = _parseBlock(source, radix, start, end);
+      if (smi != null) return sign * smi;
+      return null;
+    }
+    int smallBlockSize = length % blockSize;
     int result = 0;
+    if (smallBlockSize > 0) {
+      int blockEnd = start + smallBlockSize;
+      _Smi smi = _parseBlock(source, radix, start, blockEnd);
+      if (smi == null) return null;
+      result = sign * smi;
+      start = blockEnd;
+    }
+    _Smi multiplier = _PARSE_LIMITS[tableIndex + 1];
+    int blockEnd = start + blockSize;
+    do {
+      _Smi smi = _parseBlock(source, radix, start, blockEnd);
+      if (smi == null) return null;
+      result = (result * multiplier) + (sign * smi);

[Florian Schneider, 2014/09/25 11:38:39]

Maybe factor out the multiplication with sign out of the loop?

[Lasse Reichstein Nielsen, 2014/09/25 14:37:16]

This makes all the multiplications Smi operations, instead of having a bignum
multiplication at the end - potentially copying a large result.

[Florian Schneider, 2014/09/26 11:57:05]

I see - that makes sense.

+      start = blockEnd;
+      blockEnd = start + blockSize;
+    } while (blockEnd <= end);
+    return result;
+  }
 
-    // The value 99 is used to represent a non-digit. It is too large to be
-    // a digit value in any of the used bases.
-    const NA = 99;
-    const List<int> digits = const <int>[
-      00, 01, 02, 03, 04, 05, 06, 07, 08, 09, NA, NA, NA, NA, NA, NA,  // 0x30
-      NA, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,  // 0x40
-      25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, NA, NA, NA, NA, NA,  // 0x50
-      NA, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,  // 0x60
-      25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, NA, NA, NA, NA, NA,  // 0x70
-    ];
+  // Parse block of digits with radix > 10.
+  static _Smi _parseBlock(String source, int radix, int start, int end) {
+    _Smi result = 0;
+    if (radix <= 10) {
+      for (int i = start; i < end; i++) {
+        int digit = source.codeUnitAt(i) ^ 0x30;
+        if (digit >= radix) return null;
+        result = radix * result + digit;
+      }
+    } else {
+      for (int i = start; i < end; i++) {
+        int char = source.codeUnitAt(i);
+        int digit = char ^ 0x30;

[Florian Schneider, 2014/09/25 11:38:39]

Is this computation of the digit actually faster than the old way? e.g. for
radix 16 which is common.

[Lasse Reichstein Nielsen, 2014/09/25 14:37:16]

Testing just for hex, it seems to be pretty much the same. I'd say marginally
faster than table lookup (even if I cut the table range check down to only one
comparison), but by a marginal so small it could easily be noise.

[Florian Schneider, 2014/09/26 11:57:05]

Acknowledged.

+        if (digit > 9) {
+          digit = (char | 0x20) - (0x61 - 10);
+          if (digit < 10 || digit >= radix) return null;
+        }
+        result = radix * result + digit;
+      }
+    }
+    return result;
+  }
 
-    int code = source.codeUnitAt(i);
-    if (code == 0x2d || code == 0x2b) { // Starts with a plus or minus-sign.
-      negative = (code == 0x2d);
-      i++;
-      if (i == end) return onError(source);
-      code = source.codeUnitAt(i);
-    }
-    do {
-      if (code < 0x30 || code > 0x7f) return onError(source);
-      int digit = digits[code - 0x30];
-      if (digit >= radix) return onError(source);
-      result = result * radix + digit;
-      i++;
-      if (i == end) break;
-      code = source.codeUnitAt(i);
-    } while (true);
-    return negative ? -result : result;
-  }
+  // For each radix, 2-36, how many digits are guaranteed to fit in a smi,
+  // and magnitude of such a block (radix ** digit-count).
+  // 32-bit limit/multiplier at (radix - 2)*4, 64-bit limit at (radix-2)*4+1
+  static const _PARSE_LIMITS = const [
+    30, 1073741824,  62, 4611686018427387904,  /* radix: 2 */
+    18,  387420489,  39, 4052555153018976267,
+    15, 1073741824,  30, 1152921504606846976,
+    12,  244140625,  26, 1490116119384765625,  /* radix: 5 */
+    11,  362797056,  23,  789730223053602816,
+    10,  282475249,  22, 3909821048582988049,
+    10, 1073741824,  20, 1152921504606846976,
+     9,  387420489,  19, 1350851717672992089,
+     9, 1000000000,  18, 1000000000000000000,  /* radix: 10 */
+     8,  214358881,  17,  505447028499293771,
+     8,  429981696,  17, 2218611106740436992,
+     8,  815730721,  16,  665416609183179841,
+     7,  105413504,  16, 2177953337809371136,
+     7,  170859375,  15,  437893890380859375,   /* radix: 15 */
+     7,  268435456,  15, 1152921504606846976,
+     7,  410338673,  15, 2862423051509815793,
+     7,  612220032,  14,  374813367582081024,
+     7,  893871739,  14,  799006685782884121,
+     6,   64000000,  14, 1638400000000000000,  /* radix: 20 */
+     6,   85766121,  14, 3243919932521508681,
+     6,  113379904,  13,  282810057883082752,
+     6,  148035889,  13,  504036361936467383,
+     6,  191102976,  13,  876488338465357824,
+     6,  244140625,  13, 1490116119384765625,  /* radix: 25 */
+     6,  308915776,  13, 2481152873203736576,
+     6,  387420489,  13, 4052555153018976267,
+     6,  481890304,  12,  232218265089212416,
+     6,  594823321,  12,  353814783205469041,
+     6,  729000000,  12,  531441000000000000,  /* radix: 30 */
+     6,  887503681,  12,  787662783788549761,
+     6, 1073741824,  12, 1152921504606846976,
+     5,   39135393,  12, 1667889514952984961,
+     5,   45435424,  12, 2386420683693101056,
+     5,   52521875,  12, 3379220508056640625,  /* radix: 35 */
+     5,   60466176,  11,  131621703842267136,
+  ];
 }