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

[Emmanuele Bassi <ebassi gmail com>]

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.

-- 
W: http://www.emmanuelebassi.name
B: http://blogs.gnome.org/ebassi/