Performance improvements

[mphe]

This PR salvages #122 and adds some slight additional refactoring by caching vertices and tesselated points. Also implements the code cleanup mentioned in #122.

Notable change: Since points are now computed lazily, but some code needs immediate access to them (like tests), there is now a force_update() function.

It might be useful to call force_update in SS2D_Actions that manipulate points, but not sure if necessary.

[limbonaut]

With these changes, "defer mesh updates" option doesn't seem to work as it used to.

[limbonaut]

I think the issue is due to changed signal not being emitted until action is fully committed, and we are stuck with the old tesselation cache. We just need to make sure that cache is rebuilt when mesh updates are deferred:

diff --git a/addons/rmsmartshape/shapes/shape.gd b/addons/rmsmartshape/shapes/shape.gd
index c504f33..1c02179 100644
--- a/addons/rmsmartshape/shapes/shape.gd
+++ b/addons/rmsmartshape/shapes/shape.gd
@@ -478,6 +478,12 @@ func is_index_in_range(idx: int) -> bool:

 func set_point_position(key: int, pos: Vector2) -> void:
    _points.set_point_position(key, pos)
+   if _points.is_updating():
+       # Note: With deferred updates option, `changed` signal won't be emitted
+       #       until action is fully commited (user has released the mouse button).
+       #       So we need to update the tesselation cache here.
+       _vertex_cache[_points.get_point_index(key)] = pos
+       _cache_tesselation()

 func remove_point(key: int) -> void:

EDIT: Similar issues with editing curve points in and out. Maybe vertex cache should be handled by PointArray? After all, it knows exactly when things change (_changed func) and can invalidate the vertex cache.

[mphe]

Good idea. I'll look into it tomorrow. I guess tesselation cache can also be moved to PointArray.

[limbonaut]

Good idea. I'll look into it tomorrow. I guess tesselation cache can also be moved to PointArray.

Looking at https://github.com/SirRamEsq/SmartShape2D/blob/b585fc7a378fbe68955cb1ab127bc020cbc1c86d/addons/rmsmartshape/shapes/point_array.gd#L334C1-L338C17, we could add points_changed signal and rebuild cache (or both caches) in a handler. And at the same time keep the changed signal for mesh updates. I'd rename it, though -- changed and points_changed are too similar. Maybe changed -> update_finished or something like that.

EDIT: Although emit_changed also updates the inspector. One of these signals should be changed.

[mphe]

I'm currently looking into it. You mean emitting another signal when _updating is true? I don't like that idea because it will produce inconsistent results, as it will only work with code using begin_update() and end_update(). I prefer the approach of having SS2D_Point_Array manage the point cache itself and regenerating it lazily when requested. This is straight forward and works seamlessly in all cases.

[limbonaut]

I'm currently looking into it. You mean emitting another signal when _updating is true? I don't like that idea because it will produce inconsistent results, as it will only work with code using begin_update() and end_update(). I prefer the approach of having SS2D_Point_Array manage the point cache itself and regenerating it lazily when requested. This is straight forward and works seamlessly in all cases.

Oh, I meant a different set of signals: one that notifies when the point array is changed, and another when update_finished. In such setup, update_finished signifies the end of updates to the point array by the plugin code (a series of contextually connected operations) and is used to rebuild the mesh, and changed would be used to invalidate any data that depends on the point array, like tessellation data and the curve. The difference between the two signals is frequency: changed would be emitted any time the point data is changed, and as such could be used for cache invalidation. At this moment, we only have the update_finished signal (I mean it semantically ofc - it is called changed right now). And it's not emitted any time a change happens, but only when a series of such changes are finalized with the end_update() or when begin_update/end_update are not used (in case of simple actions).

And I agree that moving vertex cache into PointArray is a good idea. We only need it because of how the point array data is constructed and how it misaligns with the rest of the code. But I'm not sure if tessellation should belong to that class.

UPDATE: This is what I mean:

