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 > <[email protected]> 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. > _______________________________________________ clutter-list mailing list [email protected] https://mail.gnome.org/mailman/listinfo/clutter-list
