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

[Philipp Emanuel Weidmann <pew worldwidemann com>]

Hi,

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());
      }
      message("%i actors: %fs (sqrt: %f)", (i + 1) * 1000,
        timer.elapsed(), Math.sqrt(timer.elapsed()));
    }

    stage.show_all();
  }

}

void main(string[] args) {
  Clutter.init(ref args);
  var demo = new ClutterDemo();
  Clutter.main();
}
"""


On my machine, running the compiled executable produces the following
output:

1000 actors: 0.052761s (sqrt: 0.229698)
2000 actors: 0.191633s (sqrt: 0.437759)
3000 actors: 0.419020s (sqrt: 0.647318)
4000 actors: 0.750280s (sqrt: 0.866187)
5000 actors: 1.208495s (sqrt: 1.099316)
6000 actors: 1.827580s (sqrt: 1.351881)
7000 actors: 2.639493s (sqrt: 1.624652)
8000 actors: 3.654376s (sqrt: 1.911642)
9000 actors: 4.873089s (sqrt: 2.207508)
10000 actors: 6.291624s (sqrt: 2.508311)
11000 actors: 7.905477s (sqrt: 2.811668)
12000 actors: 9.771812s (sqrt: 3.125990)
13000 actors: 11.828624s (sqrt: 3.439277)
14000 actors: 14.042808s (sqrt: 3.747373)
15000 actors: 16.526229s (sqrt: 4.065246)
16000 actors: 19.134462s (sqrt: 4.374296)
17000 actors: 21.943761s (sqrt: 4.684417)
18000 actors: 24.880892s (sqrt: 4.988075)
19000 actors: 27.985830s (sqrt: 5.290164)
20000 actors: 31.321303s (sqrt: 5.596544)


Note that adding the first 1000 actors to the stage takes only 0.05
seconds, but adding 1000 actors when there are already 19000 present
takes more than 3 seconds.

It is clear that there is some sort of non-linear relationship going on.
As shown in the above output, the square root of the time it takes to
add n actors to the stage is approximately a linear function in n,
indicating that adding n actors is an O(n^2) operation.


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.

Thanks in advance & best regards
- Philipp