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

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 169 matching lines @@
   String toStringAsFixed(int fractionDigits) {
     return this.toDouble().toStringAsFixed(fractionDigits);
   }
   String toStringAsExponential([int fractionDigits]) {
     return this.toDouble().toStringAsExponential(fractionDigits);
   }
   String toStringAsPrecision(int precision) {
     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);
+      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]);
     }
-    if (temp.isEmpty) {
-      return "0";
+    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;
     }
-    StringBuffer buffer = new StringBuffer();
-    if (isNegative) buffer.write("-");
-    for (int i = temp.length - 1; i >= 0; i--) {
-      buffer.write(table[temp[i]]);
-    }
-    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";
 }
 
 class _Smi extends _IntegerImplementation implements int {
   factory _Smi._uninstantiable() {
     throw new UnsupportedError(
         "_Smi can only be allocated by the VM");
   }
@@ skipping 76 matching lines @@
     } else {
       return 0;
     }
   }
   int _shlFromInt(int other) native "Bigint_shlFromInt";
 
   int pow(int exponent) {
     throw "Bigint.pow not implemented";
   }
 }