diff --git a/addons/rmsmartshape/shapes/point_array.gd b/addons/rmsmartshape/shapes/point_array.gd
index 33375e7..d06e7ff 100644
--- a/addons/rmsmartshape/shapes/point_array.gd
+++ b/addons/rmsmartshape/shapes/point_array.gd
@@ -323,7 +323,7 @@ func end_update() -> bool:
    _updating = false
    _dirty = false
    if was_dirty:
-       emit_changed()
+       update_finished.emit()
    return was_dirty

@@ -332,10 +332,11 @@ func is_updating() -> bool:

 func _changed() -> void:
+   emit_changed()
    if _updating:
        _dirty = true
    else:
-       emit_changed()
+       update_finished.emit()

 ###############
 # CONSTRAINTS #

[mphe]

Ah, I see. That is actually a good idea regardless of the endeavour of this PR, as it provides a better distinction when related code should run.

I noticed _curve also needs to be cached, as it is used for tesselation and other functions. Now there are four options:

1. Cache vertices, curve and tesselation points in PointArray
2. Cache vertices, curve and tesselation points in Shape
3. Cache only vertices in PointArray and the rest in Shape
4. Create a new class (VertexCache, PointProvider, ...) and move all point caching functionality there.

I can see why PointArray should not be responsible for caching curve and tesselation. On the other hand, PointArray also handles curve in/out handles, hence it is not so far-fetched to let it cache the curve and tesselation and provide a central interface for all point related data. Also these three components kinda belong together semantically.

