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 _______________________________________________ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list