GNOME Bugzilla – Bug 611922
gtk_tree_model_sort_ref_node() is too slow
Last modified: 2011-08-22 21:22:26 UTC
Created attachment 155337 [details] Test case Compile and run the attached test case (written by Alban Crequy). It is terribly slow for large values of DEEP (some 35 seconds in my computer when DEEP == 27) This is because gtk_tree_model_sort_ref_node() is being called recursively in a non-linear way. This was introduced in commit b1285c3fe6333101aaa76a985a1e1f7832c55fbe in order to fix bug 364946
Created attachment 155338 [details] [review] Possible patch First of all I admit being unfamiliar with this code, but after a quick look I wonder why a node has to iterate over all of its parents. If you just ref the parent node it will in turn ref its own parent recursively, and thus all parents will end up with a reference added. I'm attaching a patch that does this. Can someone please review it? Thanks!
Looks right to me, but this really needs double-checking by kris.
(In reply to comment #2) > Looks right to me, but this really needs double-checking by kris. I agree, but I haven't seen him lately :) Let's wait then
This patch is not something that can be reviewed in 5 minutes. The main point here is that I have to investigate why exactly we changed the code in the past to recursively ref count all parents. This might or might not be something that was changed before I really started to touch this code. Once that has been found it, it has to be verified whether these cases are properly under test in the unit tests. There is a possibility this has to do with the "zero reference counting" mechanism that is in place there.
(In reply to comment #4) > The main point here is that I have to investigate why exactly we > changed the code in the past to recursively ref count all parents. To fix bug 364946. Here's the original commit: http://git.gnome.org/browse/gtk+/commit/?id=b1285c3fe6333101aaa76a985a1e1f7832c55fbe The thing is that to (un)ref all parents, it's enough to do it with the first one, since it will do the same with its parent, and so on. However your patch makes each and every node iterate over all its parents using a while loop.
Still valid in current master
Kris, any update on this ?
I haven't had the time yet .... As I mentioned in comment 4, this is not a trivial change and needs thorough checking (and a good unit test) because something can break under the hood and not manifest itself until it shows up as a very obscure bug in 1.5 years or so ...
Finally managed to dive into this while writing unit tests for the reference counting done by GtkTreeModelSort. Alberto's patch in comment 1 should work, however I think in that case we are still referencing the parent nodes too often. Instead, I think we should actually reference the parent of a level in gtk_tree_model_sort_build_level and unreference the parent in gtk_tree_model_sort_free_level. I implemented this and judging from my newly written unit tests, the sort model now references nodes in the child model properly. I will attach the two patches. These are both in my local treemodel-fix branch, which will be merged into master as soon as I get GtkTreeModelFilter's reference counting under unit test and merge bug 616871.
Created attachment 189119 [details] [review] [PATCH] Bug 611922 - gtk_tree_model_sort_ref_node() is too slow
Created attachment 189120 [details] [review] [PATCH] Avoid unreferencing deleted nodes
This has been merged into master today.
Great, thanks !