Improve speed of toRadixString, and extra much for powers of two.

runtime/lib/integers.dart

Index: runtime/lib/integers.dart
diff --git a/runtime/lib/integers.dart b/runtime/lib/integers.dart
index 7c242ef95659a9872e9810492060f0d695f8dc13..8f28051dfb1ab8b9b98630352feb15e4bc5624f7 100644
--- a/runtime/lib/integers.dart
+++ b/runtime/lib/integers.dart
@@ -187,31 +187,52 @@ class _IntegerImplementation {
     return this.toDouble().toStringAsPrecision(precision);
   }
 
+  static const _digits = "0123456789abcdefghijklmnopqrstuvwxyz";
+
   String toRadixString(int radix) {
-    final table = const ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
-                         "a", "b", "c", "d", "e", "f", "g", "h", "i", "j",
-                         "k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
-                         "u", "v", "w", "x", "y", "z"];
     if (radix is! int || radix < 2 || radix > 36) {
       throw new ArgumentError(radix);
     }
+    if (radix & (radix - 1) == 0) {
+      return _toPow2String(this, radix);
+    }
     final bool isNegative = this < 0;
     int value = isNegative ? -this : this;
     List temp = new List();

[sra1, 2013/09/25 18:03:44]

You could estimate the length and allocate a one byte string.
Fill in the digits from the end to avoid reversing.
If the estimate is wrong, use substring (or a manually coded equivalent) to get
the tail.

Even if the estimate is always wrong, the temporary string is smaller than the
temporary growable array.

[Lasse Reichstein Nielsen, 2013/09/26 09:24:49]

There are two possible optimizations here.

One is to keep a static array around, the other is to allocate a smaller buffer
than a growable list.

For the smaller buffer, I'd use an Uint8List. I don't believe I will be able to
guess the number of digits in general. The simplest estimate is to pick the
number of digits for the next lower power of 2, which is always at least as
great.

This can also use an existing buffer that we have around, like the 20-character
buffer already used by Smi.toString, and replace it with a larger buffer only
when needed.

I'll leave this optimization for a later CL :)

[sra1, 2013/09/27 01:12:42]

No problem leaving it for later.

The estimate is:

(negative?1:0) + ceil(bitlength(abs(value)) / log2(radix))

This will give the right length much of the time, e.g. for radix = 10.

32-63     gives 2, correct 100%
64-127    gives 3, correct 27/64 = 42%
128-255   gives 3, correct 100%
256-511   gives 3, correct 100%
512-1023  gives 4, correct 23/512 = 4.4%
1024-2047 gives 4, correct 100%

Since log2(radix) is inexact with an error of a few ulp, bias it low by a very
small proportion.

-    while (value > 0) {
+    do {
       int digit = value % radix;
       value ~/= radix;
-      temp.add(digit);
-    }
-    if (temp.isEmpty) {
-      return "0";
+      temp.add(_digits.codeUnitAt(digit));
+    } while (value > 0);
+    if (isNegative) temp.add(0x2d);  // '-'.
+
+    _OneByteString string = _OneByteString._allocate(temp.length);
+    for (int i = 0, j = temp.length; j > 0; i++) {
+      string._setAt(i, temp[--j]);
     }
-    StringBuffer buffer = new StringBuffer();
-    if (isNegative) buffer.write("-");
-    for (int i = temp.length - 1; i >= 0; i--) {
-      buffer.write(table[temp[i]]);
+    return string;
+  }
+
+  static String _toPow2String(value, radix) {
+    if (value == 0) return "0";
+    assert(radix & (radix - 1) == 0);
+    var negative = value < 0;
+    var bitsPerDigit = radix.bitLength - 1;
+    var length = 0;
+    if (negative) {
+      value = -value;
+      length = 1;
     }
-    return buffer.toString();
+    // Integer division, rounding up, to find number of _digits.
+    length += (value.bitLength + bitsPerDigit - 1) ~/ bitsPerDigit;
+    _OneByteString string = _OneByteString._allocate(length);
+    string._setAt(0, 0x2d);  // '-'. Is overwritten if not negative.
+    var mask = radix - 1;
+    do {
+      string._setAt(--length, _digits.codeUnitAt(value & mask));
+      value >>= bitsPerDigit;
+    } while (value > 0);
+    return string;
   }
 
   _leftShiftWithMask32(count, mask)  native "Integer_leftShiftWithMask32";