List.of and similar methods should be specialized based on the context

[mraleph]

There is an expectation that these two methods:

@pragma('vm:prefer-inline')
@pragma('dart2js:tryInline')
List<Object?> _copy1(List<Object?> array) {
  final List<Object?> clone = List<Object?>.filled(array.length, null);
  for (int j = 0; j < array.length; j++) {
    clone[j] = array[j];
  }
  return clone;
}

@pragma('vm:prefer-inline')
@pragma('dart2js:tryInline')
List<Object?> _copy2(List<Object?> array) {
  return List<Object?>.of(array, growable: false);
}

should have similar performance. Unfortunately this is not the case - List.of remains a call and resulting code is 20-50% slower even if TFA infers that array is always a fixed length list.

We should be able to specialise List.of into a fast (inlined) list copy if we know the type of the argument.

It might be good to figure out generic framework for such optimisations.

/cc @alexmarkov

[aam]

looks like a typo in line 8 return clone; List<Object?>.of(array, growable: false);

[mraleph]

@aam fixed thanks.

[rakudrama]

When I was working on making list splices smaller and faster, I noticed that AOT compiler gives up trying to inline too easily.

What would likely be best is if _copy was inlined several levels and then left as a call to _List._ofArray.

The inliner clones and simplifies List.of because it is called with one of the arguments bound to a constant.

  factory List.of(Iterable<E> elements, {bool growable: true}) {
    if (growable) {
      return _GrowableList.of(elements);
    } else {
      return _List.of(elements);
    }
  }

This simplifies to a single call, one with fewer arguments, but IsSmallLeaf rejects any result that has a static call that is not marked as 'prefer-inline'. What it should do is accept a simple reduction of one call to another provided the number of arguments does not increase.

I tried two ways of fixing this, but neither was successful.

The first way was to make IsSmallLeaf more accepting of inlining calls-to-calls. The call to List.of was replaced with a call to _List.of. But _List.of was never inlined at the next level. I suspect that the propagation of facts into the inlined code was inadequate as other passes do not run between levels of the 'inlining tree'. TFA results for the call sites inside the inlinee are too imprecise, so there needs to be some non-feedback way of refining the results.

The second way was to add a transform to replace List.of with _List.of with _List.of or _GrowableList.of, like the other List constructors . (I dislike these transforms since they change the call stack that the programmer sees - List.of, what they called, is nowhere to be seen. I think all the constructors should be written in the style of List.of and inlined. Then these transforms should be removed (after possibly fixing TFA to be aware of the growable: arguments.))

The transform did not work out well, since replacing List.of with _List.of removed one call, but not the expensive one.

AOT refused to inline _List.of because of https://github.com/dart-lang/sdk/issues/48207. It learned that sometimes there is no benefit, so it disabled inlining permanently. While impact analysis could be helpful, cases like this where the function dispatches to other functions could be handled by not making a permanent decision below a higher threshold. The threshold could be a function of the shape of the CFG - many similar sized functions have no chance of getting smaller and that is 'obvious'.

Occasionally the first few calls to _List.of were beneficial and were inlined before inlining was disabled permanently. The result then was disappointing code size, since the call to _List._ofArray was also inlined because the body of _List._ofArray has no calls. I think this could be prevented by marking static calls as the result of size-conscious inlining - the inlining heuristic (IsSmallLeaf) should be very strict for marked calls.

[aam]

Based on conversation with @alexmarkov: one possible path forward with this would be to introduce another pragma (vm:prefer-inline-if-concrete-arg-types-known?) along the lines of vm:prefer-inline/vm:never-inline so it can drive more aggressive inlining in presence of known concrete types for method parameters. Then use that pragma on _List.of and others that specialize based on argument type(_List.setRange ?)