commit c8cf274cffcb7f0a880a98db6fd6d482d73e4b13
author Ömer Sinan Ağacan <omersa@google.com> Mon Aug 05 12:25:18 2024 +0000
committer Commit Queue <dart-scoped@luci-project-accounts.iam.gserviceaccount.com> Mon Aug 05 12:25:18 2024 +0000
tree 3ef177cf468ba1c97540d7a6d4c1e49a34c776ca
parent b121353f2b3e290290a8ac3792f1e3687847977b

[dart2wasm] Refactor int parsing

This refactors dart2wasm's `int.parse` and `int.tryParse` implementations.

Current implementation is copied from VM, which supports 63-bit "smi"
integers and 32-bit integers. In dart2wasm we only support 64-bit
integers. This change updates the int parsing to handle 64-bit ints.

The changes can be summarized as refactorings plus one change.

Refactorings:

- Remove all mentions of "smi"s and 32-bit integer parsing support.

- Move patched public members `parse` and `tryParse` to the beginning of
  the patched class, to allow top-down reading of the file and separate
  entry points from internal functions.

- Refactor the `last` (inclusive last character index) parameter of
  `_tryParseSmi` (renamed to `_tryParseIntRadix10` in this CL) as `end`
  (exlusive last character index), to be consistent with the rest of the
  function in the same file.

- Remove redundant `null` checks from the pre-sound-null-safe days.

- Remove 32-bit constants from the `_PARSE_LIMITS` table.

Change:

Current code, when the input string is larger than the max. number of
digits that fit into the `int` type, parses one "block" at a time, then
combines the blocks.

(A block is a substring in the input that can be parsed as `int` without
overflows)

This makes the code very complicated (with lazily generated "overflow
limits" table, complicated logic to combine blocks while checking for
overflows) to handle just one digit after a block.

With this change we do something simpler: first we skip all leading
zeros. This part is new, current code does not skip leading zeros and
handle them as a part of a block. After the zeros we parse one block as
usual. After the block, we can parse at most two more digits without an
overflow (or underflow if the number is negative). Handling of these two
digits does not need to be optimized with special checks and table
lookups, because the amount of work done for the digits is small, and
branching and the cost of table lookups followed by more efficient code
will probably be slower than just handling digits in a simple way.

This change is done in `_parseRadix`. Rest of the changes in the file
are refactoring, as described above.

The `_PARSE_LIMITS` table with max. number of digits that fit into an
`int` is updated using this program:

```
void main() {
  final maxI64 = 9223372036854775807;
  for (int radix = 2; radix <= 36; radix += 1) {
    final str = maxI64.toRadixString(radix);
    print("Max I64 in radix $radix = $str, num digits = ${str.length}");
  }
}
```

For example, max. 64-bit signed integer in radix 20 is
"5cbfjia3fh26ja7", which has 15 digits. Unless all of the digits are the
largest digit of the radix, we need to subtract one. So the max. number
of digits for radix 20 is 14.

The only radixes where all digits are the largest digit are 2 and 8. In
these cases we can handle 63 and 21 digits respectively (instead of 62
and 20). In all other bases we subtract the number of digits printed by
the program above by one in the table.

# Benchmarks

Golem reports 61% improvement in the benchmark `Int.parse.0032.bits`.

Golem also reports 18% slowdown in Utf8Encode.sk.10M, however the Wasms
for that benchmark before and after this change are identical, so it
must be noise.

Change-Id: Ia35a50a0328e680be2d494405e13caaded1b7ad9
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/372281
Commit-Queue: Ömer Ağacan <omersa@google.com>
Reviewed-by: Martin Kustermann <kustermann@google.com>