Mobject.get_family() as a possible bottleneck

[leotrs]

The problem

As far as I can tell reading the codebase is that mobject's "family" is comprised of itself, its submobjects, and all of it's submobjects' submobjects, recursively. The method Mobject.get_family() is called by family_members_with_points, which is in turn called by shift, which is called by center, align_to, move_to, set_coord, and more. So get_family is called basically every time that you move a mobject.

There are two main issues with this. One is that get_family is called for each submobject, each of those submobjects' submobjects, and so on. So if a scene has a lot of nested mobjects, each single call to get_family (i.e. each time you move a mobject) there will be a lot of overhead just for getting a mobject's family. Remember python is not great at stacking a ton of function calls, and it's particularly bad at recursion (efficiency-wise). Not only that, but then the list of submobjects (and mobjects' submobjects,...) has to be processed with remove_list_redundancies to avoid duplication. More overhead.

This situation won't be a problem in every single scene, but it suffices for you to have a single group of fairly complicated mobjects for this to start becoming a nuisance.

The current situation

Currently, the codebase needs to do this in order to avoid duplication. Say you have a VGroup that contains two mobjects A and B. The mobject A has two submobjects: A' and C. The mobject B has two submobjects: B' and C. Note both A and B contain C. What happens if you want to move the VGroup? You can't just tell both A and B to move because they will each tell their submobjects A', C, B', C to move. So C will move twice. This is bad. You can't compute the family once and then store it because each mobject may change in time and you may miss one submobject down the road. This is bad.

So the current situation solves this by calling get_family, getting rid of the redundancies, and moving each mobject only once. That's great, but far from efficient. Finally, the list returned by get_family must be kept in order. This is done to keep the on screen rendering order correct.

The proposal

It'd be great to have a way to

1. reach each of the mobjects in a mobject's family only once
2. dynamically, since we need to keep track of which objects are added/removed/destroyed/etc
3. maintaining the rendering order
4. doing all of this efficiently. Or at least not computing the family recursively at each call

My proposal is to do this with a signal handling system. (These go by different names: hooks, signals, events, callbacks, pub/sub, observer/listener, etc). But the main idea is the same. Essentially, I'm proposing roughly following:

class Mobject:
    ...
    def add(self, mob):
        self.submobjects.append(mob)                    # keep track of who are my submobjects
        register_callback(self.shift, mob.shift)        # force my submobjects to listen to my movements

    def shift(self, vector):
        # move the coordinates of this mobject
        # nothing else needs to be done, as each submobject's callbacks will do the rest 

So, whenever a new submobject is added, its shift method will be forced to execute whenever the parent's shift method is executed. This is achieved by the refister_callback function. Let's see what it does to the requirements above:

1. reach each of the mobjects in a mobject's family only once: the register_callback function can store the callbacks in an underlying data structure that doesn't allow for repetition, for example a set. In this way, even if a single mobject's method is registered twice, it will only be called once.

2. dynamic: this is dynamic by definition because every time you add or remove (not shown above) a submobject, you will immediately register (or de-register) the callback. So there is no way to miss any of the elements in a family (even with deep nesting since each submobject will trigger the callback of its submobjects and so on and so forth...)

3. maintaining the rendering order: honestly, I'm not sure this is necessary anymore since we are trying to make use of z-order. At least it's not necessary to keep order when moving a mobject and its family. It is necessary when adding/removing or fading in/out, etc. So if we decided we want to do this, the register_callback may use an OrderedSet structure and that's it. There's no more need for remove_list_redundancies. Another more complicated alternative is to use a priority queue (instead of an OrderedSet) where the priority values are given by the z-order. In this case the actual order will never matter anymore so we don't have to keep track of which mobject was added first or last.

4. doing all of this efficiently: implementing this system will reduce shift to literally just changing a mobject's coordinates and then propagating this through callbacks. All of the overhead of recursively calling get_family and then using remove_list_redundancies is totally gone. Most of this overhead is moved to the handling of callbacks made by register_callback, but if we use a clever data structure such as an OrderedSet or priority queue, all of this will be far more efficient than now.

I believe that making such a change will benefit all scenes, not only those with deep nesting. At least, if nothing else, the codebase will be a lot easier to read and debug. Also, note this doesn't change the public API at all, so this should be 100% backwards compatible as well.

Please your thoughts @ManimCommunity/core

[yoshiask]

When I read the problem, I also thought of using an event/callback. I think that's a great solution. If necessary, maybe we should also associate each animation call with a unique ID, so that objects can choose to ignore animation calls they've already done.

[eulertour]

If you do handle it this way you'll also have to ensure that transformations that behave differently for children are handled correctly. For example if G contained M1 and M2 then G.rotate(PI) should rotate M1 and M2 around the center of G rather than rotate each one about their own centers.

[leotrs]

Both good points. I think both points can be solved by adding the appropriate arguments to each callback. For example, the callback could receive an argument that is a reference to the parent mobject. So a child mobject will know what to rotate around.

[leotrs]

Also, note that the updaters framework are basically already a (very rudimentary) version of a callback system. So if we ever implement the proposal here then we can also move updaters to the same system.

[yoshiask]

That's a good idea, are you going to create a new issue for that?

[leotrs]

Let's try to reach consensus here first, but yes I will definitely keep it in mind. Also, changing how updaters work is related to #321