More efficient Int64 parsing and printing.

More efficient Int64 parsing and printing.

This replaces code that generates lots of temporary Int64 objects with
code that works almost entirely usings SMI values in local variables.
Printing generates numbers several digits at a time.

Speedup is 10x for parsing and 100x for printing on dart2js and a little over 5x each on the VM.

Printing produces hex digits in the same case as int.toString.

R=cbracken@google.com

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

[Chris Bracken, 2013-08-27 21:36:02]

Publishing what I have so far. Haven't got all the way through _toRadixString
yet.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.dart
File pkg/fixnum/lib/src/int64.dart (left):

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:134: int digit = Int32._decodeHex(c);
Wasn't introduced by this CL, but might be a good opportunity to rename this to
_decode(c) or something similarly non-hex-y.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.dart
File pkg/fixnum/lib/src/int64.dart (right):

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:132: d2 &= _MASK_2;
Wasn't introduced by this CL, but might not be bad to rename this to _MASK2 to
be consistent with _BITS2.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:136: d0 = 0 - d0;
Is there a reason for preferring the binary - to a unary -? Perhaps
VM/dart2js/V8 optimizes this out anyway? Granted, it's negligible if anything :)

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:137: int borrow = (d0 >> _BITS) & 1;
Is there any case in which d0 >> _BITS would be anything other than 0 or 1?

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:775: //    
[----------d4----------][---d3---][---d2---][---d1---][---d0---]
Personal favourite. Second place goes to the one at the top.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:782: d0 = d0 & 0x3ff;
It's pretty clear to from the comment above that 0x3ff is a 10-bit mask, though
it might make it a tiny bit more readable to create a constant (maybe _MASK10?).
That said, I'm not entirely convinced it'd really be any better than 0x3ff.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:796: while (!(d4 == 0 && d3 == 0)) {
(d4 != 0 || d3 != 0) saves an operation, though the VM/dart2js might optimize
this away anyway. Depending on mindset it might be more readable.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:798: int r = d4 - q * fatRadix;
Is this more efficient than that modulo operator?

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:800: d3 += r * 1024;
d3 += r << 10 might be more indicative of the general tactic here. Not sure if
it's any more efficient; ideally the VM should be smart enough to make the
switch if so.

[sra1, 2013-08-27 22:26:22]

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.dart
File pkg/fixnum/lib/src/int64.dart (left):

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:134: int digit = Int32._decodeHex(c);
On 2013/08/27 21:36:02, Chris Bracken wrote:
> Wasn't introduced by this CL, but might be a good opportunity to rename this
to
> _decode(c) or something similarly non-hex-y.

Done.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.dart
File pkg/fixnum/lib/src/int64.dart (right):

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:132: d2 &= _MASK_2;
On 2013/08/27 21:36:02, Chris Bracken wrote:
> Wasn't introduced by this CL, but might not be bad to rename this to _MASK2 to
> be consistent with _BITS2.

Done.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:136: d0 = 0 - d0;
On 2013/08/27 21:36:02, Chris Bracken wrote:
> Is there a reason for preferring the binary - to a unary -? Perhaps
> VM/dart2js/V8 optimizes this out anyway? Granted, it's negligible if anything
:)

It helps type inference since the receiver is a constant.

I will be changing  d0 &= _MASK;  to  d0 = _MASK & d0;  for the same reason.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:137: int borrow = (d0 >> _BITS) & 1;
On 2013/08/27 21:36:02, Chris Bracken wrote:
> Is there any case in which d0 >> _BITS would be anything other than 0 or 1?

There is a history of flip-flopping between >> returning a signed or unsigned
result.  In the unsigned world, the value is usually (1<<10)-1.
Selecting the low bit means I don't have to call the slow _shiftRight helper.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:782: d0 = d0 & 0x3ff;
On 2013/08/27 21:36:02, Chris Bracken wrote:
> It's pretty clear to from the comment above that 0x3ff is a 10-bit mask,
though
> it might make it a tiny bit more readable to create a constant (maybe
_MASK10?).
> That said, I'm not entirely convinced it'd really be any better than 0x3ff.

I'm find the value of named constants dubious when the constant can't be
changed.  A name like _MASK10 might be confused with _BITS01.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:798: int r = d4 - q * fatRadix;
On 2013/08/27 21:36:02, Chris Bracken wrote:
> Is this more efficient than that modulo operator?

I don't know.  It really depends if the JS or VM jit can generate a fused
divmod.  If it can't, this is faster since the repeated hardware DIV instruction
is usually slower than MUL and if the jit can't tell everything is a SMI and
non-negative, % often needs a bunch sign checks.

https://codereview.chromium.org/23441004/diff/3001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:800: d3 += r * 1024;
On 2013/08/27 21:36:02, Chris Bracken wrote:
> d3 += r << 10 might be more indicative of the general tactic here. Not sure if
> it's any more efficient; ideally the VM should be smart enough to make the
> switch if so.

Done.

[Chris Bracken, 2013-08-27 23:02:11]

lgtm

https://codereview.chromium.org/23441004/diff/7001/pkg/fixnum/lib/src/int64.dart
File pkg/fixnum/lib/src/int64.dart (right):

https://codereview.chromium.org/23441004/diff/7001/pkg/fixnum/lib/src/int64.d...
pkg/fixnum/lib/src/int64.dart:805: int residue = 1024 * 1024 * d2 + 1024 * d1 +
d0;
From an indication of intent pt of view, perhaps d2 << 20 + d1 << 10 + d0?

https://codereview.chromium.org/23441004/diff/7001/pkg/fixnum/test/int_64_tes...
File pkg/fixnum/test/int_64_test.dart (right):

https://codereview.chromium.org/23441004/diff/7001/pkg/fixnum/test/int_64_tes...
pkg/fixnum/test/int_64_test.dart:537: expect(Int64.parseRadix('1000', 10), new
Int64.fromInt(1000));
checkInt(1000)?

[sra1, 2013-08-28 01:34:11]

Committed patchset #3 manually as r26760 (presubmit successful).