Optimize int.parse with a radix.

Optimize int.parse with a radix.

Handles bignums by parsing chunks of of digits into smis, then
combining the smi into a (potential) bignum, using smi arithmetic as
much as possible.
Use the optimized version for radix 10 and 16 too, instead of going to runtime.

R=fschneider@google.com

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

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

[Lasse Reichstein Nielsen, 2014-09-23 11:34:44]

lrn@google.com changed reviewers:
+ fschneider@google.com

[Lasse Reichstein Nielsen, 2014-09-23 11:34:45]

This significantly speeds up parsing with a radix, and works for bignums too.

https://codereview.chromium.org/596763002/diff/20001/runtime/lib/integers_pat...
File runtime/lib/integers_patch.dart (right):

https://codereview.chromium.org/596763002/diff/20001/runtime/lib/integers_pat...
runtime/lib/integers_patch.dart:40: }
This was what was already on the tip of tree.

https://codereview.chromium.org/596763002/diff/20001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/596763002/diff/20001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:269: return (codeUnit == 0x85) || (codeUnit ==
0xA0);
Restructured to return false quickly on most ASCII chars (range 0x21..0x7f).

[srdjan, 2014-09-24 20:05:35]

srdjan@google.com changed reviewers:
+ srdjan@google.com

[srdjan, 2014-09-24 20:05:35]

DBC

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:268: if (codeUnit < 0x85) return false;
Is that check worth it? With two below you have three checks instead of two and
more complex code.

[Lasse Reichstein Nielsen, 2014-09-24 20:26:30]

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:268: if (codeUnit < 0x85) return false;
Ack, probably not for the one-byte case. I copied it from the two-byte case
where it's guarding a much more complex test.

[Florian Schneider, 2014-09-25 11:38:39]

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
File runtime/lib/integers_patch.dart (right):

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
runtime/lib/integers_patch.dart:137: result = (result * multiplier) + (sign *
smi);
Maybe factor out the multiplication with sign out of the loop?

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
runtime/lib/integers_patch.dart:156: int digit = char ^ 0x30;
Is this computation of the digit actually faster than the old way? e.g. for
radix 16 which is common.

[Lasse Reichstein Nielsen, 2014-09-25 14:37:17]

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
File runtime/lib/integers_patch.dart (right):

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
runtime/lib/integers_patch.dart:137: result = (result * multiplier) + (sign *
smi);
This makes all the multiplications Smi operations, instead of having a bignum
multiplication at the end - potentially copying a large result.

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
runtime/lib/integers_patch.dart:156: int digit = char ^ 0x30;
Testing just for hex, it seems to be pretty much the same. I'd say marginally
faster than table lookup (even if I cut the table range check down to only one
comparison), but by a marginal so small it could easily be noise.

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:268: if (codeUnit < 0x85) return false;
Fixed.
Any chance of optimizing so that (codeunit < 0x85) followed by (codeunit ==
0x85) always boils down to one compare instruction? :)

[Florian Schneider, 2014-09-26 11:57:05]

LGTM.

Please add test coverage for the radixes if not already present.

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
File runtime/lib/integers_patch.dart (right):

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
runtime/lib/integers_patch.dart:137: result = (result * multiplier) + (sign *
smi);
On 2014/09/25 14:37:16, Lasse Reichstein Nielsen wrote:
> This makes all the multiplications Smi operations, instead of having a bignum
> multiplication at the end - potentially copying a large result.
> 

I see - that makes sense.

https://codereview.chromium.org/596763002/diff/40001/runtime/lib/integers_pat...
runtime/lib/integers_patch.dart:156: int digit = char ^ 0x30;
On 2014/09/25 14:37:16, Lasse Reichstein Nielsen wrote:
> Testing just for hex, it seems to be pretty much the same. I'd say marginally
> faster than table lookup (even if I cut the table range check down to only one
> comparison), but by a marginal so small it could easily be noise.

Acknowledged.

[Lasse Reichstein Nielsen, 2014-09-26 12:03:19]

I have added a significant number of new tests on top of what was already there.

[Lasse Reichstein Nielsen, 2014-09-26 12:04:52]

Committed patchset #7 (id:120001) manually as 40702 (presubmit successful).

[Lasse Reichstein Nielsen, 2014-09-26 12:13:55]

Committed patchset #8 (id:140001) manually as 40703 (presubmit successful).