Extension type dispatch.

[modulovalue]

(This issue is motivated by the idea to have support for augmented maps that are general and efficient. I'll be referring to simple trees to keep things simple.)

Consider, for example, a simple tree data structure with extra "augmented" data.

The tree might be big, so we want the augmented data to be represented in an efficient way.

• a third party has provided us with an augmentation based on extension types (as ThirdPartyAug), and with a function that expects a Tree where AUG needs to be a ThirdPartyAug (as run)
• another third party has provided us with the tree data structure (as Tree).

Here's what that might look like:

class Tree<AUG> {
  final Tree? left;
  final Tree? right;
  final AUG aug;

  const Tree({
    required this.left,
    required this.right,
    required this.aug,
  });
}

void main() {
  run<ThirdPartyAug>(
    tree: ... some big tree ...,
  );
}

void run<AUG extends ThirdPartyAug>({
  required Tree<AUG> tree,
}) {
  // ...
}

extension type const ThirdPartyAug(int sum) {}

If we wanted to make run support custom augmentations, then it seems like we would be forced not to bound AUG to ThirdPartyAug, but to provide the interface that we want explicitly, e.g.:

void main() {
  run2<FirstPartyAug>(
    tree: ... some big tree ...,
    sum: (final a) => a.sum,
  );
}

void run2<AUG>({
  required Tree<AUG> tree,
  required int Function(AUG) sum,
}) {
  // ...
}

class FirstPartyAug {
  final int sum;
  final int other;
  
  const FirstPartyAug({
    required this.sum,
    required this.other,
  });
}

In short:

• does that mean that type parameters bounded to an extension type are "useless"? (If the bound is the only type that it can ever be instantiated with, then why should the type parameter exist in the first place?)

• do we have to choose between efficiency (run) and generality (run2)? I suspect that calling sum via a level of indirection would be much less efficient than calling it directly by giving AUG a bound, or can we be general and maximally efficient at the same time?

[eernstg]

Sounds right: In run, in the code shown as // ..., every member invocation will statically resolve to a member declared by ThirdPartyAug (or a member from Object, which would be a normal, dispatched instance member invocation).

It doesn't matter which actual type argument is passed (if you're passing SomeSubtypeOfThirdPartyAug then the actual value of AUG at run time will be the ultimate representation type of SomeSubtypeOfThirdPartyAug), but it makes no difference for the code which is running: That code is determined at compile time, and this is only possible if we get it from the interface of ThirdPartyAug.

For run2, you are not using extension types at all, IIUC, and then you'd just get the standard OO semantics.

does that mean that type parameters bounded to an extension type are "useless"? (If the bound is the only type that it can ever be instantiated with, then why should the type parameter exist in the first place?)

Not quite: An extension type can be a useful type argument in the case where it is used multiple times in the signature:

extension type Inch(double value) implements double {}
extension on double { Inch get inch => Inch(this); }

X f<X extends double>(X x) {
  print('Floor: ${x.floor()}');
  return x;
}

void main() {
  var length = 1.5.inch;
  var otherLength = f(length);
  // bool _ = otherLength; // Shows that `otherLength` has type `Inch`.
}

do we have to choose between efficiency (run) and generality (run2)?

I think the concise way to characterize the situation is as follows: If you need OO dispatch then you need to use a reified type (and extension types are not reified, they are erased to the underlying representation type).

[modulovalue]

I think the concise way to characterize the situation is as follows: If you need OO dispatch then you need to use a reified type (and extension types are not reified, they are erased to the underlying representation type).

@eernstg do you think that it is possible to declare some run<T>() {} function where T has some members that are available inside of run, and (for the members of T) run is using static dispatch if available and OO dispatch if static dispatch is not available?

void main() {
  // run uses static dispatch for SomeExtensionType.foo
  run<SomeExtensionType>(
    // ...
  );
  // run uses OO dispatch for SomeClass.foo
  run<SomeClass>(
    // ...
  );
}

