Faster _Smi.toString()

runtime/lib/integers.dart

Index: runtime/lib/integers.dart
diff --git a/runtime/lib/integers.dart b/runtime/lib/integers.dart
index 9c503c4b775bf56c11391182b094a4bd1c7afa9b..7139e52895b648c9dafbb7ed4ef4a301f28648ad 100644
--- a/runtime/lib/integers.dart
+++ b/runtime/lib/integers.dart
@@ -260,40 +260,149 @@ class _Smi extends _IntegerImplementation implements int {
   int _shrFromInt(int other) native "Smi_shrFromInt";
   int _shlFromInt(int other) native "Smi_shlFromInt";
 
+  static const digits = const [

[Anders Johnsen, 2014/03/05 14:41:33]

better name?

Also, all of this new stuff should be private, so I can't say 

  5.digits

[Lasse Reichstein Nielsen, 2014/03/06 12:25:37]

-> digitTable.

No *need* for private, it's all static and inside a private class.
I've made them private anyway, because it really doesn't matter.

[srdjan, 2014/03/06 17:57:14]

All public members of a private class are accessible within the same library
AFAIK. By making them public you show intent that they should be used outside
the class as well. That is not the case here. Thanks for making them private.

[Lasse Reichstein Nielsen, 2014/03/07 09:29:20]

Private members are also accessible with the same library. Making them private
really only shows intent that they shouldn't be used from outside the library,
which they already can't.
The advantage of being private is that you can see locally that they are not
visible outside the library, without having to refer to the class name. Which,
arguably, is an advantage.

+    0x30,0x30,0x30,0x31,0x30,0x32,0x30,0x33,
+    0x30,0x34,0x30,0x35,0x30,0x36,0x30,0x37,
+    0x30,0x38,0x30,0x39,0x31,0x30,0x31,0x31,
+    0x31,0x32,0x31,0x33,0x31,0x34,0x31,0x35,
+    0x31,0x36,0x31,0x37,0x31,0x38,0x31,0x39,
+    0x32,0x30,0x32,0x31,0x32,0x32,0x32,0x33,
+    0x32,0x34,0x32,0x35,0x32,0x36,0x32,0x37,
+    0x32,0x38,0x32,0x39,0x33,0x30,0x33,0x31,
+    0x33,0x32,0x33,0x33,0x33,0x34,0x33,0x35,
+    0x33,0x36,0x33,0x37,0x33,0x38,0x33,0x39,
+    0x34,0x30,0x34,0x31,0x34,0x32,0x34,0x33,
+    0x34,0x34,0x34,0x35,0x34,0x36,0x34,0x37,
+    0x34,0x38,0x34,0x39,0x35,0x30,0x35,0x31,
+    0x35,0x32,0x35,0x33,0x35,0x34,0x35,0x35,
+    0x35,0x36,0x35,0x37,0x35,0x38,0x35,0x39,
+    0x36,0x30,0x36,0x31,0x36,0x32,0x36,0x33,
+    0x36,0x34,0x36,0x35,0x36,0x36,0x36,0x37,
+    0x36,0x38,0x36,0x39,0x37,0x30,0x37,0x31,
+    0x37,0x32,0x37,0x33,0x37,0x34,0x37,0x35,
+    0x37,0x36,0x37,0x37,0x37,0x38,0x37,0x39,
+    0x38,0x30,0x38,0x31,0x38,0x32,0x38,0x33,
+    0x38,0x34,0x38,0x35,0x38,0x36,0x38,0x37,
+    0x38,0x38,0x38,0x39,0x39,0x30,0x39,0x31,
+    0x39,0x32,0x39,0x33,0x39,0x34,0x39,0x35,
+    0x39,0x36,0x39,0x37,0x39,0x38,0x39,0x39
+  ];
+
+  static const int P01 = 10;
+  static const int P02 = 100;
+  static const int P03 = 1000;
+  static const int P04 = 10000;
+  static const int P05 = 100000;
+  static const int P06 = 1000000;
+  static const int P07 = 10000000;
+  static const int P08 = 100000000;
+  static const int P09 = 1000000000;
+  static const int P10 = 10000000000;
+
+  // Find the number of decimal digits in a positive smi.
+  static int positiveBase10Length(var smi) {
+    // A positive smi has length <= 19 if 63-bit, <=10 if 31-bit.
+    // Avoid comparing a 31-bit smi to a non-smi.
+    if (smi < P03) return 3;
+    if (smi < P04) return 4;
+    if (smi < P07) {
+      if (smi < P05) return 5;
+      if (smi < P06) return 6;
+      return 7;
+    }
+    if (smi < P10) {
+      if (smi < P08) return 8;
+      if (smi < P09) return 9;
+      return 10;
+    }
+    smi = smi ~/ P10;
+    if (smi < P01) return 11;
+    if (smi < P02) return 12;
+    return 10 + positiveBase10Length(smi);
+  }
+
   String toString() {
     if (this == 0) return "0";
-    var reversed = _toStringBuffer;
-    var negative = false;
-    var val = this;
-    int index = 0;
-
-    if (this < 0) {
-      negative = true;
-      // Handle the first digit as negative to avoid negating the minimum
-      // smi, for which the negation is not a smi.
-      int digit = -(val.remainder(10));
-      reversed[index++] = digit + 0x30;
-      val = -(val ~/ 10);
+    if (this < 0) return negativeToString(this);
+    // Inspired by Andrei Alexandrescu: "Three Optimization Tips for C++"
+    // Avoid expensive remainder operation by doing it on more than
+    // one digit at a time.
+    int length = this < 10 ? 1 : this < 100 ? 2 : positiveBase10Length(this);

[srdjan, 2014/03/05 17:40:46]

Please use parentheses.

[Lasse Reichstein Nielsen, 2014/03/06 12:25:37]

Rewritten.

+    _OneByteString result = _OneByteString._allocate(length);
+    int index = length - 1;
+    var smi = this;
+    while (smi >= 100) {
+      // Two digits at a time.
+      var twoDigits = smi.remainder(100);
+      smi = smi ~/ 100;
+      int digitIndex = twoDigits * 2;
+      result._setAt(index, digits[digitIndex + 1]);
+      result._setAt(index - 1, digits[digitIndex]);
+      index -= 2;
+    }
+    if (smi >= 10) {
+      // No remainder for this case.
+      int digitIndex = smi * 2;
+      result._setAt(index, digits[digitIndex + 1]);
+      result._setAt(index - 1, digits[digitIndex]);
+    } else {
+      result._setAt(index, 0x30 + smi);
     }
+    return result;
+  }
 
-    while (val > 0) {
-      int digit = val % 10;
-      val = val ~/ 10;
-      reversed[index++] = (digit + 0x30);
+  // Find the number of decimal digits in a negative smi.
+  static int negativeBase10Length(var negSmi) {
+    // A negative smi has length <= 19 if 63-bit, <=10 if 31-bit.
+    // Avoid comparing a 31-bit smi to a non-smi.
+    if (negSmi > -P03) return 3;
+    if (negSmi > -P04) return 4;
+    if (negSmi > -P07) {
+      if (negSmi > -P05) return 5;
+      if (negSmi > -P06) return 6;
+      return 7;
     }
-    if (negative) reversed[index++] = 0x2D;  // '-'.
+    if (negSmi > -P10) {
+      if (negSmi > -P08) return 8;
+      if (negSmi > -P09) return 9;
+      return 10;
+    }
+    negSmi = negSmi ~/ P10;
+    if (negSmi > -P01) return 11;
+    if (negSmi > -P02) return 12;
+    return 10 + negativeBase10Length(negSmi);
+  }
 
-    _OneByteString string = _OneByteString._allocate(index);
-    for (int i = 0, j = index; i < index; i++) {
-      string._setAt(i, reversed[--j]);
+  // Convert a negative smi to a string.
+  // Doesn't negate the smi to avoid negating the most negative smi, which
+  // would become a non-smi.
+  static String negativeToString(int negSmi) {
+    // Number of digits, not including minus.
+    int digitCount =
+        (negSmi > -10) ? 1 : (negSmi > -100) ? 2 : negativeBase10Length(negSmi);
+    _OneByteString result = _OneByteString._allocate(digitCount + 1);
+    result._setAt(0, 0x2D);  // '-'.
+    int index = digitCount;
+    while (negSmi <= -100) {
+      var twoDigits = negSmi.remainder(100);
+      negSmi = negSmi ~/ 100;
+      int digitIndex = -twoDigits * 2;
+      result._setAt(index, digits[digitIndex + 1]);
+      result._setAt(index - 1, digits[digitIndex]);
+      index -= 2;
     }
-    return string;
+    if (negSmi <= -10) {
+      // No remainder necessary for this case.
+      int digitIndex = -negSmi * 2;
+      result._setAt(index, digits[digitIndex + 1]);
+      result._setAt(index - 1, digits[digitIndex]);
+    } else {
+      result._setAt(index, 0x30 - negSmi);
+    }
+    return result;
   }
 }
 
-// Reusable buffer used by smi.toString.
-final List _toStringBuffer = new Uint8List(20);
-
 // Represents integers that cannot be represented by Smi but fit into 64bits.
 class _Mint extends _IntegerImplementation implements int {
   factory _Mint._uninstantiable() {