Re: Speed of GtkListStore additions O(n^2)?

[Owen Taylor <otaylor redhat com>]

On Tue, 2003-06-03 at 05:07, Linus Walleij wrote:
> I have a serious problem with speed on the GtkListStore widget. Calling
> 
>    gtk_list_store_append ();
>    gtk_list_store_set ();
> 
> multiple times to add, say 2000 rows of various metadata exhibit
> something like a O(n^2) behaviour, whereas the old GtkClist was certainly
> O(n).
> 
> Point is: GtkListStore is unacceptably slow when adding many, many rows.
> (I have a view attached to my list store.)
> 
> Has anyone had direct experience with this before and a quick and obvious
> solution?
> 
> Otherwise I recon I'm the first to use big list stores so I'll have to
> start writing test programs and dig into GTK until I find the flawed
> routine. It cannot be like this.

Insertion in a GtkListStore is *not* in general O(n^2). Some possible
reasons why things might be slow for you:

 - Insertion into a *sorted* GtkListStore is O(n^2). Delaying turning
   on sorting until after the list store is filled will allow GTK+
   to use more efficient sorting algorithms.

 - If you return control to GTK+ and let it recalculate and redraw
   after inserting things will be very slow. O(n) but very slow.

 - If you have columns in your GtkTreeView set 
   to GTK_TREE_VIEW_COLUMN_AUTOSIZE, this makes many operations much
   more expensive. AUTOSIZE should be avoided for large treeviews.

Regards,
                                             Owen