GNOME Bugzilla – Bug 109292
Massive inefficiency in gtk_tree_model_sort_level_find_insert()
Last modified: 2011-02-04 16:12:02 UTC
Two performance things: - The function does a linear search in the array instead of a binary search. - Even when the model is caching iters, it doesn't use that information but slowly converts to a path and back. These problems makes insertions into an existing GtkTreeModelSort incredibly slow, not suprisingly. Something that I think has been asked about several times gtk-list. There also is a suspicious looking piece of logic: if (!skip_sort_elt && SORT_ELT (iter->user_data2) == tmp_elt) continue; which looks very much backwards. The attached patch fixes both of these problems and seems to work well for me in limited testing. However, I would strongly recommend: A) Going through the patch carefully B) Doing more extensive testing, especially of the skip_sort_elt part, since I reversed the existing logic. One final note ... in the case where there are multiple elements that sort identically I think changing an element will, now, or with my patch, cause it to jump around, even if the change doesn't change the sort key. My guess is that the code should, in the skip_sort_elt case, do effectively: if (cmp (elt_index, elt_index- 1) == 0 || cmp (elt_index, elt_index + 1) == 0) return elt_index; That is, if the model is sorted without moving the element, don't move it.
Created attachment 15218 [details] [review] Patch fixing efficiency problems
I would say that it looks okay, but I am not yet sure yet whether we should include the "jumping thing". Also, I guess it's a good idea to only commit this on the HEAD branch for now. We can always backport later if it proves stable ... (GtkTreeModelSort is a fragile mess :/). Thanks for looking into this --Kris
Hi, I've been using this patch for a few days and it's an amazing improvement on the previous implementation, which was so slow that we got bug reports about it in epiphany (filtering a sorted view with ~250 nodes took more than 15 seconds in a modest computer). But (always a but), I think I've found a bug in it. When I try to sort an already sorted model, some elements are positioned in wrong places, and in successive sorts on that model they stay in the wrong place. My knowledge about GtkTreeView is very modest, but if you need it I could try to do a small testcase. Anyway you can see this trying the latest epiphany release, or cvs, with this patch applied to gtk+ and clicking twice in any topic in the Bookmarks Editor.
Not sure if I want this in 2.2. I think only if somebody stamptests it to death P: Anyway, it's up to owen and jrb from here.
We really need this to go in cvs. People are not even giving the Epiphany bookmark system a change due to the slowness of not using this patch.
Because GtkTreeModelSort is pretty fragile, I don't want to have this on the stable branch, unless Owen believes that the fix is rock solid and bugfree. Which means that at least the issue brought up by Xan should be fixed. I know Owen is pretty busy, I might look at it if I have time. But I am too afraid to mess things up again. Please don't send people to this bug to say "me too". That's not going to help any, except for the bug to be fixed later rather than earlier.
I tried it, and it doesn't sort quite right. I'm attaching a test case that doesn't work.
Created attachment 17077 [details] [review] rewrite of testtreesort.c that fails
Okay. I managed to finagle it into working, test it, and commit to both stable and HEAD. I'm pretty sure it's right, but would appreciate knowing immediately if I broke something.
This code seem to lead to some problem in Rhythmbox (CVS version at least). In the song view when one column is in sorting mode and we double-click on a song, the song list is incorrectly reordered. For example you are sorting with track number and have 4 songs with track numbers 1 2 4 10. If you dbl-click on the first song, it will get reorded in 2 1 4 10. I followed the code and landed in gtk_tree_model_sort_row_changed and then in gtk_tree_model_sort_level_find_insert. In this function the skip_index is always incorrectly computed, so the function does as if it was a new row to insert and it returns 2 (in reality 1 because of zero indexing) which leads to 2 1 10 ! Don't know if Rhythmbox messes something or if it a bug in the function.
Can you add a test case that demonstrates this?
[discussed with yann] The problem line is: skip_index = SORT_ELT (iter->user_data2) - SORT_ELT (level->array->data); here, iter is the child model's iter, not the iter of the current row. Thus, iter->user_data2 is unknown. We need to pass in the skip_index as calculating it from the child iter will be slow.
Created attachment 18829 [details] [review] Correct the skip_index computation problem.
Created attachment 18830 [details] [review] Nearly same patch but this one also changes the old_index computation method.
*** Bug 119243 has been marked as a duplicate of this bug. ***
Thanks for figuring it out and for providing a patch. I tested the patch with the Epiphany bug (#119243), since I guess you've already tested it with rb ;) Committed to gtk-2-2 and HEAD. (I hope this was the last reopening for this bug P: ).