GNOME Bugzilla – Bug 80868
Look into optimizing row validation
Last modified: 2011-02-04 16:12:26 UTC
SSIA.
Moving remaining bugs to 2.2.1.
The current plan is to add a property which disables validation. It will use fixed heights, and fixed columns. I don't see much more rooms for performance improvements than this though, I need to learn to use a profiler soon. I have some concept patches on my harddrive. Once I make a stable once, I will put it out for testing.
Adding property means punting to 2.3.x
*** Bug 99134 has been marked as a duplicate of this bug. ***
*** Bug 71968 has been marked as a duplicate of this bug. ***
*** Bug 94710 has been marked as a duplicate of this bug. ***
Is there any progress being made on speeding up GtkTreeView? I don't have much free time to implement the fixed heights/columns, but if I can help you to do it, or help with testing/debugging, I can swing that. Fifteen months after reporting #71968 I'm still unable to migrate Pan to TreeView because it's literally 22x slower than GtkCTree. How on Earth does this a puntable unassigned normal/normal? :) From the timing comparison programs included with #71968: % pkg-config --modversion gtk+-2.0 2.2.1 % ./time-clist ** Message: clist inserted 30000 rows in 1.3 seconds (23351 rows/sec) % ./time-treeview2 ** Message: gtk_list_store appended 30000 items in 4.7 secs (6403 rows/sec) ** Message: 29.2 seconds until idle
I did some work on a fixed height patch. I think it got lost somewhere after my machine went bad. Need to find it and attach it here. It didn't help all that much though, I think there are more issues. The latest pango HEAD might help (which has improved performance IIRC). Don't count on me too much, I just don't have any profiling skills.
Is there any progress on this one? Is there anything out that could be tested/benchmarked?
No profiling skills are needed. Just create a test list with a million entries in it and have the data provider log every request. The goal should be to only call the data provider for visible cells.
I'm also very interessted in speeding up the GtkTreeView. I use it in synaptic (a gtk frontend for apt). And it take much too long to display all 13.000 debian packages. I use gtk_tree_view_column_set_fixed_width() and gtk_cell_renderer_text_set_fixed_height_from_font() to minimize the amount of computation. But it still takes ~9sec to display the 13.000 packages (6 columns). I build gtk with profiling support and linked synaptic against this version. I can provide the profiling output if someone is interessted. It looks like the bottleneck is do_validate_rows(). Why does it go throught all the rows and columns? As far as I understand the code (I admit that I do not understand it very well) this is done to calc the size of each cell? If we use fixed sizes, this shouldn't be needed?
We know that do_validate_rows is the bottleneck. Currently it goes through all rows/columns because it has to measure them. This is indeed not needed if we use fixed sizes, hence the fixed height patch I was talking about earlier in this bug. I have a concept patch on my hard drive. I will try to rewrite it against HEAD ASAP (shouldn't take long, if I get time). The fixed height patch will definitely make 2.4.
that are really great news. I like the GtkTreeView, the only think that bugs me is that it's not fast enough. So, once there is something to test (even a preliminarily patch), please let me know. Maybe you can even post the concept patch here, so that I can try to help you with it (also I'm not familiar with the gtktreeview code).
Michael, could you try upgrading to glib, pango and gtk+ HEAD and tell me how long it takes with those? The TreeView should be a good bit faster in HEAD.
FYI, these are the numbers I get with cvs HEAD on the benchmarks from #71968: CList: ** Message: clist inserted 30000 rows in 1.0 seconds (29781 rows/sec) TreeView: ** Message: added 30000 rows in 3.4 seconds (8813 rows/sec) So the TreeView is currently 3.4 times slower than CList. Not terribly bad, I'd say (but there's room for improvement of course).
That's good news Soeren! There probably is some more room for improvement (in gobject IIRC, we talked about that on IRC a few months back, but I forgot all details ...). Michael, I can't post the concept patch, since it's old (I think I wrote it in December of last year), doesn't apply anymore and it's broken. I will probably rewrite it somewhere this week, which is something I should be able to do in one afternoon/evening. Writing that patch is basically on top of my todo list now.
blah, ignore those numbers, because a) a lot of the time in both cases is spent in code that only runs once (cache building and such). The benchmark needs to run with more data to say anything useful. b) I had a compilation running. c) I had some extra patches applied The point still stands though: HEAD is substantially faster than stable, and actually I don't see any huge performance problems with it.
Kristian, well I believe I said then that I don't think a programmer-settable "fixed-height" property makes sense, because it is basically a hack that requires more knowledge about the data tahn I think should be necessary. I'd tend to agree with Morten that the TreeView should be able to just assume that everything is fixed height, and only ask the data provider when the tree view is "proven wrong".
I agree that it is a hack, I am also really afraid that people will misuse it. Your second comment is interesting. I have some thoughts right now on how to implement it (I will think about it more on the train tomorrow ;), I will give that a try first this week. If that doesn't help enough, I will fallback on my fixed-height plan.
Ok, thanks for the hints. I build synaptic against GLib/Pango/Gtk+ HEAD and measured the time spend in do_validate_rows via clock() (sorry for this simple method but I was to lazy to build a profiling version again). Please note that I measured how long it takes to build the complete tree (until idle), not the time until something is visible for the first time. My results for a list with ~13.000 packages and 6 columns (1 pixmap, 5 text): GTK+ - HEAD: start - end do_validate_rows: 6140000 = 6.1sec GTK+ - 2.2.2 start - end do_validate_rows: 8590000 = 8.5sec (times measured/approximated ;) in clock_t on a 1200Mhz Pentium3) While this is certainly a improvement, I really hope that there is room for more :) [Disclaimer: I'm not 100% sure if this figures are ok for HEAD, because something is wrong with my pango HEAD installation, I get: "** (synaptic:17820): WARNING **: No builtin or dynamically loaded modules were found. Pango will not work correctly." on startup.]
Soren or Michael: could you run CVS HEAD against the two benchmarks I attached to issue #71968? (1) http://bugzilla.gnome.org/showattachment.cgi?attach_id=6815 times how long it takes to populate & render a 30,000-item clist (2) http://bugzilla.gnome.org/showattachment.cgi?attach_id=6816 time-treeview.c: times how long it takes to populate & render a 30,000-item treeview cheers
I think it should be emphasized that benchmarking GtkTreeStore is one thing and the other thing is to have ability to "only call the data provider for visible cells" - as Morten wrote. Otherwise, GtkTreeView will remain hardly useful for browsing eg. databases and similar data structures which have large cost associated with fetching the data.
I have to say that I agree with Pavel here. I did a benchmark nevertheless :) Here are my results (same as above my pango HEAD gives me a warning about: No builtin or dynamically loaded modules found). HEAD ** Message: clist inserted 30000 rows in 0.2 seconds (143375 rows/sec) ** Message: added 30000 rows in 2.2 seconds (13369 rows/sec) GTK+ - 2.2.2 ** Message: clist inserted 30000 rows in 0.2 seconds (133822 rows/sec) ** Message: added 30000 rows in 2.8 seconds (10555 rows/sec) [Machine is a Pentium3 1200Mhz, gcc 3.3.1]
A small addition: from the 2.2 sec it took in HEAD to display the list, 2,03 secs are spend in do_validate_rows() (according to my "clock()" profile).
> Message: clist inserted 30000 rows in 0.2 seconds (143375 rows/sec) > Message: added 30000 rows in 2.2 seconds (13369 rows/sec) So the treeview is over an order of magnitude slower than gtkclist. jrb marked #71968 (which was closed as a dup of this bug) as a high priority, major severity back in Feb 2002.
Created attachment 19790 [details] [review] proof of concept patch to speed up validate_rows() against 2.2.2
I had a look into validate_rows() today and hacked around a bit. I added two new private variables use_uniform_row_height and uniform_row_height. If uniform_row_height is set (currently hardcoded), the row height is only calculated once in validate_rows() and then used for all other rows in the treeview. This way, the treeview is much faster. I attach a proof of concept patch against gtk+ 2.2.2 (the patch is pretty trivial).
Created attachment 19791 [details] [review] second part of proof of concept patch for speeding up validate_rows()
Yes, we know that, and that is what we need to get TreeView to do most of the time. The only problem is deciding when exactly we use which method. I wrote some ideas on paper during class last week, which I am trying to get jrb to look at (he has some comments on those). The plan is here: http://www.math.leidenuniv.nl/~kris/validation-plan As soon as jrb and I settle on those details, I can start implementing it. Then it won't be long before there is a patch ;) I really want to write this patch and get it in soon now.
After talking with owen on IRC, we decided to go with the property. Owen basically had two comments: * He doesn't like a scrollbar which starts changing automagically when scrolling. * In order to use this, the programmer should set *all* columns to FIXED and set the fixed_height_mode property to TRUE. Else it will not work. I will attach two patches: 1) The patch adding a fixed_height_mode property. 2) A patch (inspired by jrb) to shortcircuit touching the childs in gtk_tree_view_build_tree if the model specifies that it doesn't and won't contain children.
Created attachment 19877 [details] [review] Fixed height patch.
Created attachment 19878 [details] [review] Patch shortcircuiting _build_tree.
thanks for the patch. the speed is _much_ better. in fact no slowdown is noteable at all with 12.000 entrys with my P3-1200. the row height is wrong in my test, but it's wrong regardless if I enable fixed_height or not, so it's probably my fault (installing two pango versions seems a bit tricky). This will be part of gtk 2.4? released in november? can't wait for it :) It's really great that this issue is fixed now! thanks a lot!
> * He doesn't like a scrollbar which starts changing > automagically when scrolling. Neither do I, but this would _only_ happen when the TreeView was "proven wrong", so in the 99% case where the tree view actually is fixed height, the scrollbar would not change automagically. And in the case of a big list (which is what we are concerned about here), the scrollbar thumb would be at its minimum width anyway, so unlikely to actually change. The only advantage to having the property that I see is that in the case where the rows are unequal height AND the programmer knows that this may be the case AND the treeview is _not_ big enough to make the scrollbar thumb the minimum size AND the programmer is conscientious to not turn on the property anyway, in that case scrollbar thumbs won't change size during scroll (but the tree view will be slow). The disadvantage is that it requires the programmer to manually specify information that he in many cases *does not have*. If the data comes from an external source, then the programmer often can't be sure that it will actually be fixed height without manually doing a validation ... I predict programmers will invariably turn the property on anyway, and things will be broken when the rows are actually unequal height. The TreeView could compensate by actually doing a validation when it discovers a row with a different height, but then you'd get changing scrollbars ... > * In order to use this, the programmer should set *all* columns to > FIXED and set the fixed_height_mode property to TRUE. Else it will > not work. This would be necessary for both approaches, but the no-property approach would result in one less thing that could fail. (Why doesn't the tree view use the RB tree to keep track of the maximum width btw? It should not be necessary to pass over all the data for each and every change to some row.)
Soeren - you seem to be neglecting that most tree views are small enough for the current approaches to work well. I think sacrificing correctness (and the scrollbar that changes size as you scroll is *not* correct) for those tree views would be a bad mistake. And also, since you have to set all columns to FIXED means that people have to read the "My TreeView is slow" FAQ anyways, so adding something else there isn't a big deal. (The reason that autosize is as slow at is is because a per-column width attribute in the RBTree would be a huge memory sink. But even if you took that hit, you'd still have to measure every string in the tree.)
I'm one of the developpers of Balsa, and for us we can afford to have automagically changing scrollbars if the tree can be drawn rapidly for thousands of lines (~10 columns by row). And I guess pan will also use that feature (last time I checked they were still using clist or ctree, and I think it is certainly for perormance reason). So I would vote for this : fixed height tree could be turned on by the programmer and he could also ask the treeview to adapt its height when a visible line is greater than the fixed value.
I checked out the latest gtk cvs today and I noticed that the "fixed_height_mode" patch is not in (yet). What prevents it from going in?
I am waiting on Jonathan to review/approve the patches.
I really don't want to get on your nerves, but according to http://www.gtk.org/plan/2.4/ there is the api/abi freeze planed for 1 October 2003. I'm sligthly worried, that if the patch does not make it before, it will be missing in gtk 2.4.
As bug 123538 shows, it only takes 100 lines of text to make things horribly slow. Long lines, admittedly, but that is what real life is going to throw at treeview/pango. If the powers that be intend to let this one slip, would they please speak up! Then, at least, we could make informed decision as to whether a forked and severely bastadized treeview should be coded up for gnumeric.
gnumeric wouldn't be the only program with the forked gtktreeview if this patch does not make it. True, one can work around this in certain conditions with help of some gtk_tree_view_get_visible_rect() gtk_tree_view_get_cell_area() calls but that's not effective, and it breaks the MVC model.
Michael / Pawel / etc. The sign of something not making the API freeze is someone changing the milestone to be "2.6 API freeze". Has that happened? Then you don't need to clutter up the bug report.
Sorry for making noise again. But it just wanted to ask if there is a way I can help getting the fixed-height patch in (now that 2.3.0 is released without the patch)? IMHO it's save to apply as it's not enabled by default and only applications that explicit set the property will get the new code.
I am going to pester jrb to get my patches reviewed this week.
Some comments on "Patch shortcircuiting _build_tree" first: * You need to do a g_return_val_if_fail(model->priv->child_model) in both GtkTreeModelFilter and GtkTreeModelSort, as we can't change our flags after the child model has been added. Thus get_flag shouldn't be called before the child is set. * It looks like we don't set the _IS_LIST flag in the case where the model doesn't explicitly set the flag, but it is one anyway.
Some comments on the first reading of the fixed-height patch: * If there's the invariant that columns have to be FIXED for fixed_height to be set, then we need to also check for it when we add new columns or when columns change their SIZING. * I think we should store the height of the fixed height (and clear it in style_set). Your current strategy of always using tree_view->priv->tree->root as the height is cute, but won't provide a consistent behavior. People will use this with non-fixed-height trees despite the warning, and tree_view->priv->tree->root will change as nodes get added/removed. Additionally, if we keep the height, we can actually do insert_remove synchronously.
Jonathan: are your comments about fixed-height patch a show-stopper for the inclusion of the in gtk 2.3.1? Kristian: are you working on the issues pointed out by Jonathan already or do you want me to give it a try? (though I don't have a lot of experience with the internals of the widget).
I will fix my patch and commit it on Saturday.
(build tree patch went in yesterday, fixed height will follow later (needs more changes and a new review)).
Created attachment 22513 [details] [review] second attempt.
Second attempt committed with some slight changes. Case closed. (hooray)
This isn't actually quite as powerful as I would have liked. It currently requires gtk_tree_view_column_get_sizing (column) == GTK_TREE_VIEW_COLUMN_FIXED which, if I understand things right, means that I must come up with a proper width in pixels for the column (since I have more than one column). What does width have to do with fixed-height?
Yes, you are going to have to come up with a good width for your column. Fixed height mode basically avoids the validation phase; in the validation phase the width was also measured to come up with a good column size for autosize columns. Since fixed height mode avoids validation this is no longer possible. I might change the requirement to be "the column should not be of type AUTOSIZE", instead of "the column should be of type FIXED". But I will talk with jrb about that first. But that's not going to help you much. Anyway, you get to come up with a column size. This complete fixed height thing is not the most beautiful hack of the world. As I said in my mail on gtk-devel-list/d-d-l, only use it when it is REALLY needed. Closing again as FIXED.