[FEATURE] Use classes instead of Records for efficiency

[josxha]

The research in #1750 (comment) and #1750 (comment) points out the reasons to avoid records.
Records have no advantage on memory consumtion while they require about double the time to be initialized.

As a consequence we should remove records from the package and use immutable classes in favour of it.

[monsieurtanuki]

@josxha That would include this one in Projection:

  (double, double) projectXY(LatLng latlng);

Would definitely be a breaking change, but would hopefully bring better performances. Something like that?

  DoublePoint projectDoublePoint(LatLng latlng);

Instead of redundant code like this one:

  _ProjectedPolygon._fromPolygon(Projection projection, Polygon<R> polygon)
      : this._(
          polygon: polygon,
          points: List<DoublePoint>.generate(
            polygon.points.length,
            (j) {
              final (x, y) = projection.projectXY(polygon.points[j]);
              return DoublePoint(x, y);
            },

[monsieurtanuki]

@josxha For the record I've just tried to replace (double, double) methods with Offset in class Crs (which eventually impacted a dozen of classes).
I cannot say that there was that much impact on performances using Offset instead of (double, double), in a first approach, using the "Polyline Stress Test" in profile mode (raster then UI, in ms):

x	old solid algo	new solid algo
offset	203.4 + 43.6	556.2 + 54.6
(double, double)	206.2 + 42.1	578.9 + 53.2

For next tests:

• profile mode
• "Polyline Stress Test"
• zoom 5 times around "Valence, France"
• slider to the left

Something like that:

[JaffaKetchup]

I will say that I don't think this is top priority. This is quite a level of micro-optimization!

[mootw]

@josxha @monsieurtanuki quick update on this. I have been doing some numbers optimizations for another rendering project using FM and drawing verts. Here are a few things i have found that using the

The math Point class is much slower (2-3x in my testing) than the Offset class which is fixed to the double type.

I actually looked at swapping out all of the references to Point in FM to Offset, and it affects many classes but it should be doable, and would lead to noticeable improvements in performance, especially in slow areas.

Avoid creating new objects, always reuse objects if possible.

Record/destructuring response from the project method is significantly faster than the Offset return type, ONLY if i do not re-create more Offset objects after handling projection.

Writing/reading things to fixed size lists is insanely fast, easily 10x faster than Linked List types.

I am able to render easily in under 16ms well over 50k projected triangles with unique colors per frame using DrawVertsRaw and these tricks above!

I believe that implementing fixed size lists, using the destructuring/record type for offsets and removing offsets from the last 0-2 steps of rendering (depending on where it is appropriate) will lead to significant improvements in render time for the most expensive layers like polygons and polylines. Storing a Float32List for all positions is significantly faster than a List of Offsets.

[monsieurtanuki]

@mootw If relevant, we could even create our own MyPoint class. We somehow currently do so, with DoublePoint, don't we?
As I started coding in the 80's I can have surprising ideas regarding optimization, like storing 2 floats inside a single 64-bit integer. Especially given the level of "floatitude" that we probably need here (I mean, pixels). Tell me if you're interested.

About fixed-length lists, it does look promising, but there may be problems with memory (as I assume they allocate a single consecutive space that needs to be "big enough", like an array, TBC). What happens when we add an item: does it rebuild the whole array?

[mootw]

You cannot add items to fixed length arrays! So they aren't always the best solution. I have found they are best for storing and transforming a final list of points. Like, for instance, we take the origin point of the map and the list of projected points, iterating over that list, modifying, and allocating it, is going to be way faster than using a linked list. But a fixed size list likely will end up slower than a Linked list if you're constantly re-allocating it. Even if you use a separate length pointer, and allocate a fixed "largest possible size". I did a test implementation of one of the polyline simplifier functions (radial dist), using fixed size arrays), and it costs more than using the linked list in my testing with about 500,000 points, and a fairly large simplification factor, because we are "wasting" most of the reserved memory space. But in that case for a low simplification factor the cost is SIGNIFICANTLY less for the same function.

Example:

const int size = 500000;
const int seed = 1234;
const LatLng start = LatLng(44.861294, 13.845086);
const double sqTolerance = 0.1;

ending points: 159
simplifyDouglasPeucker: 4.175 ms
simplifyRadialDist: 2.736 ms
simplifyRadialDistFast: 6.778 ms

const double sqTolerance = 0.0;

ending points: 500,000
simplifyDouglasPeucker: 59.423 ms
simplifyRadialDist: 11.667 ms
simplifyRadialDistFast: 5.855 ms

You can see that the Fast implementation is basically fixed time because iterating and modifying the fixed length list is so much faster than the linked list. However, there is a fixed cost of allocating the list (in this example its about 0.2ms), and since this function may result in a smaller list, it also needs to do a new list copy at the end to generate the sub list of final points, which i assume has a slightly larger cost but have not measured it. Not entirely sure why the old implementation is still much faster, i figured it would be about equal worst case even with the fixed cost overhead, but i could just be missing something with my implementation, or the compiler is just smarter than me. But this also is a non-ideal spot to use a fixed length list because it is literally about generating a list of points that is much smaller than the source list. it would make sense if we start using it at the rendering level to store points for pass-through and for iterating and adding a fixed offset to the projection for instance when panning the map. Also internally, flutters renderer uses the fixed size lists. So when you pass down lists in the render chain there is ALWAYS eventually a function that iterates it to a fixed size list that gets copied over to the low level rendering engine/shader. Generally though, there is not really much harm in using a DoublePoint (aka Offset or LatLng) they all serve the same purpose, and as far as rendering goes, they are nearly as fast to access in most cases and easier to read for the programmer. It's only really helpful for big expensive functions, and when we get closer to the renderer. For example, if we implement a Polygons.raw method that passes through a Float32List of points down the render chain, we could potentially avoid some of the optimization tricks and caching because the fixed size lists are just that much faster to read/write to.

These techniques are i would argue BETTER than doing bit-packing or other weird language tricks and other stuff like that. (2 float 32s in a float64 for instance). Generally optimization like that should be handled by the compiler in my opinion, because the way we would do it would certainly be worse in some edge case. But something like using a fixed size list is a real optimization that has certain places where it can show its strengths and really make a difference because fundamentally its different than a linked list (also see HashMap vs Map).

[josxha]

Thanks a lot for all the investigation @mootw!

The math Point class is much slower (2-3x in my testing) than the Offset class which is fixed to the double type.
I actually looked at swapping out all of the references to Point in FM to Offset, and it affects many classes but it should be doable, and would lead to noticeable improvements in performance, especially in slow areas.

I am a huge fan of removing math.Point in favor of something better, too. It would be sad if we throw all the simplification out. However, if an improved memory usage is better than we currently have with the simplification, it might be worth to roll with that.

Storing a Float32List for all positions is significantly faster than a List of Offsets.

Those typed_data types would fit great to accieve this goal, too:

Avoid creating new objects, always reuse objects if possible.

typed_data lists allow to update in-place. In fact, wouldn't we even achieve 1 instead of N objects?

Writing/reading things to fixed size lists is insanely fast, easily 10x faster than Linked List types.

That's awesome! And as you said, especially for drawVertices we need it in this format in the end anyways.