Re: ideas on improving the performance of gtk_tree_view
Hi, Lainaus Federico Mena Quintero [EMAIL PROTECTED]: El jue, 29-03-2007 a las 17:43 +0300, [EMAIL PROTECTED] escribió: Using arrays in GtkTreeDataSortHeader doesn't appear to be optimal, because their length is not constant. We would end up to alloc/dealloc/copy sequence when adding new items. From a quick look at the code, the only place where _gtk_tree_data_list_header_new() gets called is from gtk_list_store_set_n_columns(), which is an internal construct-time function. So the number of headers cannot change. Wouldn't it be possible that calling gtk_tree_sortable_set_sort_func with some strange sort_column_id causes _gtk_tree_data_list_set_header to append new items to header list? At least it contains the code to create new items. However, why this step is needed at all for each comparisison!! It's certainly the case that there will be more sort function calls than changes to sort criteria. This would allow us to cache the pointer to active GtkTreeDataSortHeader directly, providing us constant time O(1) access. Or did I miss something? Oh, you are completely right! You could indeed cache the current header and only refresh it when the sort_column_id changes. Who's got a patch burning a hole in their pocket? :) I made my first try :) There is now a new bug in bugzilla to follow the patches related to this matter: http://bugzilla.gnome.org/show_bug.cgi?id=430095 -Markku- ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
El jue, 29-03-2007 a las 17:43 +0300, [EMAIL PROTECTED] escribió: Using arrays in GtkTreeDataSortHeader doesn't appear to be optimal, because their length is not constant. We would end up to alloc/dealloc/copy sequence when adding new items. From a quick look at the code, the only place where _gtk_tree_data_list_header_new() gets called is from gtk_list_store_set_n_columns(), which is an internal construct-time function. So the number of headers cannot change. [Same thing for gtktreesort.c - it only creates the headers when you change the underlying model.] However, why this step is needed at all for each comparisison!! It's certainly the case that there will be more sort function calls than changes to sort criteria. This would allow us to cache the pointer to active GtkTreeDataSortHeader directly, providing us constant time O(1) access. Or did I miss something? Oh, you are completely right! You could indeed cache the current header and only refresh it when the sort_column_id changes. Who's got a patch burning a hole in their pocket? :) Federico ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
Hi, On Mon, 2007-03-26 at 19:06 -0600, Federico Mena Quintero wrote: I was looking at the GtkTreeView code and it looks like there are other places that could get the array treatment. One place in particular was the sorting machinery... GtkListStore also uses a GList of information for the sort headers, and walks the list in g_list_store_compare_func (!). Using arrays in GtkTreeDataSortHeader doesn't appear to be optimal, because their length is not constant. We would end up to alloc/dealloc/copy sequence when adding new items. They are also accessed according to sort_id (which can come from application program and are not neccesarily contiguous). This means that if we would have an ordered vector we could reach O(log n) search time. Yes, it's better than current O(n) one. However, why this step is needed at all for each comparisison!! It's certainly the case that there will be more sort function calls than changes to sort criteria. This would allow us to cache the pointer to active GtkTreeDataSortHeader directly, providing us constant time O(1) access. Or did I miss something? -Markku- ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: Speeding up stroking of dashed rectangles (was: ideas on improving the performance of gtk_tree_view)
What hadn't ever been made clear is if real-world applications were seeing performance problems caused by the dashed stroking. It sounds like maybe you're on to one of those now. To be fair, even though it's a justifiable use, that's an extreme case - with the font I'm using, one tree row is more than one hundred thousand pixels long. if (stroke_style-dash) return CAIRO_INT_STATUS_UNSUPPORTED; After you do that, the results won't be correct, (the focus rectangle will come out solid instead of dashed), but it should give you a feeling of the upper-bound of the performance benefit you could expect from adding dash support to this function, (and also confirm if the dashed stroking is the cause of the problems you're seeing). I commented out the line, and, as expected, the performance becomes good. The response time was divided by about 100! And if so, then yes, the cairo list might be the best place to continue the discussion. In fact, I just decided to pull that list in with this reply. Please feel free to drop gtk-devel-list from future replies if we just keep talking about cairo's dashed stroking code. I've kept gtk-devel-list to inform everyone of the results, since that's one more argument in favor of integrating Markku's patch. I'll also take the opportunity to thank again everyone involved in these productive discussions. This is one healthy community! Carl, see you in the cairo list for the continuation of this :) I'll try submitting a pertinent test for integration in the perf/ suite, and then a tentative implementation of dash support in _cairo_path_fixed_stroke_rectilinear. Nico ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
Nicolas, can you get another profile using Markku's patch?
Most certainly!
A couple of preliminary remarks.
I have observed a startup time increase of between 20% and 30%.
When scrolling, here is what I observed:
- when displaying the selected row, performance is as bad as
before (scrollbars take between 5 and 15 seconds to react)
- when not displaying the selected row, performance is acceptable
(scrollbars take between 0 and 2 seconds to react, and I'm compiling
at -O0)
An interesting point to note is that this seems due to the drawing of
the keyboard input rectangle (the dotted lines rectangle): when I
select a row with the mouse, the interface is snappy, both for
selecting and for scrolling (between 0 and 2 seconds response time),
but when I then change the selected row using Up or Down keys, the
interface takes around 10 seconds to highlight the newly selected row.
Maybe the experts will have an idea why this is so?
Let's have a look at the relevant time profile (line N calls line N+1):
SelfTotal Library Symbol
0.0%73.7% libgtk-x11-2.0.0.dylib gtk_main
0.0%73.7% libglib-2.0.0.dylib g_main_loop_run
0.0%73.7% libglib-2.0.0.dylib g_main_context_iterate
0.0%73.6% libglib-2.0.0.dylib g_main_context_dispatch
0.0%73.6% libglib-2.0.0.dylib g_main_dispatch
0.0%71.8% libglib-2.0.0.dylib g_idle_dispatch
0.0%71.8% libgdk-x11-2.0.0.dylib gdk_threads_dispatch
0.0%71.8% libgdk-x11-2.0.0.dylib gdk_window_update_idle
0.0%71.8% libgdk-x11-2.0.0.dylib gdk_window_process_all_updates
0.0%71.8% libgdk-x11-2.0.0.dylib gdk_window_process_updates_internal
0.0%71.8% libgtk-x11-2.0.0.dylib gtk_main_do_event
0.0%71.8% libgtk-x11-2.0.0.dylib gtk_widget_send_expose
0.0%71.8% libgtk-x11-2.0.0.dylib gtk_widget_event_internal
0.0%71.8% libgobject-2.0.0.dylib g_signal_emit
0.0%71.8% libgobject-2.0.0.dylib g_signal_emit_valist
0.0%71.8% libgobject-2.0.0.dylib signal_emit_unlocked_R
0.0%71.8% libgobject-2.0.0.dylib g_closure_invoke
0.0%71.8% libgobject-2.0.0.dylib g_type_class_meta_marshal
0.0%71.8% libgtk-x11-2.0.0.dylib _gtk_marshal_BOOLEAN__BOXED
0.0%71.8% libgtk-x11-2.0.0.dylib gtk_tree_view_expose
0.1%71.5% libgtk-x11-2.0.0.dylib gtk_tree_view_bin_expose
0.0%67.0% libgtk-x11-2.0.0.dylib gtk_paint_focus
0.0%67.0% libgtk-x11-2.0.0.dylib gtk_default_draw_focus
0.0%67.0% libcairo.2.dylibcairo_stroke
0.0%67.0% libcairo.2.dylibcairo_stroke_preserve
0.0%67.0% libcairo.2.dylib_cairo_gstate_stroke
0.0%67.0% libcairo.2.dylib_cairo_surface_stroke
0.0%67.0% libcairo.2.dylib_cairo_surface_fallback_stroke
0.0%66.9% libcairo.2.dylib_clip_and_composite_trapezoids
0.0%66.8% libcairo.2.dylib_cairo_traps_extract_region
0.0%66.8% libcairo.2.dylib_cairo_pixman_region_union_rect
0.0%66.8% libcairo.2.dylib_cairo_pixman_region_union
9.7%66.7% libcairo.2.dylibpixman_op
A bit of analysis, now. As before the patch, most of the time is
spent in gtk_tree_view_bin_expose.
If we have a closer look at the previous hot spot, here's what we see:
SelfTotal LineCode
4240 /* we *need* to set cell data on all cells before
the
call
4241 * to _has_special_cell, else _has_special_cell()
does
not
4242 * return a correct value.
4243 */
4244 for (list = (rtl ? g_list_last (tree_view-priv-
columns) : g_list_first (tree_view-priv-columns));
4245 list;
12.5% 0.0%4246 list = (rtl ? list-prev : list-next))
4247{
28.1% 0.0%4248 GtkTreeViewColumn *column = list-data;
3.1%5.6%4249 gtk_tree_view_column_cell_set_cell_data
(column,
4250
tree_view-priv-model,
4251
iter,
4252
GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT),
4253
node-children?TRUE:FALSE);
4254}
We spend between 3 and 4% of the time
Re: ideas on improving the performance of gtk_tree_view
2007/3/27, Nicolas Setton [EMAIL PROTECTED]: Nicolas, can you get another profile using Markku's patch? Most certainly! A couple of preliminary remarks. I have observed a startup time increase of between 20% and 30%. When scrolling, here is what I observed: - when displaying the selected row, performance is as bad as before (scrollbars take between 5 and 15 seconds to react) - when not displaying the selected row, performance is acceptable (scrollbars take between 0 and 2 seconds to react, and I'm compiling at -O0) An interesting point to note is that this seems due to the drawing of the keyboard input rectangle (the dotted lines rectangle): when I select a row with the mouse, the interface is snappy, both for selecting and for scrolling (between 0 and 2 seconds response time), but when I then change the selected row using Up or Down keys, the interface takes around 10 seconds to highlight the newly selected row. Maybe the experts will have an idea why this is so? What's your Cairo version? The input focus rectangle has been identified as a performance problem some time ago: http://lists.freedesktop.org/archives/cairo/2006-October/008135.html Another thing we identified at GUADEC is that the dashed stroke for the focus rectangle that GTK+ uses is also a performance problem. This is another case that we should ensure is going through the fast path for whole-pixel regions. though I *think* it has been adressed since. But if you are running 1.4, that would hint that it still is a problem. P.S. The performance-list[1] might be a better place for this discussion... [1] http://mail.gnome.org/mailman/listinfo/performance-list -- Kalle Vahlman, [EMAIL PROTECTED] Powered by http://movial.fi Interesting stuff at http://syslog.movial.fi ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Speeding up stroking of dashed rectangles (was: ideas on improving the performance of gtk_tree_view)
On Tue, 27 Mar 2007 17:50:08 +0200, Nicolas Setton wrote: Interesting, the dashed stroke is exactly what's causing problems - thanks for the pointer! Ah, ... though I *think* it has been adressed since. But if you are running 1.4, that would hint that it still is a problem. There have been great advances in cairo performance lately, unfortunately this one might have been overlooked. I'll investigate further. It hasn't been overlooked, per se. But we know it hasn't been addressed yet. The mention I made of it before, (from GUADEC last year), was with respect to a synthetic benchmark that just drew a single big, focused button over and over again as fast as it could. And that example showed quite clearly that post-cairo GTK+ drew that button much more slowly than pre-cairo GTK+, (and it is definitely the dashed stroke that is causing the problem). What hadn't ever been made clear is if real-world applications were seeing performance problems caused by the dashed stroking. It sounds like maybe you're on to one of those now. Indeed. Just subscribed to that list. In order to avoid confusing everyone, I'll stay on this list for now, and might open future topics on performance-list (or on the cairo list, if I can make myself useful there). I'm on all three of the lists, and I'd be glad to continue the discussion wherever you see fit. Within cairo, for example, there's a custom _cairo_path_fixed_stroke_rectilinear function that would be the ideal place to throw in support for really fast dashing. And I don't think it would even be a huge amount of work to fix that to support the kinds of dashing used in the focus rectangle here. One thing you could do that might be very useful would be to go into that function in cairo and remove the following two lines: if (stroke_style-dash) return CAIRO_INT_STATUS_UNSUPPORTED; After you do that, the results won't be correct, (the focus rectangle will come out solid instead of dashed), but it should give you a feeling of the upper-bound of the performance benefit you could expect from adding dash support to this function, (and also confirm if the dashed stroking is the cause of the problems you're seeing). And if so, then yes, the cairo list might be the best place to continue the discussion. In fact, I just decided to pull that list in with this reply. Please feel free to drop gtk-devel-list from future replies if we just keep talking about cairo's dashed stroking code. -Carl pgpZJ7qQMwjR4.pgp Description: PGP signature ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
El lun, 26-03-2007 a las 00:18 +0300, [EMAIL PROTECTED] escribió: I tried this idea and changed the GtkTreeDataList to be an array instead of linked list (see the attached patch, made against svn head). The original testcase (5000x50 model) started up faster (but was still slow), but I didn't do any actual measurements yet (let's see tomorrow ;) I made the following changes: * Added dimension/index parameter to many GtkTreeDataList calls (I understood that this API was OK to be changed). The GtkTreeDataList is now an array of n elements instead of single list node. * GtkListStore and GtkTreeStore needed similar patches, including: Simpler get_value/set_value implementation, because we know that the datalist will contain n elements and they can be indexed easily. * Drag'n'drop code now uses simpler _gtk_tree_data_list_copy (I renamed _gtk_tree_data_list_node_copy, since we now have more than one element). Holy crap, you kick ass! Nicolas, can you get another profile using Markku's patch? I was looking at the GtkTreeView code and it looks like there are other places that could get the array treatment. One place in particular was the sorting machinery... GtkListStore also uses a GList of information for the sort headers, and walks the list in g_list_store_compare_func (!). Federico ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
Hi,
Lainaus Federico Mena Quintero [EMAIL PROTECTED]:
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 tried this idea and changed the GtkTreeDataList to be an array instead of
linked list (see the attached patch, made against svn head). The original
testcase (5000x50 model) started up faster (but was still slow), but I didn't do
any actual measurements yet (let's see tomorrow ;)
I made the following changes:
* Added dimension/index parameter to many GtkTreeDataList calls (I understood
that this API was OK to be changed). The GtkTreeDataList is now an array of
n elements instead of single list node.
* GtkListStore and GtkTreeStore needed similar patches, including:
Simpler get_value/set_value implementation, because we know that the
datalist will contain n elements and they can be indexed easily.
* Drag'n'drop code now uses simpler _gtk_tree_data_list_copy (I renamed
_gtk_tree_data_list_node_copy, since we now have more than one element).
-Markku-
Index: gtk/gtktreestore.c
===
--- gtk/gtktreestore.c (revision 17562)
+++ gtk/gtktreestore.c (working copy)
@@ -386,8 +386,11 @@
node_free (GNode *node, gpointer data)
{
if (node-data)
-_gtk_tree_data_list_free (node-data, (GType*)data);
- node-data = NULL;
+ {
+GtkTreeStore *store = GTK_TREE_STORE(data);
+_gtk_tree_data_list_free (node-data, store-column_headers, store-n_columns);
+node-data = NULL;
+ }
return FALSE;
}
@@ -398,7 +401,7 @@
GtkTreeStore *tree_store = GTK_TREE_STORE (object);
g_node_traverse (tree_store-root, G_POST_ORDER, G_TRAVERSE_ALL, -1,
- node_free, tree_store-column_headers);
+ node_free, tree_store);
g_node_destroy (tree_store-root);
_gtk_tree_data_list_header_free (tree_store-sort_list);
g_free (tree_store-column_headers);
@@ -557,20 +560,17 @@
{
GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
GtkTreeDataList *list;
- gint tmp_column = column;
g_return_if_fail (column tree_store-n_columns);
g_return_if_fail (VALID_ITER (iter, tree_store));
list = G_NODE (iter-user_data)-data;
- while (tmp_column-- 0 list)
-list = list-next;
-
if (list)
{
_gtk_tree_data_list_node_to_value (list,
tree_store-column_headers[column],
+ column,
value);
}
else
@@ -719,8 +719,6 @@
gboolean sort)
{
GtkTreeDataList *list;
- GtkTreeDataList *prev;
- gint old_column = column;
GValue real_value = {0, };
gboolean converted = FALSE;
gboolean retval = FALSE;
@@ -748,61 +746,23 @@
converted = TRUE;
}
- prev = list = G_NODE (iter-user_data)-data;
-
- while (list != NULL)
+ list = G_NODE (iter-user_data)-data;
+ if (G_UNLIKELY(list == NULL))
{
- if (column == 0)
- {
+ G_NODE (iter-user_data)-data = list =
+ _gtk_tree_data_list_alloc (tree_store-n_columns);
+}
+
if (converted)
- _gtk_tree_data_list_value_to_node (list, real_value);
+ _gtk_tree_data_list_value_to_node (list, column, real_value);
else
- _gtk_tree_data_list_value_to_node (list, value);
+ _gtk_tree_data_list_value_to_node (list, column, value);
retval = TRUE;
if (converted)
g_value_unset (real_value);
if (sort GTK_TREE_STORE_IS_SORTED (tree_store))
-gtk_tree_store_sort_iter_changed (tree_store, iter, old_column, TRUE);
+gtk_tree_store_sort_iter_changed (tree_store, iter, column, TRUE);
return retval;
- }
-
- column--;
- prev = list;
- list = list-next;
-}
-
- if (G_NODE (iter-user_data)-data == NULL)
-{
- G_NODE (iter-user_data)-data = list = _gtk_tree_data_list_alloc ();
- list-next = NULL;
-}
- else
-{
- list = prev-next = _gtk_tree_data_list_alloc ();
- list-next = NULL;
-}
-
- while (column != 0)
-{
- list-next = _gtk_tree_data_list_alloc ();
- list = list-next;
- list-next = NULL;
- column --;
-}
-
- if (converted)
-_gtk_tree_data_list_value_to_node (list, real_value);
- else
-_gtk_tree_data_list_value_to_node (list, value);
-
- retval = TRUE;
- if (converted)
-g_value_unset (real_value);
-
- if (sort GTK_TREE_STORE_IS_SORTED (tree_store))
-gtk_tree_store_sort_iter_changed (tree_store, iter, old_column, TRUE);
-
- return retval;
}
/**
@@
Re: ideas on improving the performance of gtk_tree_view
On Thu, Mar 22, 2007 at 08:18:14PM +0200, Tommi Komulainen wrote: On 3/22/07, Kalle Vahlman [EMAIL PROTECTED] wrote: 2007/3/22, Yevgen Muntyan [EMAIL PROTECTED]: IIRC reusing single cell renderer in multiple columns was declared broken and unsupported (because it was broken). Is this correct? Yes, a single cell renderer is not supposed to be used in multiple columns. Of couse you might get lucky and it works more or less. Maybe there are specific cell renderers that are broken? As I understood it, it is broken if you do not set the same set of attributes on each column. Try mapping text and font weight on one column, and just text on another column and see what happens ;-) That's one really good example of how things will break. And you also already provided a way to work around it :) For the record I am not planning on fixing any new bugs which show up because of using a single cell renderer in multiple columns. Maybe we should guard for reusing a cell renderer multiple times in a later version of GTK+. regards, -kris. ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
2007/3/23, Kristian Rietveld [EMAIL PROTECTED]: On Thu, Mar 22, 2007 at 08:18:14PM +0200, Tommi Komulainen wrote: On 3/22/07, Kalle Vahlman [EMAIL PROTECTED] wrote: 2007/3/22, Yevgen Muntyan [EMAIL PROTECTED]: IIRC reusing single cell renderer in multiple columns was declared broken and unsupported (because it was broken). Is this correct? Yes, a single cell renderer is not supposed to be used in multiple columns. Of couse you might get lucky and it works more or less. Maybe there are specific cell renderers that are broken? As I understood it, it is broken if you do not set the same set of attributes on each column. Try mapping text and font weight on one column, and just text on another column and see what happens ;-) That's one really good example of how things will break. And you also already provided a way to work around it :) For the record I am not planning on fixing any new bugs which show up because of using a single cell renderer in multiple columns. Maybe we should guard for reusing a cell renderer multiple times in a later version of GTK+. And at minimum update the docs ASAP to note this. The paragraph I pasted had me at least thinking it doesn't matter at all where the renderer is used... -- Kalle Vahlman, [EMAIL PROTECTED] Powered by http://movial.fi Interesting stuff at http://syslog.movial.fi ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
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
Re: ideas on improving the performance of gtk_tree_view
El vie, 23-03-2007 a las 23:19 +0100, Michael Natterer escribió: I would rather say we absolutely don't abuse lists here. There is no significant difference between list and array for a couple of items (say 50 items). The only abuse I see is creating a treeview with 5000 columns. The widget is simply not made for that. It would be the same as optimizing GtkVBox for 5000 children and asking for the internal list being replaced by an array. So, a few things: * 5000 columns is definitely abusing the *user*. Who cares about the toolkit. * A tree row has an immutable number of columns; their datums are of known sizes. This screams array. * An array would give you less memory overhead from allocator padding, better cache locality, less pressure on the allocator, and constant-time access to the columns. I bet that it will also require less code than a list :) What GTK+ needs here is a *sheet* widget, something that is optimized for organizing two-dimensional data in an efficient way. Hacking up GtkTreeView for insane use cases does no good whatsoever. Yes, we definitely need a sheet widget. I don't know why people don't just write one, or revive the old one. Maybe they are scared that it doesn't do enough for a spreadsheet --- but people are not building spreadsheets; they just want to display simple tabular data. P.S.: I do not say that optimizing treeview is a bad idea, I would just find it very unfortunate to waste developer resources in order to optimize use cases like this. I'd rather not discourage people who are actually bothering to profile our shitty code --- they don't come along very often. Federico ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
On Fri, 2007-03-23 at 17:35 -0600, Federico Mena Quintero wrote: El vie, 23-03-2007 a las 23:19 +0100, Michael Natterer escribió: [...] What GTK+ needs here is a *sheet* widget, something that is optimized for organizing two-dimensional data in an efficient way. Hacking up GtkTreeView for insane use cases does no good whatsoever. Yes, we definitely need a sheet widget. I don't know why people don't just write one, or revive the old one. Maybe they are scared that it doesn't do enough for a spreadsheet --- but people are not building spreadsheets; they just want to display simple tabular data. Such widget was written a while ago by Lorenzo Gil Sánchez (Gazpacho's author): http://www.sicem.biz/personal/lgs/projects/gtkgrid/view_project But the discussion take here when it was proposed, wasn't very stimulating so far: http://mail.gnome.org/archives/gtk-devel-list/2004-April/msg00137.html -- Germán Poó Caamaño Concepción - Chile ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
ideas on improving the performance of gtk_tree_view
This describes an idea to improve the display performance of the
tree_views, based on the sources of gtk+-2.10.11, and suggests
possible solutions.
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.
Preliminary note: a tree of 50 columns and 5000 rows displays better
performance (scrollbars take between 0 and 1 seconds to respond).
Using the Apple Shark profiler gave me the following tree showing
where the time is spent while simply scrolling the scrollbar. In this
tree, line N+1 calls line N.
SelfTotal Library
0.0%80.3% bigtree main
0.0%80.3% libgtk-x11-2.0.0.dylib gtk_main
0.0%80.3% libglib-2.0.0.dylib g_main_loop_run
0.0%80.3% libglib-2.0.0.dylib g_main_context_iterate
0.0%80.3% libglib-2.0.0.dylib g_main_context_dispatch
0.0%80.3% libglib-2.0.0.dylib g_main_dispatch
0.0%79.8% libglib-2.0.0.dylib g_idle_dispatch
0.0%79.8% libgdk-x11-2.0.0.dylib gdk_window_update_idle
0.0%79.8% libgdk-x11-2.0.0.dylib gdk_window_process_all_updates
0.0%79.8% libgdk-x11-2.0.0.dylib
gdk_window_process_updates_internal
0.0%79.8% libgtk-x11-2.0.0.dylib gtk_main_do_event
0.0%79.8% libgtk-x11-2.0.0.dylib gtk_widget_send_expose
0.0%79.8% libgtk-x11-2.0.0.dylib gtk_widget_event_internal
0.0%79.8% libgobject-2.0.0.dylib g_signal_emit
0.0%79.8% libgobject-2.0.0.dylib g_signal_emit_valist
0.0%79.8% libgobject-2.0.0.dylib signal_emit_unlocked_R
0.0%79.8% libgobject-2.0.0.dylib g_closure_invoke
0.0%79.8% libgobject-2.0.0.dylib g_type_class_meta_marshal
0.0%79.8% libgtk-x11-2.0.0.dylib _gtk_marshal_BOOLEAN__BOXED
0.0%79.8% libgtk-x11-2.0.0.dylib gtk_tree_view_expose
0.2%79.6% libgtk-x11-2.0.0.dylib gtk_tree_view_bin_expose
0.4% 26.4% libgtk-x11-2.0.0.dylib
gtk_tree_view_column_cell_set_cell_data
0.0%18.4% libgtk-x11-2.0.0.dylib gtk_tree_model_get_value
17.5% 18.0% libgtk-x11-2.0.0.dylib gtk_list_store_get_value
I have two comments to make about this tree:
A) it seems strange that 18% of the time is spent in
gtk_list_store_get_value.
B) it seems very strange that gtk_tree_view_bin_expose calls
gtk_tree_view_column_cell_set_cell_data.
Investigating further in the direction given by comment A), I saw
that the following lines in gtkliststore.c were consuming the biggest
amount of time:
SelfTotal LineCode
451 static void
452 gtk_list_store_get_value (GtkTreeModel
*tree_model,
453 GtkTreeIter *iter,
454 gint column,
455 GValue *value)
0.0%0.1%456 {
457 GtkListStore *list_store = (GtkListStore *)
tree_model;
458 GtkTreeDataList *list;
459 gint tmp_column = column;
460
0.0%0.0%461 g_return_if_fail (column
list_store-n_columns);
0.0%0.4%462 g_return_if_fail (VALID_ITER (iter,
list_store));
463
0.0%0.4%464 list = _gtk_sequence_ptr_get_data
(iter-user_data);
465
53.2% 51.8% 466 while (tmp_column-- 0 list)
46.5% 45.3% 467 list = list-next;
468
0.0%0.0%469 if (list == NULL)
470 g_value_init (value,
list_store-column_headers[column]);
471 else
0.1%1.9%472 _gtk_tree_data_list_node_to_value (list,
473
list_store-column_headers[column],
474
Re: ideas on improving the performance of gtk_tree_view
2007/3/22, Nicolas Setton [EMAIL PROTECTED]: [snip] 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. Your test program is also creating 4950 cellrenderers more in that case, while the extra rows are for free in that sense (ie. same amount of data items stored, but no extra cellrenderers). See below for more on this. First suggestion: we'd be better off in this subprogram if the data was implemented as an array instead of as a linked list. I guess this could be valid in any case... Let's turn now to comment B). Why is gtk_tree_view_bin_expose calling gtk_tree_view_column_cell_set_cell_data ? [snap] 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? It _is_ really needed for expose, since GtkCellRenderers are not tied to the data it's rendering: The primary use of a GtkCellRenderer is for drawing a certain graphical elements on a GdkDrawable. Typically, one cell renderer is used to draw many cells on the screen. To this extent, it isn't expected that a CellRenderer keep any permanent state around. Instead, any state is set just prior to use using GObjects property system. Then, the cell is measured using gtk_cell_renderer_get_size(). Finally, the cell is rendered in the correct location using gtk_cell_renderer_render(). http://developer.gnome.org/doc/API/2.0/gtk/GtkCellRenderer.html#id3190590 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. ...so it isn't really feasible to cache the renderer state. The good news learned from the above is that if you simply move the renderer creation outside the for loop, you'll get the same functionality but without 4999 extra cellrenderers in memory :) To sum up (thanks for reading me), would you accept a patch along those lines? I let Kris and others comment on the array thing, but it would be interesting to re-measure and see how much the 4999 cellrenderers were affecting the performance (not much I guess, but it should use a fair amount less memory then). Anyway, nice test case to hack on :) -- Kalle Vahlman, [EMAIL PROTECTED] Powered by http://movial.fi Interesting stuff at http://syslog.movial.fi ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
On Thu, Mar 22, 2007 at 04:55:30PM +0100, Nicolas Setton wrote: 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. Preliminary note: a tree of 50 columns and 5000 rows displays better performance (scrollbars take between 0 and 1 seconds to respond). There is a really simple answer to this: GtkTreeView is not a table, it was not designed to handle views like this with 50 columns. First suggestion: we'd be better off in this subprogram if the data was implemented as an array instead of as a linked list. That would only help GtkListStore, other models might need different solutions. There are also multiple places in GtkTreeView which all assume a reasonable amount of columns (I would say 50), I am not sure if all this is worth changing at all. 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? It is needed to make the call to gtk_tree_view_has_special_cell() return a proper and correct result. This correct result is required in order to make the key navigation behave properly. 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. This is something which cannot really be cached, CellDataFuncs can also influence this value, and CellDataFuncs can depend on more data than just the data found in the model. regards, -kris. ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
Kalle Vahlman wrote: 2007/3/22, Nicolas Setton [EMAIL PROTECTED]: [snip] 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. ...so it isn't really feasible to cache the renderer state. The good news learned from the above is that if you simply move the renderer creation outside the for loop, you'll get the same functionality but without 4999 extra cellrenderers in memory :) IIRC reusing single cell renderer in multiple columns was declared broken and unsupported (because it was broken). Is this correct? Yevgen ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
2007/3/22, Yevgen Muntyan [EMAIL PROTECTED]: Kalle Vahlman wrote: 2007/3/22, Nicolas Setton [EMAIL PROTECTED]: [snip] 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. ...so it isn't really feasible to cache the renderer state. The good news learned from the above is that if you simply move the renderer creation outside the for loop, you'll get the same functionality but without 4999 extra cellrenderers in memory :) IIRC reusing single cell renderer in multiple columns was declared broken and unsupported (because it was broken). Is this correct? It worked amazingly well for being broken ;) Maybe there are specific cell renderers that are broken? -- Kalle Vahlman, [EMAIL PROTECTED] Powered by http://movial.fi Interesting stuff at http://syslog.movial.fi ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
On 3/22/07, Kalle Vahlman [EMAIL PROTECTED] wrote: 2007/3/22, Yevgen Muntyan [EMAIL PROTECTED]: IIRC reusing single cell renderer in multiple columns was declared broken and unsupported (because it was broken). Is this correct? It worked amazingly well for being broken ;) Maybe there are specific cell renderers that are broken? As I understood it, it is broken if you do not set the same set of attributes on each column. Try mapping text and font weight on one column, and just text on another column and see what happens ;-) -- Tommi Komulainen [EMAIL PROTECTED] ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: ideas on improving the performance of gtk_tree_view
[Thanks everyone for your answers] There is a really simple answer to this: GtkTreeView is not a table, it was not designed to handle views like this with 50 columns. I'm not sure I understand this part: should I use a gtk_table to display this kind of data? What is the preferred way to display this kind of information (5000 columns x 50 rows) in Gtk+? The GtkTreeView seemed the best approach to me. Moreover, the GtkTreeView 'almost' supports this, so I think it would be a shame to simply throw down our weapons so soon! See below for suggestions. That would only help GtkListStore, other models might need different solutions. There are also multiple places in GtkTreeView which all assume a reasonable amount of columns (I would say 50), I am not sure if all this is worth changing at all. The GtkTreeStore would also benefit from that, but I agree with you, it might not be worth changing. 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? It is needed to make the call to gtk_tree_view_has_special_cell() return a proper and correct result. This correct result is required in order to make the key navigation behave properly. This gives me an idea. Proposal (1): we give the user the possibility (through a property, for instance) to deactivate keyboard navigation, in exchange for an enormous gain of performance for big trees. 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. This is something which cannot really be cached, CellDataFuncs can also influence this value, and CellDataFuncs can depend on more data than just the data found in the model. This gives me another idea, which I think is better than Proposal (1). Proposal (2): we give the user the possibility to tell the tree view that the only way the data will change is through the model. When the tree view is guaranteed this, it executes the loop on gtk_tree_view_column_cell_set_cell_data only once in each model change, and not once in every expose. Note that, when you deactivate this loop, you get very fluid response even for the 5000 columns tree. We're looking at something like 5000% performance increase, and this the kind of users would get from Proposal (1) or Proposal (2). What do you think? Nicolas ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
