Faster _Smi.toString()

runtime/lib/integers.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.
 
 // TODO(srdjan): fix limitations.
 // - shift amount must be a Smi.
 class _IntegerImplementation {
   factory _IntegerImplementation._uninstantiable() {
     throw new UnsupportedError(
         "_IntegerImplementation can only be allocated by the VM");
@@ skipping 242 matching lines @@
   }
   int get _identityHashCode {
     return this;
   }
   int operator ~() native "Smi_bitNegate";
   int get bitLength native "Smi_bitLength";
 
   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) 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;
+  }
 
-    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);
+  // 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 (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);
+  }
 
-    while (val > 0) {
-      int digit = val % 10;
-      val = val ~/ 10;
-      reversed[index++] = (digit + 0x30);
+  // 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;
     }
-    if (negative) reversed[index++] = 0x2D;  // '-'.
-
-    _OneByteString string = _OneByteString._allocate(index);
-    for (int i = 0, j = index; i < index; i++) {
-      string._setAt(i, reversed[--j]);
+    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 string;
+    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() {
     throw new UnsupportedError(
         "_Mint can only be allocated by the VM");
   }
   int get _identityHashCode {
     return this;
   }
   int operator ~() native "Mint_bitNegate";
@@ skipping 30 matching lines @@
     } else {
       return 0;
     }
   }
   int _shlFromInt(int other) native "Bigint_shlFromInt";
 
   int pow(int exponent) {
     throw "Bigint.pow not implemented";
   }
 }