WebAssembly / WebAssembly/binaryen

Avoid hosting allocations (especially array allocations) out of conditional paths

Open
#7,304 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
WebAssembly
Stars
8.6k
Forks
885
Avg merge
1d 19h
Merged PRs (30d)
69

Description

We have for example this Dart code

const _codeUnitsCacheSize = 512;
final _codeUnitsCache = WasmArray<WasmI16>(_codeUnitsCacheSize);

JSStringImpl _jsStringFromAsciiBytes(U8List source, int start, int end) {
  final length = end - start;
  final array =
      length <= _codeUnitsCacheSize
          ? _codeUnitsCache
          : WasmArray<WasmI16>(length);
  for (int j = start, i = 0; i < length; ++i, ++j) {
    array.write(i, source.getUnchecked(j));
  }
  return JSStringImpl(
    jsStringFromCharCodeArray(array, 0.toWasmI32(), length.toWasmI32()),
  );
}

Notice that we have a fast path: For small lengths we want to avoid allocating the wasm array and use a cache instead.

Compiled with dart2wasm and optimized with binaryen we get this:

  (func $_jsStringFromAsciiBytes (;452;) (param $var0 (ref $U8List)) (param $var1 i64) (param $var2 i64) (result (ref $JSValue_66))
    (local $var3 i64)
    (local $var4 (ref $Array<i16>))
    global.get $_codeUnitsCache
    local.get $var2
    local.get $var1
    i64.sub
    local.tee $var3
    i32.wrap_i64
    array.new_default $Array<i16>
    local.get $var3
    i64.const 512
    i64.le_s
    select (ref $Array<i16>)
    local.set $var4
    i64.const 0
    local.set $var2
    loop $label0
      local.get $var2
      local.get $var3
      i64.lt_s
      if
        local.get $var4
        local.get $var2
        i32.wrap_i64
        local.get $var0
        struct.get $U8List $field3
        local.get $var1
        i32.wrap_i64
        array.get_u $Array<WasmI8>
        array.set $Array<i16>
        local.get $var2
        i64.const 1
        i64.add
        local.set $var2
        local.get $var1
        i64.const 1
        i64.add
        local.set $var1
        br $label0
      end
    end $label0
    local.get $var4
    i32.const 0
    local.get $var3
    i32.wrap_i64
    call $wasm:js-string.fromCharCodeArray (import)
    call $JSStringImpl
  )

Notice that it hoisted the array allocation (the slow path) out of the conditional and unconditionally allocates and then uses a select (ref $Array<i16>) to select between the two.

This is very problematic

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the supplied Dart example through dart2wasm and Binaryen, then inspect the optimization that turns the conditional WasmArray allocation into an unconditional array.new_default followed by select. Done means the slow-path array allocation remains conditional and the optimized output no longer allocates it for the cache path.

Written by the indexing model from the issue text.

Assessment

Tech stack
dart, wasm
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.