Regarding refactoring discussions we had in Discord about removing the whole point-array-point-key mapping and using a simple list of Point objects instead, it would make sense to cache vertices in PointArray and also provide a `get_vertices()´ function there.

Option 4) would decouple point caching from both Shape and PointArray while keeping the vertices, curve and tesselation together. I find this idea actually quite clean. The more I think about it, I find this option best, as caching lies semantically somewhere between Shape and PointArray.

Regarding option 3) + an update_finished signal, PointArray would handle vertex cache and Shape would handle curve/tesselation cache. Shape would listen for changed signals to invalidate the internal curve/tesselation cache and rebuild it lazily when the data is requested by get_tesselation_points or get_curve(). It also introduces another dirty flag in Shape (something like _points_dirty) that is only related to keeping the point cache up-to-date but not the complete mesh.

I don't particulary like 3) as it distributes computation of tightly related data across two classes. Personally, I'd go for 1) or 4), but I'm open for discussion.

Regardless of which option is chosen, this change requires adapting various places where the tesselation and curve cache is accessed directly.

[limbonaut]

Should also consider the use-case when several shapes share a single PointArray resource. The whole reasoning why we started to rely on the changed signal during 4.x development is partly because we retired the node that was responsible for synchronization of the point data between several shapes. Now you can simply copy and paste the shapes to do that - and they reuse the resource. I think 1) would allow reusing this cached data instead of recalculating it in each shape instance that uses the same point array resource. And 1 and 4 can also be combined, with PointArray handling the requests and delegating the cache calculation to a specialized class (or classes). I don't think we need a VertexCache though - after all, it's just an array of points and is the domain of PointArray class (in code, _vertex_cache is just a plain array of all points in their proper key order).

[mphe]

Ah, good point, then 1) actually sounds most reasonable. For 4), I didn't mean to have a separate class for each type of cache, the names I mentioned were just some examples of how you could name one class that handles all point related caches. I'm not sure whether 1) with 4) combined makes the code actually cleaner or more obscure because then there is another class that essentially implements one function that could easily be integrated into PointArray without making a mess. I will try out and report back when I got something.

[limbonaut]

I gave it a spin, and it all works great - I didn't find any regressions. Aside from a couple of nitpicks above, this PR looks good to me. And thanks for adding the doc comments in various places!

[mphe]

I wasn't completely finished, yet, I'm still working on the update_finished signal but couldn't find the time, yet.

But since we're here already, here are some notes to the changes so far:

• Moved all point related caching to PointArray, including the new tesselation <-> vertex index mapping
• Point cache is now recomputed lazily on access when dirty. As a result, there is now a separation between point cache and edge cache. Point cache is computed in PointArray, edge cache in shape.gd. Point cache is recomputed lazily when dirty, edge cache is recomputed deferred when dirty. That means, code has seamless access to all point related data, while edge data might need a shape.force_update() if the data is required immediately.
• I also deprecated various functions in shape.gd that act as a wrapper to PointArray. IMO this is redundant and respective functions should be called directly on the PointArray object.
• I decided against implementing 4) (for now) because I find it clearer without it. There is not that much additional code related to caching that would be worth extracting into a separate class. An exception is SS2D_TesselationVertexMapping, because it is used directly in a unit test and I wanted to keep it that way (for now). Maybe the caching functionality should be extracted in a separate class in the future to similarily allow better unit testing, but not sure.
• Most of the doc comments are actually taken from respective wrapper functions in shape.gd. I just moved them over to PointArray.

I will try to update in the next few days and fix the mentioned change requests.

[limbonaut]

Ah I see. I thought you were done, since it's not set as a draft. Maybe edge cache can also be lazily computed? Could mark it dirty on a changed signal.

[mphe]

Doesn't make much sense IMO because edges usually need to update every frame to reflect the current state, except when deferred updates are enabled, but that use-case is already handled. There are also not many cases where outside code needs to access the generated edges. Thinking about it, we don't really have edge cache as such. What I meant with edge cache was more like edge data generation, i.e. meshes and collisions.

[mphe]

I have noticed some .duplicate() calls in PointArray and in get_curve().

https://github.com/SirRamEsq/SmartShape2D/blob/b585fc7a378fbe68955cb1ab127bc020cbc1c86d/addons/rmsmartshape/shapes/point_array.gd#L160-L171

https://github.com/SirRamEsq/SmartShape2D/blob/b585fc7a378fbe68955cb1ab127bc020cbc1c86d/addons/rmsmartshape/shapes/shape.gd#L206-L207

Theses are just some examples. There are duplicate()s everywhere in PointArray. I wonder if this is actually necessary. Sometimes those functions are never even used in the project. I can kinda see why a copy would be safer but on the other hand it seems like a needless copy and I would even expect to get the original object in some cases. PointArray even listens for changed signals on each point to make sure they can be safely modified directly. So I think it's safe to remove the duplication and just return the object. What do you think? As for get_curve(), I already removed the duplicate() in the PointArray.get_curve() but kept it in the now deprecated wrapper in shape.gd for compatibility.

[mphe]

Ready for review.

[limbonaut]

There are duplicate()s everywhere in PointArray. I wonder if this is actually necessary. Sometimes those functions are never even used in the project. I can kinda see why a copy would be safer but on the other hand it seems like a needless copy and I would even expect to get the original object in some cases. PointArray even listens for changed signals on each point to make sure they can be safely modified directly. So I think it's safe to remove the duplication and just return the object. What do you think? As for get_curve(), I already removed the duplicate() in the PointArray.get_curve() but kept it in the now deprecated wrapper in shape.gd for compatibility.

Yeah, I think those duplicate() calls can be removed. It's unlikely to cause issues with third-party code, and if a user tempers with those points, they probably expect the changes to apply in the shape state.

[limbonaut]

Retested, and LGTM :+1: And I think you can ditch those dup() calls if you want to.

[mphe]

Done. I removed various duplicate calls and added missing changed-signal-handling of points and vertex properties, now that these can be accessed directly. Also made use of static tying in various places.

I did some quick performance testing comparing editor performance of master with that of 715b35af611d33dd8881d09c32e452ccaef397ed, 22dd79b77060460f760199b07c0e53f8f43dec1e and HEAD. The performance gain is massive with larger shapes. Alone removing all those duplicates improved the performance immensely. There is still more room for optimization, but this PR improved much more than I had expected.

[SirRamEsq]

This is looking really good you guys.

I now remember writing all those duplicate() calls. The thought process was, "I'll do this now to make sure everything works, then I'll put some tests in place and slowly phase out the duplicates" That last part never actually happened :)

I also never really felt the pain of performance myself, because I typically used smaller shapes.

Anyhow, all of this looks like a fantastic improvement. Thanks so much for all the hard work 🙂 Really exciting stuff.

[limbonaut]

Checked the additions, and it LGTM :+1: