Re: GtkTreeView: inserting rows faster.

[Jonathan Blandford <jrb redhat com>]

Peter Zelezny <pzel dodo com au> writes:

> Hi All,
> 
> I've been trying to improve the performance of inserting new rows
> into a GtkTreeView. The performance is somewhat lacking. I am calling
> gtk_list_store_insert_after(), to try to avoid linear searches through
> existing rows, but it's not having the desired effect.

I would be surprised if that's particularly slow.  Have you done any
timings or profiling?  Also, it is (not surprisingly) slower when you
have a listener such as a GtkTreeView.

> There are two areas where things could probably be improved. I'm not
> all that familiar with gtk's source, so you might want to correct me
> here and there:
> 
> GtkListStore:
> ~~~~~~~~~~~~~
> 
> In gtk_list_store_append_after() there is a loop that could be
> elimintated:

(you mean gtk_list_store_insert_after)

>   for (list = list_store->root; list && list != sibling->user_data; list =
> list->next)
>     i++;
> 
> We'd need to change ListStore to use doubly linked lists, so it would
> take 4 bytes extra memory per row on x86.

This loop exists to find the position of the new row being inserted.
Doing the double-linked list wouldn't help here -- you still need to
walk the tree.

> list_store_append_after() also calls gtk_tree_model_row_inserted, which
> in turn calls gtk_list_store_get_path(). 

gtk_tree_model_row_inserted just emits the signal.

> There's another linear loop here:
> 
>   for (list = G_SLIST (GTK_LIST_STORE (tree_model)->root); list; list =
> list->next)
> 
> gtk_tree_path_append_index is called 2 times at least, that's 2 realloc()s.
> This could probably be optimized too.

I seriously doubt that a realloc here is the slow point.  Also, we won't
realloc in the case of the list as we start with one element in the
path, and never deal with deeper paths than that.

> gtk_tree_row_ref_inserted_callback has another linear loop.

That is a loop to go through all row refs.  We need to visit them all.

> GtkTreeView:
> ~~~~~~~~~~~~
> 
> It redraws even when the newly inserted row is not visible. I havn't
> looked at this code at all yet.

It doesn't.  This code is incredibly complicated, and cannot be
described in a paragraph.  It does measure all rows at some point
(mostly in an idle.)

> That's about I can see that could potentially be improved, from a quick
> scan through the source. I'd like to hear some comments from people more
> familiar with the code.

There is definitely room for speeding up this code, but I don't think
any of these are worthwhile.

> Ideally, it should be possible to insert rows in constant time when
> calling gtk_list_store_insert_(after/before). Is it achievable?

Insert before is not without adding a back pointer.  Also, we need to
know the location of rows when we emit the signal.  This does require
the walking of the list, but I feel this is prolly fast -- especially as
we special case the last row (which is reasonably common.)  We might be
able to do a few more special cases, but I'd really like to make sure
this is slow first.

Thanks,
-Jonathan