Re: [gtkmm] Custom TreeStore Problems

[Christer Palm <palm nogui se>]

Murray Cumming Comneon com wrote:
> In this case, I am not convinced that enough research has been done to fix
> the original performance problem. People don't seem to have this problem
> with GTK+, and Daniel didn't seem to have this problem with gtkmm in
> regexxer. If someone can show that it's a gtkmm-specific problem then I
> would like to investigate that.

I performed some simple comparisons between GTK+ and gtkmm ListStore 
performance, and came up with the following numbers (this is on a 2.4GHz 
P4):

           append (ms)
---------------------------------
rows       100    1k   10k   100k
GTK+       1.3    12   120    170
gtkmm      4.4    39   390    900


          traverse (ms)
---------------------------------
rows       100    1k   10k   100k
GTK+      .050  .35   3.2    33
gtkmm      .15   1.1    11   101


So it appears that both scale similarly and roughly linearly, but that 
gtkmm consistently has a ~4x overhead on append and ~3x overhead on 
traverse. So judging from those, admittedly rather naïve, measurements, 
it appears that it migh not be a gtkmm-specific problem other than that 
the overhead would cause exponential-time operations to become 
unacceptable much earlier in gtkmm compared to GTK+.

The TreeIter is a forward-only iterator and the TreePath operations, 
although having a random-access interface, are internally implemented 
using g_slist_nth(), which is linear time. Sort will thus essentially be 
exponential time.

That's pretty bad, because sort is a basic functionality of a TreeView, 
and because the TreeView itself essentially makes a lot of random 
accesses to its TreeModel. As this is a GTK+ problem rather than a 
gtkmm-problem, I put the GTK+ list on copy.

--
Christer Palm