void run<T>() {
  // T has a member called foo 
}

extension type SomeExtensionType(double foo) {}

abstract class SomeClass {
  double get foo;
  
  String get bar;
}

I suppose some form of monomorphization would be required here to make this work, correct? And since there doesn't appear to be much support for monomorphization (dart-lang/site-www#4998), this is not possible yet?

[modulovalue]

I wrote a micro benchmark to compare how the different runtimes behave.

(Note: extension types have not shipped yet, so the numbers here are not final)

JS:

DartPad
master channel
Use Flutter version 3.14.0-14.0.pre.282 and Dart version 3.2.0-140.0.dev
+ Dart experiments: --enable-experiment=inline-class

via class on class: 184ms
via extension type on class: 64ms
via class on function: 160ms
via extension type on function: 61ms
via class on function monomorphic: 11ms
via extension type on function monomorphic: 10ms

Dart SDK version: 3.2.0-134.1.beta (beta) (Thu Sep 14 06:41:14 2023 -0700) on "macos_arm64"

JIT:

via class on class: 27ms
via extension type on class: 23ms
via class on function: 66ms
via extension type on function: 64ms
via class on function monomorphic: 22ms
via extension type on function monomorphic: 22ms

AOT:

via class on class: 14ms
via extension type on class: 71ms
via class on function: 52ms
via extension type on function: 30ms
via class on function monomorphic: 12ms
via extension type on function monomorphic: 12ms

Code:

void main() {
  const size = 10000000;
  final datasetClass = List.generate(size, (final a) => SomeClass(foo: a));
  final datasetExtensionType = List.generate(size, (final a) => SomeExtensionType(a));
  final sw = Stopwatch();
  final viaClass = RunClass();
  final viaExtensionType = RunExtensionType();
  sw.start();
  viaClass.execute(datasetClass);
  sw.stop();
  print("via class on class: ${sw.elapsedMilliseconds}ms");
  sw.reset();
  sw.start();
  viaExtensionType.execute(datasetExtensionType);
  sw.stop();
  print("via extension type on class: ${sw.elapsedMilliseconds}ms");
  sw.reset();
  sw.start();
  run<SomeClass>(datasetClass, (final a) => a.foo);
  sw.stop();
  print("via class on function: ${sw.elapsedMilliseconds}ms");
  sw.reset();
  sw.start();
  run<SomeExtensionType>(datasetExtensionType, (final a) => a.foo);
  sw.stop();
  print("via extension type on function: ${sw.elapsedMilliseconds}ms");
  sw.reset();
  sw.start();
  runClass(datasetClass);
  sw.stop();
  print("via class on function monomorphic: ${sw.elapsedMilliseconds}ms");
  sw.reset();
  sw.start();
  runExtensionType(datasetExtensionType);
  sw.stop();
  print("via extension type on function monomorphic: ${sw.elapsedMilliseconds}ms");
}

class RunExtensionType with Run<SomeExtensionType> {
  @override
  int sum(final SomeExtensionType v) => v.foo;
}

class RunClass with Run<SomeClass> {
  @override
  int sum(final SomeClass v) => v.foo;
}

extension type SomeExtensionType(int foo) {}

class SomeClass {
  final int foo;

  const SomeClass({
    required this.foo,
  });
}

mixin Run<T> {
  int sum(
    final T v,
  );

  int execute(
    final List<T> tree,
  ) {
    int total = 0;
    for (final a in tree) {
      total += sum(a);
    }
    return total;
  }
}

int run<T>(
  final List<T> data,
  final int Function(T) sum,
) {
  int total = 0;
  for (final a in data) {
    total += sum(a);
  }
  return total;
}

int runClass(
  final List<SomeClass> data,
) {
  int total = 0;
  for (final a in data) {
    total += a.foo;
  }
  return total;
}

