The generic implementation of `math.Point` entails significant overhead. Should there be an alternative or warning?

[ignatz]

Hi Dart folks, long time no see.

Take this as an RFC... arguably math.Point is working exactly as implemented and nothing I'm going to say will be a major surprise, at least qualitatively....

I've always wondered if math.Point isn't a pathological use-case for reified generics? In my head, reified generics work great for cases where you have a lot of generic code (where you wanna pay the cost to binary size once) dealing with mostly opaque objects like with containers. However, math.Point is the polar opposite. On top, the operations it implements are extremely cheap lending exacerbated significance to the virtual function overhead that comes with reified generics.

I finally came around to quantify the impact with a silly micro-benchmark (never trust a micro-benchmark in general and don't trust me specifically) and found the overhead for simple vector additions to be in the order of 20+x [1].
Motivated by that result I replaced math.Point with my own basic points in some number-crunching heavy libraries and got real-life performance improvements of tens or hundreds of percent. Nothing to sneeze at.

So my question to you, is math.Point (and probably math.Rectangle as well) setting a bad example? By virtue of being in the standard library, it's the go-to solution for many mathy dart libraries. Unless you want to write code that specifically deals with Point<num> (and all the type assertion exceptions that come with it), there isn't much benefit in math.Point being generic. My hunch is that most users would happily pay the cost to binary size for an unrolled version given the significant performance advantage. I would even argue that something as frame-time-sensitive as Flutter would greatly benefit from a pivot.
I understand that removing math.Point won't fly w/o breaking the world but maybe it's worth warning/steering users to an unrolled alternative?
Curious to hear what you think.

Cheers,
Sebastian

[1] my micro-benchmark:

import 'dart:math';

class PointInt {
  final int x;
  final int y;

  const PointInt(this.x, this.y);

  PointInt operator +(PointInt other) =>
    PointInt(x + other.x, y + other.y);
}

class PointDouble {
  final double x;
  final double y;

  const PointDouble(this.x, this.y);

  PointDouble operator +(PointDouble other) =>
    PointDouble(x + other.x, y + other.y);
}

const N = 1000000000;

final ints = <(String, Function)>[
  ('PointInt', () {
      var x = PointInt(23, 23), y = PointInt(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
  ('Point<int>', () {
      var x = Point<int>(23, 23), y = Point<int>(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
];

final doubles = <(String, Function)>[
  ('PointDouble', () {
      var x = PointDouble(23, 23), y = PointDouble(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
  ('Point<double>',
    () {
      var x = Point<double>(23, 23), y = Point<double>(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
];

void main() {
  for (final suite in [ints, doubles]) {
    final results = suite.map((s) {
      final (k, f) = s;
      final w = Stopwatch()..start();
      f();
      return (k, w.elapsed);
    });

    final factor =
        results.last.$2.inMicroseconds / results.first.$2.inMicroseconds;

    print('${results}: ${factor.toStringAsFixed(1)}');
  }
}

and example output:

$ dart compile exe generic2.dart && ./generic2.exe
Generated: /home/sebastian/projects/dart/generic2.exe
((PointInt, 0:00:00.335539), (Point<int>, 0:00:08.149218)): 19.1
((PointDouble, 0:00:00.284572), (Point<double>, 0:00:09.913140)): 23.1

[eernstg]

That's a very interesting observation! Note the relations to monomorphization, e.g., issue #52722, and other issues that @modulovalue created or commented on.

Perhaps macros could offer compact code (avoiding two or more copies of essentially the same code at the source level) with type specific variants (e.g., int and double specific variants of classes like Point).

[modulovalue]

@ignatz if you want backwards compatibility with the Point interface, you could try subclassing Point from dart:math like this:

import 'dart:math';

class PointInt {
  final int x;
  final int y;

  const PointInt(this.x, this.y);

  PointInt operator +(PointInt other) =>
    PointInt(x + other.x, y + other.y);
}

class PointDouble {
  final double x;
  final double y;

  const PointDouble(this.x, this.y);

  PointDouble operator +(PointDouble other) =>
    PointDouble(x + other.x, y + other.y);
}

class PointDouble2 extends Point<double> {
  const PointDouble2(super.x, super.y);
  
  PointDouble2 operator +(covariant PointDouble2 other) =>
    PointDouble2(x + other.x, y + other.y);
}

class PointInt2 extends Point<int> {
  const PointInt2(super.x, super.y);
  
  PointInt2 operator +(covariant PointInt2 other) =>
    PointInt2(x + other.x, y + other.y);
}

const N = 10000000;

final ints = <(String, Function)>[
  ('PointInt', () {
      var x = PointInt(23, 23), y = PointInt(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
  ('Point<int>', () {
      var x = Point<int>(23, 23), y = Point<int>(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
  ('PointInt2', () {
      var x = PointInt2(23, 23), y = PointInt2(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
];

final doubles = <(String, Function)>[
  ('PointDouble', () {
      var x = PointDouble(23, 23), y = PointDouble(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
  ('Point<double>',
    () {
      var x = Point<double>(23, 23), y = Point<double>(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
  ('PointDouble2',
    () {
      var x = PointDouble2(23, 23), y = PointDouble2(42, 42);
      for (int i = 0; i < N; ++i) x += y;
    }),
];

void main() {
  for (final suite in [ints, doubles]) {
    final results = suite.map((s) {
      final (k, f) = s;
      final w = Stopwatch()..start();
      f();
      return (k, w.elapsed);
    });

    final factor =
        results.last.$2.inMicroseconds / results.first.$2.inMicroseconds;

    print('${results}: ${factor.toStringAsFixed(1)}');
  }
}

I've tested it on DartPad (other runtimes might vary) and it appears to provide the performance that you're looking for:

((PointInt, 0:00:00.047000), (Point<int>, 0:00:00.235000), (PointInt2, 0:00:00.046000)): 1.4
((PointDouble, 0:00:00.047000), (Point<double>, 0:00:00.239000), (PointDouble2, 0:00:00.049000)): 1.0

explanation

A self type would be nice for getting rid of the use of covariant here.

It looks like other languages have annotations for doing this in an automated way.

For performance sensitive use cases there's a first party vector_math package that avoids the use of generics.

[ignatz]

Thanks Erik, thanks Modestas for the super quick reply.

Let me take a step back, I feel like we're mixing two conversations:

1. How this could be fixed, e.g. with a new language/toolchain features could force monomorphization of all math.Points in existence w/o requiring interaction by library maintainers
2. What existing alternatives there are or how to best roll your own.

Personally, I'm not very interested in (2.) unless it comes shipped as part of the standard library and with clear guidance to create momentum. Implementing your own Point class isn't very hard or verbose. However, getting folks to use yours or having to deal with the glue for 50 different Point implementations throughout your program's transitive closure of dependencies is hard.

Let me just quickly comment on the proposed inheritance-based solution. It is a fun little detail that inheritance forces monomorphization (guaranteed or not). I will certainly remember this trick. Compiling to native, I'm seeing the projected performance gains, however in "compat" mode:

Point<int> x = PointInt2(23, 23);
Point<int> y = PointInt2(42, 42);
for (int i = 0; i < N; ++i) x += y;

I'm seeing a 12x performance reduction over plain PointInt. Whether or not this "compat" approach can save me anything in practice, both in terms of typing and performance, seems very case dependent. What does an external library looking like List<Point> expensive(List<Point> input) do internally?
Independent of vector_math, PointInt, PointInt2, if I have to convince a library owner to move away from math.Point the amount of work for them will roughly be the same and my lack of persuasiveness would only be helped by some divine endorsement, e.g. a standard library provided solution (no matter the implemenation) or at least a big friendly warning regarding math.Point's performance implications.

Coming back to (1.), before-mentioned annotations (et al) would arguably be a silver-bullet: huge performance gains w/o any additional work besides re-compiling. I'm keen to hear from you how attainable such a solution would be in the short/mid/long-term? Depending on the time-horizon, maybe there's still an opportunity to at least create awareness one way or another?
From my point of view, Dart is a really fast language, just math.Point leaves a lot of performance on the table and many authors don't even realize.

[lrhn]

Point and Rectangle are not great classes, and not well-positioned in dart:math. The design is actually more "screen"-based than math based. (The rectangle considers (min-x, min-y) the top-left corner, not the bottom-left corner, like "screen coordinates"). And it's more of a vector than a point (you can't add points together, that's a vector operation).
The classes are trying to solve too many problems, while doing none of them really well.

The rectangle being defined in terms of top, left, width and height makes a lot of things more complicated (but it ensures that you won't get a width of infinity without having a left or right of infinity too, which is possible for left = -maxFiniteDouble, right = maxFiniteDouble, width = right - left. But you can get a NaN right if left is -infinity and width is infinity. Just don't be infinite, please.)

I'd be happy to move the class into package:html or similar, which is where it's used, if I can get away with it. (But they probably want just the Point<int> type then).

Deprecating it entirely and throwing it away would also be great. Probably hard to sell, since there are uses.

Deprecating the class and replacing it with an extension type might be more sellable, at least you should get some performance benefits.
Something like https://dartpad.dev/?id=9f717b5f699fcda195d5d3d466d2951f&channel=master

Still, removing, replacing, or even changing, platform library types is hard, because there is no versioning or opt-out for users. Their code gets the new version when their users upgrade their SDK.

[ignatz]

Deprecating it entirely and throwing it away would also be great. Probably hard to sell, since there are uses.

I don't see your proposals as mutually exclusive. Even if the end goal was to throw it away eventually, you'd need to offer alternatives and leave plenty of lead time first.

Deprecating the class and replacing it with an extension type might be more sellable, at least you should get some performance benefits.
Something like https://dartpad.dev/?id=9f717b5f699fcda195d5d3d466d2951f&channel=master

Marking math.Point (et al) explicitly as Deprecated and offering alternatives would certainly send a very strong signal and such be all I could have ever hoped for.

I had a quick look at extension types, it's not clear to me if one even wanted to tie shiny new alternatives to math.Point through inheritance or else. Personally, I'd be fine if they don't share any traits, which would also help to address some of your earlier concerns that math.Point and math.Ractangle should maybe do less or certain things differently.

Hope you folks will have a chance to talk this out. I don't feel very strong, at least not yet, towards any solution. In the end it would just be lovely, to see fewer libraries grab for math.Point in compute-heavy tasks and sometimes unknowingly pay 3 or 4 digit percentage points overhead.

Thanks y'all for being so responsive and on top of things.