UTF8.decode is slow (performance)

[Hixie]

UTF8.decode seems surprisingly slow for large buffers.

Using this Flutter program:

import 'dart:async';
import 'dart:convert';
import 'dart:typed_data';

import 'package:flutter/services.dart';

Future<Null> main() async {
  ByteData data = await rootBundle.load('LICENSE');
  for (int i = 1024; i < data.lengthInBytes; i += 1024) {
    final Stopwatch watch = new Stopwatch()..start();
    UTF8.decode(data.buffer.asUint8List(0, i));
    int time = watch.elapsedMilliseconds;
    print('${"$i bytes".padLeft(15)} ${"${time}ms".padLeft(10)} ${(1000 / 1024 * i / time).toStringAsFixed(1)} KB per second');
  }
}

...I find that on a Pixel 2 XL, 4KB is parsed in about 1ms, 40KB in about 12ms, and 400KB in about 135ms. This is only about 3MB per second. Then again, I'm not sure what would be considered good throughput on this device. Maybe this is as good as we can get?

Presumably this could be fixed in the most radical fashion by supporting UTF-8 as a native data type.

[mraleph]

All of the decoding is implemented in Dart so performance suffers in AOT mode.

JIT mode (debug) does around 15-20 MB per second vs 1.7-2MB in AOT mode on Nexus 5X.

• Short term this can be addressed by moving UTF8 decoding into C++, if it is a bottleneck.

We expect things to become better in AOT mode post Dart 2 transition as AOT code quality should improve considerably. However it is not trivial to reach the parity with JIT on this benchmark.

LICENSE is a Latin1 file so it essentially tests how fast we can determine that and create a string out of it.

Most important loops for the benchmark are in scanOneByteCharacters, _scanCodeUnits and _createOneByteString.

• Note: _scanCodeUnits does thing that was already done by scanOneByteCharacters so it is obviously wasteful and needs to be fixed first thing.

Here is how all those functions look:

    int scanOneByteCharacters(List<int> units, int from) {
      final to = endIndex;
      final mask = _ONE_BYTE_LIMIT;
      for (var i = from; i < to; i++) {
        final unit = units[i];
        if ((unit & mask) != unit) return i - from;
      }
      return to - from;
    }

List<int> units does not really tell much to the AOT compiler (even in Dart 2 mode) because there are multiple types implementing lists, while JIT is capable of establishing that units is a Uint8 view (by observing the type feedback collected in runtime) and completely inlining units[i] because the code is monomorphic.

In Dart 2 mode we might be able to establish the same thing using type flow analysis, but I am cautiously optimistic about that because it is likely that people invoke UTF8.decode on various List<int> implementations.

It might be that we need to implement something heavier as a real solution - e.g. some mechanism to duplicate / "version" performance sensitive code that manipulates typed lists.

[rakudrama]

We have already solved this problem for dart2js/browser.

There is a hook for host-specific acceleration.
The dart2js runtime uses this hook to do decoding via the browser's TextDecoder, which provided a 10x speedup on browsers that support TextDecoder.
VM/Flutter could also use this hook to detect byte arrays and use an alternative implementation.

If you hook to a second implementation, you could use C++, or a clone of the current implementation and modify it to use the byte array implementation type. If you do this, I would advise bailing out to the main algorithm to handle error cases since the Dart runtime is incompatible with the browser implementation in error cases. We want to fix the discrepancy by changing the Dart library to match the browser as that would make the in-browser conversion more efficient by avoiding a validation scan. If you fall-back to the main implementation on edge cases, that will ensure that we need to fix edge cases in only one implementation.

@lrhn fyi.

[mraleph]

Thanks for the tip about _convertIntercepted @rakudrama. We could use it if we decide to do a short term solution for just JSON.decode.

The real problem however is much larger - if the user writes similar code they will see similar slowness (especially comparing JIT vs AOT), so I would like us to think about it in that context too.

[Hixie]

it is likely that people invoke UTF8.decode on various List<int> implementations.

It seems extremely likely to me that any large inputs are going to be from ByteData instances.

FWIW, I would be perfectly fine with specialized ByteData or Uint8List variants of this API (and other similar APIs that take List<int>). In general in Flutter land there are definitely codepaths where we don't even support the non-ByteData case.

[mraleph]

12c461b by @aartbik improved performance of this microbenchmark on 64-bit platforms (4-5x on my measurements). I have not measured ARM32 yet.

Before the change:

I/flutter (22444):    622592 bytes      337ms 1804.2 KB per second

after the change:

I/flutter (22623):    622592 bytes       66ms 9212.1 KB per second