int runExtensionType(
  final List<SomeExtensionType> data,
) {
  int total = 0;
  for (final a in data) {
    total += a.foo;
  }
  return total;
}

Unfortunately, there's no way to automatically monomorphize code. The manual monomorphization appears to be consistently the fastest and it would be great if Dart could offer an automated way for doing that.

Furthermore, injected "delegates" in the form of functions are very convenient, but appear not to be as efficient as having a class where the functions are methods. #1048 + some form of configurable monomorphization (dart-lang/sdk#52722 (comment)) might support making the convenient path as efficient as the class-based implementation.

[modulovalue]

The extension-type-related performance regression observed in the benchmark above has been fixed via dart-lang/sdk#53542 (comment)

---

There are several dimensions one can play with here:

• closures vs. delegates
• classes vs. functions
• generic classes vs. classes that use a shared mixin instantiated with a constant type argument
• generic functions vs. a function that was instantiated with a constant type argument (const foo = bar<int>;)

I am hopeful that the last dimension, that I did not consider before because it is a fairly new addition to Dart, could solve this issue in a convenient way. However, under AOT there appears to be a major performance regression that makes everything else 10x slower once that feature has been used. I'm going to file an issue for that tomorrow.

Furthermore, it's weird that under JIT, the manually monomorphized version appears to perform WORSE than a delegate + function + const foo = bar<int>; based implementation...

[eernstg]

@modulovalue wrote:

I suppose some form of monomorphization would be required here to make this work

True, it is not possible (at least not plausible) to perform static analysis of the body of run and decide that myT.foo resolves to a declaration in SomeExtensionType, and at the same time have another static analysis where resolves to a class instance member, and then generate code for both of those possible outcomes (which would be quite different), and finally turn run into one entity which can be used at run time.

The only plausible way to get that semantics, as far as I can see, would be to copy the declaration of run (in the extreme case we would have one copy for each unique type argument passed to run), and then run the static analysis on the body of each copy. A bit like a C++ template function.

However, that's a really awkward match for Dart, because it is in general not decidable which values any given type variable in Dart will have at run time. Also, there is no guarantee that the number of distinct values for a given type variable is limited by any finite number. So we'd want a "smart" approach where we generate just one run-time function for "most cases" (where the generated code is valid for all of them), and then a few extras for cases where the compiled code must be different.

(And then we'd need to consider what it means to call that function dynamically, or tearing it off in a location where no context type is available, etc.)

You could get this kind of behavior by declaring run as a macro and instantiating that macro at each call site, or generate a copy of the function which is specialized to each actual type argument list which will cause different code generation. When you mention 'manual monomorphization' it is my understanding that you are referring to a manual code transformation which corresponds to that macro expansion. However, I don't think the current proposal about macros in Dart will do this (for instance, an instantiated macro can not be an expression).

---

This discussion is very interesting, and it is important that we're aware of the performance characteristics of different "styles" of coding.

However, at the same time I can't help thinking that there is a very serious built-in conflict at play here: (1) We want to know all facts at compile time in order to generate code that runs fast, and (2) we want to write code which is generic in order to be able to use it with a large number of different factual situations.

"Just duplicate the generic code and specialize it for each call site" is an obvious answer, but it does also have a number of drawbacks (like code size explosion, and questionable readability).

It does make sense to try to find the golden mean path here, but we shouldn't be too surprised if the trade-offs appear to be hard. ;-)

[modulovalue]

Thank you, @eernstg. Your remark about global functions being constant (#1048 (comment)) gave me the idea to try the const foo = bar<int>; approach as a way to monomorphize generic functions. The JIT performance looks very promising, but the AOT performance is not quite there yet.

I'm going to wait until the following issues are resolved before I draw any further conclusions:

• [extension types/JIT/perf] manual monomorphization of generic function slower than constant function + delegate? sdk#53573
• [extension types] extension types slower than classes on AOT. sdk#53572
• [perf] AOT performance regression when "fully instantiated" constant functions are present. sdk#53571