`PbList` checks element type twice on each add

[osa1]

I don't think this can be fixed, but it's still worth documenting this issue somewhere probably..

PbList.add currently checks the element type, and then calls GrowableList.add, which checks the element type again.

Here's the relevant Wasm when compiled with -O2: (the default optimization setting when building Flutter apps)

(func $PbList.add (;353;) (param $var0 (ref $Object)) (param $var1 (ref null $#Top)) (result (ref null $#Top))
  (local $var2 (ref $PbList))
  (local $var3 (ref $_Type))
  (local $var4 (ref $#Closure-0-1))
  local.get $var0
  ref.cast $PbList
  local.tee $var2
  struct.get $PbList $field2
  local.set $var3
  local.get $var1
  ref.is_null
  if (result i32)
    local.get $var3
    struct.get $_Type $field2
  else
    local.get $var3
    local.get $var1
    ref.as_non_null
    call $_InterfaceType._checkInstance
  end
  ...
)

(func $GrowableList.add (;174;) (param $var0 (ref $Object)) (param $var1 (ref null $#Top)) (result (ref null $#Top))
  (local $var2 (ref $_Type))
  (local $var3 (ref $WasmListBase))
  (local $var4 (ref $#Top))
  (local $var5 i64)
  (local $var6 i32)
  local.get $var0
  ref.cast $WasmListBase
  local.tee $var3
  struct.get $WasmListBase $field2
  local.set $var2
  local.get $var1
  ref.is_null
  if (result i32)
    local.get $var2
    struct.get $_Type $field2
  else
    block $label0 (result i32)
      i32.const 1
      local.get $var2
      struct.get $_Type $field0
      local.tee $var6
      i32.const 8
      i32.eq
      br_if $label0
      drop
      local.get $var1
      ref.as_non_null
      local.set $var4
      local.get $var6
      i32.const 12
      i32.eq
      if
        local.get $var2
        local.get $var4
        call $_InterfaceType._checkInstance
        br $label0
      end
      local.get $var2
      local.get $var4
      local.get $var2
      struct.get $_Type $field0
      i32.const 287
      i32.add
      call_indirect (param (ref $_Type) (ref $#Top)) (result i32)
    end $label0
  end
  i32.eqz
  if
    local.get $var1
    local.get $var2
    call $_TypeError._throwAsCheckError
  end
  ...
)

Now consider a packed field decoding loop, with #959.

For each 4-byte integer, we box the integer, and then check the type of it twice.

To have an idea of how much we could save, if I omit type checks in the generated code with -O4, here's before and after:

// Before
protobuf_PackedInt32Decoding(RunTimeRaw): 49775.0 us.

// After
protobuf_PackedInt32Decoding(RunTimeRaw): 36812.5 us.

That's 26% of decoding time wasted on redundant type checks.

[mkustermann]

The fact that we perform the check multiple times is due to wrapping List<T>, something like this:

class PbList<E> {
  final List<E> _wrapped = <E>[]; // (in reality slightly different, as we have multiple assignments in different constructors)

  void add(E value) => _wrapped.add(value);
}

This could be something that TFA (or even CFE, although that may be a stretch) could optimize: The _wrapped.add(value) call's covariance type check is known to be successful because we know that the E of PBList<E> is the same as the E in List<E> (i.e. the ladder is not a subtype)

In some sense this would be an extension of the optimization we do already with dispatches on this.foo(value) targeting foo(E value) where we can use the unchecked entrypoint as we know on callsite that value is E and the target E is the same.

/cc @alexmarkov @chloestefantsova

[alexmarkov]

@osa1 Could you post the reproduction steps? I'd like to investigate what exactly happens in TFA in this case.

@mkustermann Do we use multiple (checked/unchecked) entry points in dart2wasm? If not, and we're not inlining GrowableList.add into PbList.add, then how would it help to know that certain call site does not need argument type checks which are performed inside the callee (GrowableList.add)?

@rakudrama Could this be addressed by the optimization you're building?

[osa1]

@alexmarkov to repro:

• In benchmarks/ directory:
• Run ./tool/compile_protos.sh
• Compile bin/binary_decode_packed.dart

You should see a bunch of references to PbList.add in the kernels or generated code.

The Wasm code in my message above are generated with dart compile wasm -O2 --no-strip-wasm bin/binary_decode_packed.dart and then by disassembling the generated .wasm.

[mkustermann]

@alexmarkov Yes, I recently added support for this in the compiler and we always generate them if there's calls to them.

[alexmarkov]

There are multiple things which currently prevent TFA from inferring that GrowableList.add call from PbList.add is unchecked:

• TFA does not partition fields: for each field a single type is calculated (union of all types of possible values). So, if a field could contain a GrowableList<int> and GrowableList<String>, then we would only know that it is a GrowableList.
• PbList._wrappedList is initialized with different type arguments in different constructors: _wrappedList = <E>[], _wrappedList = List<E>.from(from) and _wrappedList = _emptyList where _emptyList = <Never>[]). So, even if we would propagate symbolic type arguments in addition to known type arguments, inferred type of PbList._wrappedList would still be GrowableList without type arguments.

[osa1]

PbList._wrappedList is initialized with different type arguments in different constructors: _wrappedList = [], _wrappedList = List.from(from) and _wrappedList = _emptyList where _emptyList = []). So, even if we would propagate symbolic type arguments in addition to known type arguments, inferred type of PbList._wrappedList would still be GrowableList without type arguments.

This is actually deliberate, the code even tries to document it:

protobuf.dart/protobuf/lib/src/protobuf/pb_list.dart

Lines 22 to 26 in 9daf5ca

	/// A growable list, to be used in `unmodifiable` constructor to avoid
	/// allocating a list every time.
	///
	/// We can't use `const []` as it makes the `_wrappedList` field polymorphic.
	static final _emptyList = <Never>[];

To avoid making _wrappedList GrowableList in some cases and non-growable in others, we use growable list always. To avoid allocating in unmodifiable we use a static final value with Never as the type argument so that it will be a valid value for any E.

protobuf.dart/protobuf/lib/src/protobuf/pb_list.dart

Lines 38 to 41 in 9daf5ca

	PbList.unmodifiable()
	: _wrappedList = _emptyList,
	_check = _checkNotNull,
	_isReadOnly = true;

If we use <E>[] or List.unmodifiable that allocates in unmodifiable. Currently it's a global.get in Wasm.

I tried using <E>[], but it didn't improve the final code, and made it allocate a new list in unmodifiable. So at least currently it's not worth changing the code.

(I think when I added this code const <Never>[] was probably not allowed. We can use it now as the value of _wrappedList in unmodifiable, but it doesn't change the final generated code.)

[mkustermann]

@alexmarkov Correct about the <Never>[], but assume we always use <E>[], how could we make this work?

I think it's actually a very common pattern that a generic class has internal fields that it initializes with the same type parameters.

[rakudrama]

My proposed invariance analysis would be helpful here.

It would handle this case since (provided we replace <Never>[] with <E>[]), the analysis would infer _wrapped.E == E.
For the SDK class QueueList<E>, the internal list _table always has type parameter _table.E == E?.

The basic idea is to do something a bit like the Dart language type inference / checking / promotion with extra subtype constraints to find cycles that mean a shared type is invariant. Seed constraints for the analysis come from annotations on external factories, by definition for generative constructors which just store their type arguments. We have benchmarks that should improve markedly when this is implemented.

The results of the invariance analysis would be communicated via a flag that is already in the Kernel IR. InstanceInvocation.isInvariant can be set to indicate that the target method's parametric covariant checks will pass. The expansion of control flow collections set this bit for the calls to add() and addAll(). dart2js and AOT use this bit to avoid checks.

(TFA very often can mark the control flow collection calls as using use the unchecked entry. When TFA succeeds, the isInvariant bit is not needed (for AOT and wasm). TFA is pretty reliable when the type parameter is constant.)

The control flow collection

    final list = <String>[if (a != null) a, if (b != null) b];

is essentially compiled to

  final list = <String>[];
  if (a != null) list.add(a); 
  if (b != null) list.add(b);

If you write the expansion by hand, it does not have the isInvariant bits.

AOT generates the same code for the above because the type is constant and TFA adds 'unchecked-entry' to the metadata.

However, if the type is symbolic, the code is better for the control flow collection.

Consider:

List<E> makeList1<E>(E? a, E? b) => [if (a != null) a, if (b != null) b];

List<E> makeList2<E>(E? a, E? b) {
  final List<E> result = [];
  if (a != null) result.add(a);
  if (b != null) result.add(b);
  return result;
}

The code generated for makeList1 by AOT has fewer checks (if you work hard enough to make calls polymorphic in the type parameter and prevent inlining).

A simple form of invariance analysis might figure out that the calls in makeList2 are invariant. It will take something more advanced for ListQueue, where the types are related rather than exact matches, the field is not final and has multiple assignments.

PbList as it stands is intriguing. - there is a strong correlation between _isReadOnly and the reachability of calls that might use the unchecked entry point. There is also a strong correlation between the constructor and _isReadOnly. I'm normally very wary of going down the state space explosion rabbit-hole, but this has such a simple relation that it might be sufficient to pretend it is a different class for each constructor.

[mkustermann]

My proposed invariance analysis would be helpful here.

👍

@rakudrama Do you have any idea on how costly this analysis would be (in terms of compile-time)? I'd guess that a simple analysis would cover most common cases (e.g. final field case like in protobuf (assuming we don't have <Never>[] case)) and wouldn't be too hard to implement.