Re: Is GTK+ 3.x 2x slower than GTK+ 2.x?

[Oscar Lazzarino <oscar lazzarino i-m3d com>]

On 10/17/2011 07:12 PM, David Nečas wrote:
> On Mon, Oct 17, 2011 at 06:12:37PM +0200, Oscar Lazzarino wrote:
> > On 10/17/2011 11:51 AM, jcupitt gmail com wrote:
> > > On 17 October 2011 10:23, Clemens Eisserer<linuxhippy gmail com>   wrote:
> > > > > I was shocked by the bad performance of the tree list view from the
> > > > > beginning, so much that i'm now back to FOX toolkit.
> > > >
> > > > Yes, the tree list few is probably one of the worst performing pieces
> > > > of code in GTK+.
> > >
> > > I wonder if this could be down to how they are using the widget?
> >
> > Last time I checked, GTK used glib containers in a much "sub-optimal" way.
> >
> > One example of this is the "append_row" method of the tree model which
> > was implemented more or less with a
> >
> > list->insert(new_row, list->size())
> >
> > (I'm writing by memory and using a pseudo c++ syntax)
> >
> > list->size() does a linear scan of the list to find out the list size
> >
> > ...
> >
> > BTW this was on GTK 2.20 (more or less, I don't remember the exact
> > version number and I can't check right now)
>
> That's funny because Gtk{List,Tree}Store has been based on a splay tree
> (publicly available as GSequence from GLib now) since Gtk+ 2.5.x.
>
> So either you are off by some six years and seven releases or the code
> you checked was not Gtk+ source.
>
> Yeti

OK, thank you for pointing that out, when I checked this I was just 
trying to understand why a treeview took more and more time to append 
rows as it grew (I had 30000 rows more or less) so I just looked at

gtk_list_store_append
gtk_list_store_insert
g_sequence_insert_before
g_sequence_get_length

It still looks like g_sequence_get_length starts from the end node and 
climbs back to the root node where it reads n_nodes. So this costs 
log(n) (when the tree is balanced -- or is the end_node actually the 
root node when appending?) and is done three times in a 
gtk_list_store_append call.

So appending n rows costs n*log(n), instead of n. Could be worse, but 
could also be better, considering that the g_sequence has a 
g_sequence_append method...

Incidentally, I found that calling calling gtk_list_store_prepend with 
rows in reverse order is faster than using gtk_list_store_append

Oscar