Skip to content
This repository was archived by the owner on Feb 25, 2025. It is now read-only.

Conversation

@jonahwilliams
Copy link
Contributor

@jonahwilliams jonahwilliams commented Feb 6, 2024

Attempts to reduce the allocation overhead of the stroke geometry generator, while also making it easier to debug and profile. Reverts the change to make PathBuilder::TakePath not move the path data, as this was regressing performance.

  • removes dynamic std::vector from cubic to linear component evaluation.
  • removes copy from path positions to UVs for texture filled paths
  • removes almost all stateful lambdas. Instead there is now a statefull interface that generates the vertices. Stack traces now have useful names.
  • Cap/Join procs are now static functions.

Fixes flutter/flutter#142873

@jonahwilliams
Copy link
Contributor Author

alignment * dir;

VS::PerVertexData vtx;
CubicPathComponent(start_offset, start_handle, middle_handle, middle)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We talked about this offline - should we have some specialized codepath for this since we know we're trying to approximate a circle? If not for this patch, for a follow up bug?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

std::vector<Point> TessellateConvex(const Path& path, Scalar tolerance);

//----------------------------------------------------------------------------
/// @brief Create a temporary polyline. Only one can exist at a time.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Per thread? Per process?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Per process, tessellator.h is not thread safe.


~Data() = default;

Data Clone() const;
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Document this - what's getting copied, is it copy on write, etc.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Everything - Done

Copy link
Contributor

@dnfield dnfield left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mostly LGTM, please add some more documentation/clarification

@jonahwilliams jonahwilliams requested a review from dnfield February 6, 2024 22:03
@flar
Copy link
Contributor

flar commented Feb 7, 2024

I prefer to see fixes for different issues separated into different PRs. The issue with the overhead of PathBuilder cloning is unrelated to the issue of the efficiency of the stroked join code. Separation means that further work in one area is not complicated by any potential reverts to fix the other areas.

@jonahwilliams
Copy link
Contributor Author

Sure, I can split that out into a new PR.

@jonahwilliams
Copy link
Contributor Author

Done here: #50444

@jonahwilliams
Copy link
Contributor Author

no, but you do review code.

@jonahwilliams
Copy link
Contributor Author

@gaaclarke would probably be a better reviewer :)

Point forward(offset.y, -offset.x);
Point forward_normal = forward.Normalize();

CubicPathComponent arc;
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Look at the line_geometry.cc which does round caps using direct tessellation.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It looks like the EllipticalVertexGenerator would do what I want. Does that generate two full circles for the each center? I think to incorporate it with the existing triangle strip I'd need to do one at a time.

Copy link
Contributor

@flar flar Feb 8, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That class is a very thin veil over the generator proc. The generator procs get a list of trig values (sin/cos) spaced reasonably for a circle of a given radius. The trig arrays are basically a single quarter circle quadrant of a full circle and they are iterated in various ways 4 times over to produce zig-zag triangle strips. They are the raw trig values so you still need to multiply by the distance (and potentially the direction) - the thing that varies based on the pixel size is how many of them to produce.

The GenerateRoundCapLine proc is close to what we need since it generates the quadrants at an angle based on a direction vector and breaks it down into 2 vectors - one along the line and one across the line both sized by the stroke width. But it generates a triangle strip instead of a poly-line so it's mostly a matter of the order in which the trigs are iterated and multiplied by the along and across vectors. The (triangle) vertices for a single line segment start at the very outward end of the round cap (the top of the semicircle) and zig zag down it until they meet the base of the cap (which is where a butt cap would just cut across) - it then does the reverse on the far round cap since it is responsible for both ends of a drawLine and the jump from one cap to the other naturally covers the body of the line segment itself.

For path tracing you only deal with one round cap at a time and since you are generating polylines instead of triangle strips you would need to iterate in a different order - basically start at the base of the semi-circle and run up one side and then down the other - iterating the trigs twice and moving along the semi-circle instead of zig-zagging down it from the top.

A couple of tricks - the symmetry of the sin/cos values means that whether you are going from 0 to 90 degrees or 90 to 0 degrees you can iterator forward over the array and just swap the sin/cos values. So, flipping from going up one side of the semicircle and then down the other side would just involve iterating forward over the trigs twice, once using cos/sin and the second time swapping to use sin/cos and changing the sign of whether the across vector is added or subtracted from the segment endpoint.

