Optimize number-to-string conversions.

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 extends _Num {
   factory _IntegerImplementation._uninstantiable() {
     throw new UnsupportedError(
         "_IntegerImplementation can only be allocated by the VM");
@@ skipping 275 matching lines @@
     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
   ];
 
+  /**
+   * Result of int.toString for -99, -98, ..., 98, 99.
+   */
+  static const _smallLookupTable = const [
+    "-99", "-98", "-97", "-96", "-95", "-94", "-93", "-92", "-91", "-90",
+    "-89", "-88", "-87", "-86", "-85", "-84", "-83", "-82", "-81", "-80",
+    "-79", "-78", "-77", "-76", "-75", "-74", "-73", "-72", "-71", "-70",
+    "-69", "-68", "-67", "-66", "-65", "-64", "-63", "-62", "-61", "-60",
+    "-59", "-58", "-57", "-56", "-55", "-54", "-53", "-52", "-51", "-50",
+    "-49", "-48", "-47", "-46", "-45", "-44", "-43", "-42", "-41", "-40",
+    "-39", "-38", "-37", "-36", "-35", "-34", "-33", "-32", "-31", "-30",
+    "-29", "-28", "-27", "-26", "-25", "-24", "-23", "-22", "-21", "-20",
+    "-19", "-18", "-17", "-16", "-15", "-14", "-13", "-12", "-11", "-10",
+    "-9", "-8", "-7", "-6", "-5", "-4", "-3", "-2", "-1", "0",
+    "1", "2", "3", "4", "5", "6", "7", "8", "9", "10",
+    "11", "12", "13", "14", "15", "16", "17", "18", "19", "20",
+    "21", "22", "23", "24", "25", "26", "27", "28", "29", "30",
+    "31", "32", "33", "34", "35", "36", "37", "38", "39", "40",
+    "41", "42", "43", "44", "45", "46", "47", "48", "49", "50",
+    "51", "52", "53", "54", "55", "56", "57", "58", "59", "60",
+    "61", "62", "63", "64", "65", "66", "67", "68", "69", "70",
+    "71", "72", "73", "74", "75", "76", "77", "78", "79", "80",
+    "81", "82", "83", "84", "85", "86", "87", "88", "89", "90",
+    "91", "92", "93", "94", "95", "96", "97", "98", "99",

[Ivan Posva, 2014/08/29 20:58:47]

Trailing comma.

[koda, 2014/08/29 21:02:33]

Done.

[Lasse Reichstein Nielsen, 2014/09/01 07:14:21]

There isn't anything inherently wrong with a trailing comma in Dart. I would
actually prefer it for "tables" like this one, because it makes it easier to add
more lines or rearrange lines.
(But this is VM code, so do go with the VM preferred style here).

+  ];
+
   // Powers of 10 above 1000000 are indistinguishable by eye.
   static const int _POW_10_7  = 10000000;
   static const int _POW_10_8  = 100000000;
   static const int _POW_10_9  = 1000000000;
 
   // Find the number of decimal digits in a positive smi.
   // Never called with numbers < 100. These are handled before calling.
   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 < 1000) return 3;
     if (smi < 10000) return 4;
     if (smi < _POW_10_7) {
       if (smi < 100000) return 5;
       if (smi < 1000000) return 6;
       return 7;
     }
     if (smi < _POW_10_8) return 8;
     if (smi < _POW_10_9) return 9;
     smi = smi ~/ _POW_10_9;
     // Handle numbers < 100 before calling recursively.
     if (smi < 10) return 10;
     if (smi < 100) return 11;
     return 9 + _positiveBase10Length(smi);
   }
 
   String toString() {
+    if (this < 100 && this > -100) return _smallLookupTable[this + 99];

[Lasse Reichstein Nielsen, 2014/09/01 07:14:21]

Would it make sense to put this after the sign check?
Then we would have:
  if (this < 0) return _negativeToString(this);
  if (this < 100) return _posSmallLookupTable[this];
and in _negativeToSTring
  if (this > -100) return _negSmallLookupTable[this + 99];

It seems to have one less test for the positive case (but then, -99..99 test can
be done in one compare by a good compiler).
I.e., do we have a benchmark that can see what is best?

     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.
     const int DIGIT_ZERO = 0x30;
-    if (this < 10) {
-      return _OneByteString._allocate(1).._setAt(0, DIGIT_ZERO + this);
-    }
-    if (this < 100) {
-      int digitIndex = 2 * this;
-      return _OneByteString._allocate(2)
-          .._setAt(0, _digitTable[digitIndex])
-          .._setAt(1, _digitTable[digitIndex + 1]);
-    }
     int length = _positiveBase10Length(this);
     _OneByteString result = _OneByteString._allocate(length);
     int index = length - 1;
     var smi = this;
     do {
       // Two digits at a time.
       var twoDigits = smi.remainder(100);
       smi = smi ~/ 100;
       int digitIndex = twoDigits * 2;
       result._setAt(index, _digitTable[digitIndex + 1]);
@@ skipping 120 matching lines @@
     } else {
       return 0;
     }
   }
   int _shlFromInt(int other) native "Bigint_shlFromInt";
 
   int pow(int exponent) {
     throw "Bigint.pow not implemented";
   }
 }