Re: Why is adding n actors an O(n^2) operation?

[Philipp Emanuel Weidmann <pew worldwidemann com>]

Hi Emmanuele,

thank you for the fast and competent reply.

The sorting of course explains why there would be a quadratic runtime
behavior, and sure enough, replacing "stage.add(new Actor());" with
"stage.insert_child_at_index(new Actor(), -1);" in the example brings a
huge speedup.

Interestingly, however, the runtime still seems to be quadratic (I
increased the number of actors added per cycle from 1000 to 10000 to
better show the effect):

10000 actors: 0.701129s (sqrt: 0.837335)
20000 actors: 2.728694s (sqrt: 1.651876)
30000 actors: 7.393900s (sqrt: 2.719173)
40000 actors: 17.025317s (sqrt: 4.126175)
50000 actors: 32.895560s (sqrt: 5.735465)
60000 actors: 54.371447s (sqrt: 7.373700)
70000 actors: 80.712491s (sqrt: 8.984013)
80000 actors: 111.603155s (sqrt: 10.564239)
90000 actors: 146.789027s (sqrt: 12.115652)
100000 actors: 186.156586s (sqrt: 13.643921)

Any thoughts on why that is?

Best regards
- Philipp




On Thu, 2013-09-12 at 15:24 +0100, Emmanuele Bassi wrote:
> hi;
>
> On 12 September 2013 15:02, Philipp Emanuel Weidmann
> <pew worldwidemann com> wrote:
>
> > consider the following example code (Vala, compile with "valac --pkg
> > clutter-1.0 -X -lm test.vala"):
> >
> > """
> > using Clutter;
> >
> > class ClutterDemo {
> >
> >   public ClutterDemo() {
> >     var stage = Stage.get_default();
> >
> >     var timer = new Timer();
> >     timer.start();
> >
> >     for (int i = 0; i < 20; i++) {
> >       for (int j = 0; j < 1000; j++) {
> >         stage.add(new Actor());
>
> you're using two deprecated methods alongside new style Clutter API. I
> suggest you don't.
>
> first of all, don't use Clutter.Stage.get_default(), but a proper
> stage instance. secondly, use the Clutter.Actor methods to add a child
> to a container, instead of Clutter.Container.add(). the reason why you
> shouldn't use deprecated API is explained below.
>
> > I would like to know both why that is and what, if anything, can be done
> > about it when one wants to add a large number of actors with high
> > performance. AFAICS, the time required for adding an actor to a
> > container should (*in the absence of a layout manager*) have no
> > dependency on what is already in the container.
>
> that's not entirely correct, and in fact it hasn't been the case since
> Clutter 0.1. Clutter.Container.add() on Clutter.Group, for instance,
> always kept the children list sorted by depth, and appended children
> at the end of each depth "bucket". this was a naive way to ensure that
> the paint order could be influenced by the depth property. this API
> reflected the old (or "gtk") style used to implement our scene graph —
> as it deferred the storage and handling of child nodes to each
> container, instead of centralising it into the node class itself.
>
> if you look at the documentation for Clutter.Actor.add_child() says:
>
> """
> This function will take into consideration the "depth" of child, and
> will keep the list of children sorted.
> """
> -- https://developer.gnome.org/clutter/stable/ClutterActor.html#clutter-actor-add-child
>
> this is needed to retain compatibility with Clutter.Container.add(),
> at least until we can break API.
>
> if you want to insert a large number of (possibly already sorted)
> children into a container then I suggest you look at the
> Clutter.Actor.insert_child_*() methods. in particular,
> insert_child_at_index() with an index of 0 will prepend a child in
> constant time, whereas using an index of -1 (or larger than the list
> of children) will append a child in constant time. you can also use
> insert_child_above()/below() in addition with
> get_first_child()/get_last_child() as a sibling; again, those are all
> constant time operations.
>
> ciao,
>  Emmanuele.