Since this will be the first (potentially only) generator proc that produces a polyline instead of a triangle strip we should probably make that clear in the name(s).

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

While we do generate a polyline for the stroke, that doesn't include the caps/joins, those are appended as triangle strips as we process the polyline.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah, then it gets even easier. It's more a matter of only generating half of the circle than switching the vertex ordering - for the caps. The joins would still require computing the correct subset of the trigs to use which is something none of the current generators try to do.

static StrokePathGeometry::CapProc GetCapProc(Cap stroke_cap);
static StrokePathGeometry::CapProc GetCapProc(Cap cap);

static void CreateButtCap(VertexWriter& vtx_builder,
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm a bit confused - these don't seem to be used in this PR, is there a reason they were added to the headers?

(these = all the static void CreateXCap methods)

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

They are used, see https://github.com/flutter/engine/pull/50379/files#diff-c75818e02ee25c31e8f8a6d5cac9a4f80b33edf3066d39104cd805268310625dR267

Previous this used to pass around closures, but I updated these to be static functions, since that is what they are anyway.

Copy link
Member

@gaaclarke gaaclarke left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mostly LGTM, mostly just style and minor feedback. The most important things are:

  1. Investigate using compile-time polymorphism instead of runtime polymorphism
  2. Remove the raw pointer and pass it into the Generate method
  3. Switch the struct to a class
  4. Adding a return type to ComputeOffset

join_proc(p_join_proc),
cap_proc(p_cap_proc),
scale(p_scale),
vtx_builder(p_vtx_builder) {}
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Here you are storing a raw pointer to vtx_builder, can you instead pass this in as an argument to Generate?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Since this is an private class I think we can maintain this invaraint?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's kind of leaving a footgun in the code, seems like an easy change to remove it unless I'm missing something.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

How is it a footgun?

Copy link
Member

@gaaclarke gaaclarke Feb 8, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Here's the official stance of the c++ style guide: https://google.github.io/styleguide/cppguide.html#Ownership_and_Smart_Pointers

This particular case is a grey area. You have a non-owning raw pointer which is at risk of becoming a dangling pointer.

Here's one example where it can go wrong:

class Foo {
public:
  void good();
  Bar bad();
};

class Bar {
public:
  Bar(Foo& foo) : foo_(foo) {}
  Foo& foo_;
};

void Foo::good() {
  Bar bar(*this);
}

Bar Foo::bad() {
  return Bar(*this);
}

You can imagine a few other ways this can go wrong. We can try to avoid them, but that's why it's a foot gun and not a error. There is no compile-time guarantee that you won't introduce a dangling pointer and that's of the intent of ownership section.

If you remove the field that is storing a raw pointer you remove the risk that it can become a dangling pointer.

At a bare minimum, any C++ class that has a raw pointer should define copy constructors which would remove many of the cases where you'd get dangling pointers. I think just removing the field is easier option though.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

My read of both of those is to be careful with functions that return references, if the lifetime is potentially too short. but in this case I'm not returning a reference, I'm using the class as a storage for a reference.

Happy to make it non-moveable and copyable though.

Copy link
Member

@gaaclarke gaaclarke Feb 8, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

My read of both of those is to be careful with functions that return references,

The key text is "Avoid defining functions that require a const reference parameter to outlive the call". The internal version is "Avoid defining functions that require a reference parameter to outlive the call." That's what we have here with the constructor. I'm happy to deviate from the style guide if we have a valid reason.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The reference already outlives the call, and is used in a class as is. Its equivalent to closing over a non-const reference, which we do all the time. I'd argue that is actually less safe, since I could more easily call the closure in a scope where the reference had been destructed.

At any rate, it turns out its trivial to just pass the reference in so I've made this change.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

C++ style guide has guidance for lambda too: "Use default capture by reference ([&]) only when the lifetime of the lambda is obviously shorter than any potential captures."

I don't know if it is ever truly obvious in c++ haha.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah I feel like this is a case where the class holding the reference has a more obvious lifetime than the closures, but perhaps you could say that the closures we had didn't follow the style guide anyway?

Copy link
Member

@gaaclarke gaaclarke left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

lgtm! thanks

@jonahwilliams jonahwilliams added the autosubmit Merge PR when tree becomes green via auto submit App label Feb 9, 2024
@auto-submit auto-submit bot merged commit fc147a1 into flutter:main Feb 9, 2024
@jonahwilliams jonahwilliams deleted the path_preallocation branch February 9, 2024 18:37
@gaaclarke
Copy link
Member

I was just looking through this again. I just realized that you introduced new symbols that don't exist in headers. Those should have been placed in anonymous namespaces to avoid collisions. It's not a huge deal. I'll fix it up real quick and see if I can swap out the runtime polymorphism for you at the same time.

@jonahwilliams
Copy link
Contributor Author

Oh, they could collide if we introduced similar public names?

@gaaclarke
Copy link
Member

Yep, anything that doesn't have a definition in a header should be in an anonymous namespace.

namespace impeller {
namespace {
  class PositionWriter : public VertexWriter {...};
} // namespace
} // namespace impeller

@jonahwilliams
Copy link
Contributor Author

Damn this language is trying to kill me

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Feb 9, 2024
engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Feb 9, 2024
gaaclarke added a commit that referenced this pull request Feb 9, 2024
…hism (#50506)

followup to #50379

improvements:
1) Symbols in cc are now in anonymous namespaces
1) The header is smaller (limits recompilation time)
1) Removed runtime polymorphism (faster, yay)

