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

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

Approx x2 speedup in general, x6 for powers of two (with 16 being probably
the most common radix).

R=srdjan@google.com

Committed: https://code.google.com/p/dart/source/detail?r=27988

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

https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart
File runtime/lib/integers.dart (right):

https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart#new...
runtime/lib/integers.dart:201: List temp = new List();
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:48]

https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart
File runtime/lib/integers.dart (right):

https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart#new...
runtime/lib/integers.dart:201: List temp = new List();
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 :)

[Lasse Reichstein Nielsen, 2013-09-26 09:45:11]

PTAL

[srdjan, 2013-09-26 22:29:51]

lgtm

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

https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart
File runtime/lib/integers.dart (right):

https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart#new...
runtime/lib/integers.dart:201: List temp = new List();
On 2013/09/26 09:24:49, Lasse Reichstein Nielsen wrote:
> 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 :)

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.

[Lasse Reichstein Nielsen, 2013-09-27 06:19:55]

On 2013/09/27 01:12:42, sra1 wrote:
> https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart
> File runtime/lib/integers.dart (right):
> 
>
https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart#new...
> runtime/lib/integers.dart:201: List temp = new List();
> On 2013/09/26 09:24:49, Lasse Reichstein Nielsen wrote:
> > 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 :)
> 
> 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.

It's clever.
However, I expect log2 to be more expensive that copying a few bytes. It may pay
off for very large numbers (bigint range, maybe mint), but let's try it and see
how expensive it really is.

[kasperl, 2013-09-27 06:22:50]

On 2013/09/27 06:19:55, Lasse Reichstein Nielsen wrote:
> On 2013/09/27 01:12:42, sra1 wrote:
> > https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart
> > File runtime/lib/integers.dart (right):
> > 
> >
>
https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart#new...
> > runtime/lib/integers.dart:201: List temp = new List();
> > On 2013/09/26 09:24:49, Lasse Reichstein Nielsen wrote:
> > > 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 :)
> > 
> > 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.
> 
> It's clever.
> However, I expect log2 to be more expensive that copying a few bytes. It may
pay
> off for very large numbers (bigint range, maybe mint), but let's try it and
see
> how expensive it really is.

You could argue that you're not going to need to cache that many values of
log2(radix)...

[Lasse Reichstein Nielsen, 2013-09-27 07:03:04]

Committed patchset #2 manually as r27988 (presubmit successful).

[Lasse Reichstein Nielsen, 2013-09-27 07:04:49]

On 2013/09/27 06:22:50, kasperl wrote:
> On 2013/09/27 06:19:55, Lasse Reichstein Nielsen wrote:
> > On 2013/09/27 01:12:42, sra1 wrote:
> > > https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart
> > > File runtime/lib/integers.dart (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/24497004/diff/1/runtime/lib/integers.dart#new...
> > > runtime/lib/integers.dart:201: List temp = new List();
> > > On 2013/09/26 09:24:49, Lasse Reichstein Nielsen wrote:
> > > > 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 :)
> > > 
> > > 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.
> > 
> > It's clever.
> > However, I expect log2 to be more expensive that copying a few bytes. It may
> pay
> > off for very large numbers (bigint range, maybe mint), but let's try it and
> see
> > how expensive it really is.
> 
> You could argue that you're not going to need to cache that many values of
> log2(radix)...

That's a good point!