Re: ideas on improving the performance of gtk_tree_view

[Federico Mena Quintero <federico ximian com>]

El jue, 22-03-2007 a las 16:55 +0100, Nicolas Setton escribi�Hi, Nicolas,

Thanks for taking the time to profile this!

> Consider the subprogram attached. It shows a simple tree_view  
> displaying a list_store (5000 columns and 50 rows containing  
> integers). The display performance is very poor: when displaying the  
> last columns, the vertical scollbar takes between 5 and 10 seconds to  
> respond.

Two things:

1. Yes, we abuse lists here and there.  The performance would definitely
be better with an array.  This is reasonably easy to do, since the
changes are internal and self-contained in GtkListStore and
GtkTreeDataList.

2. You just created a user interface disaster :)  How are your users
going to be able to jump to the right column?

> So, it seems that we spend most of our time traversing the list of  
> columns. Note that this explains why a tree of 5000 columns x 50 rows  
> has such bad performance compared to a tree of 50 columns x 5000 rows.
> 
> First suggestion: we'd be better off in this subprogram if the data  
> was implemented as an array instead of as a linked list.

Exactly.  GtkListStore is implemented as a GSequence (a splay tree),
where each node is one row in the list.  Then, the data for the row's
columns is stored in a linked list (GtkTreeDataList).  You could
reimplement GtkTreeDataList in terms of an array and get a good speedup
for *all* uses of GtkListStore (i.e. you'd be replacing a dominant
O(n^2) for get/set operations in the list store with a simpler O(log n)
for splay tree lookups, plus the constant time to access a column within
a node).

Using an array instead of a linked list for GtkTreeDataList is a great
idea, and we should definitely review a patch for that :)

> I'm not familiar with this area yet, so I'm puzzled: is the call to  
> gtk_tree_view_column_cell_set_cell_data really needed for the  
> purposes of gtk_tree_view_bin_expose, or is it just needed for the  
> call to gtk_tree_view_has_special_cell?
> 
> In any case, I suggest we cache this - probably there is no need to  
> do it in every expose call, only after the model data has changed.

It absolutely needs to be called for each row, so that the tree view can
know how to display the focus rectangle (a cell-wide rectangle for
editable/activatable cells, a row-wide rectangle for "cold" cells).

The has_special_cell condition is particular to each row, so the
benefits of caching it (say, in the GtkRBTree) would only serve for
multiple exposes of the same unchanging data.  But since one needs to
walk the entire row to paint it, anyway, you'd simply be doing one walk
instead of two.  But the main problem is getting the cell's data from
the model (i.e. walking the GtkTreeDataList) - fix that, and the problem
with has_special_cell may simply disappear.

Hacking GtkListStore/GtkTreeDataList to use an array for the row data
should take one or two afternoons, and it would benefit all trees, not
just your huge one.  Wanna do it for fame and glory? :)

[This would also save memory, since you avoid having GSlice-induced
padding in each GtkTreeDataList structure and you also save a pointer
per node.  I'd love to see actual numbers for this.]

  Federico