## Pre-launch Checklist

- [x] I read the [Contributor Guide] and followed the process outlined
there for submitting PRs.
- [x] I read the [Tree Hygiene] wiki page, which explains my
responsibilities.
- [x] I read and followed the [Flutter Style Guide] and the [C++,
Objective-C, Java style guides].
- [ ] I listed at least one issue that this PR fixes in the description
above.
- [x] I added new tests to check the change I am making or feature I am
adding, or the PR is [test-exempt]. See [testing the engine] for
instructions on writing and running engine tests.
- [x] I updated/added relevant documentation (doc comments with `///`).
- [x] I signed the [CLA].
- [x] All existing and new tests are passing.

If you need help, consider asking for advice on the #hackers-new channel
on [Discord].

<!-- Links -->
[Contributor Guide]:
https://github.com/flutter/flutter/wiki/Tree-hygiene#overview
[Tree Hygiene]: https://github.com/flutter/flutter/wiki/Tree-hygiene
[test-exempt]:
https://github.com/flutter/flutter/wiki/Tree-hygiene#tests
[Flutter Style Guide]:
https://github.com/flutter/flutter/wiki/Style-guide-for-Flutter-repo
[C++, Objective-C, Java style guides]:
https://github.com/flutter/engine/blob/main/CONTRIBUTING.md#style
[testing the engine]:
https://github.com/flutter/flutter/wiki/Testing-the-engine
[CLA]: https://cla.developers.google.com/
[flutter/tests]: https://github.com/flutter/tests
[breaking change policy]:
https://github.com/flutter/flutter/wiki/Tree-hygiene#handling-breaking-changes
[Discord]: https://github.com/flutter/flutter/wiki/Chat
engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Feb 9, 2024
auto-submit bot pushed a commit to flutter/flutter that referenced this pull request Feb 9, 2024
…143251)

flutter/engine@8c521eb...6a3b021

2024-02-09 [email protected] [Impeller] cleaned up StrokePathGeometry and removed runtime polymorphism (flutter/engine#50506)
2024-02-09 [email protected] [web] Fix HtmlViewEmbedder.dispose (flutter/engine#50482)
2024-02-09 [email protected] Roll Dart SDK from 03130d49f214 to 444f7a422da4 (6 revisions) (flutter/engine#50502)
2024-02-09 [email protected] [Impeller] improve performance of polyline and stroke generation by reducing allocation and lambda usage. (flutter/engine#50379)

If this roll has caused a breakage, revert this CL and stop the roller
using the controls here:
https://autoroll.skia.org/r/flutter-engine-flutter-autoroll
Please CC [email protected],[email protected],[email protected] on the revert to ensure that a human
is aware of the problem.

To file a bug in Flutter: https://github.com/flutter/flutter/issues/new/choose

To report a problem with the AutoRoller itself, please file a bug:
https://issues.skia.org/issues/new?component=1389291&template=1850622

Documentation for the AutoRoller is here:
https://skia.googlesource.com/buildbot/+doc/main/autoroll/README.md
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

autosubmit Merge PR when tree becomes green via auto submit App e: impeller

Projects

None yet

Development

Successfully merging this pull request may close these issues.

[Impeller] Cacheable paths adds overhead when paths are unstable.

5 participants