GNOME Bugzilla – Bug 616871
GtkTreeModelFilter wasting CPU in g_array_remove_index()
Last modified: 2011-08-23 08:58:20 UTC
I've been profiling the usage of HildonLiveSearch to filter a view of 5000 rows. One of the issues I discovered is in GtkTreeModelFilter spending 12% of the time inside g_array_remove_index(). When I refilter the model, gtk_tree_model_filter_row_changed() is called on every rows, which will call gtk_tree_model_filter_remove_node() on rows that should not be shown anymore. Each time, an element have to be removed from level->array, which is a sorted GArray. That means that g_array_remove_index() is called and all the memory following the element is shifted. Since level->array contains FilterElt structs, and not pointers to FilterElt structs that memory to be shifted is huge when the array contains 5000 elements.... It looks like to me that the data structure used here is not optimal, using a GTree or GtkRBTree is probably much faster in this case. But the code is complex and lots of places are playing with index inside the array, making changing the data structure very hard. Currently I'm investiguating if changing the GArray to a GPtrArray containing pointer to FilterElt structs would already speedup (even if complexity of the operation remains the same without changing completely the structure). Any opinion?
Created attachment 159678 [details] Test case
For the record, I'm working on a patch for this bug, replacing GArray by a GSequence. So far, the result is time going from 17s to 1s when running test case on N900.
Here is my branch: http://git.collabora.co.uk/?p=user/xclaesse/gtk.git;a=shortlog;h=refs/heads/sequence All unit tests passes, and it even fixes an issue in gtk_tree_model_filter_rows_reordered() which was passing indexes values counting invisible elements to the outside. @Kris: I guess you are the one who should review this.
Note that GtkTreeModelSort could probably also have the same kind of patch.
(In reply to comment #3) > @Kris: I guess you are the one who should review this. I put it on my to do list. I cannot do any promises when I will get to this unfortunately, GTK+ hacking is not my day job and my spare time is extremely limited at the moment.
Added an patch in my branch, fixing crashes found when testing on Maemo.
I rebased my branch on master. Please don't forget to review this. The same patch got included into N900's glib and we found no regression. Thousands (millions?) people is already running that code everyday :) Setting dep on bug #617254 to replace bsearch_elt_with_offset() with g_sequence_lookup() once it lands in glib.
Unfortunately rebase had conflicts this time. I pushed rebased branch there: http://git.collabora.co.uk/?p=user/xclaesse/gtk.git;a=shortlog;h=refs/heads/sequence2 I hope I did not introduced any regression when rebasing, tests still pass at least. (In reply to comment #7) > Setting dep on bug #617254 to replace bsearch_elt_with_offset() with > g_sequence_lookup() once it lands in glib. done in the above branch
Happy birthday to the still waiting for review patch.
I was looking into 621076 first in combination with what to do with the row-deleted situation. However, I am being quite discouraged from doing so in my spare time this way.
I am now bringing GtkTreeModelFilter's reference counting under unit test, which will make the GtkTreeModelFilter unit tests more complete. After that I will start looking into this bug/patch.
(In reply to comment #11) > I am now bringing GtkTreeModelFilter's reference counting under unit test, > which will make the GtkTreeModelFilter unit tests more complete. After that I While bringing this under unit test, I also had to completely rework the filter model's reference counting handling to make it function like expected. I have this mostly under control now so can start looking at this patch. (In reply to comment #3) > All unit tests passes, and it even fixes an issue in > gtk_tree_model_filter_rows_reordered() which was passing indexes values > counting invisible elements to the outside. Is this still contained in the top commit? I think I should review that separately first and bring it under unit test.
(In reply to comment #12) > (In reply to comment #3) > > All unit tests passes, and it even fixes an issue in > > gtk_tree_model_filter_rows_reordered() which was passing indexes values > > counting invisible elements to the outside. > > Is this still contained in the top commit? I think I should review that > separately first and bring it under unit test. It has been a while I didn't look at that code, but I think that's fixed in the same commit, yes. If I understand correctly, in current code you have old_offset = j; ... tmp_array[elt_count] = old_offset; But j is an index in level->array. My new code does tmp_array[elt_count++] = g_sequence_iter_get_position (elt->visible_siter); So it takes the position couting only visible elements.
(In reply to comment #13) > It has been a while I didn't look at that code, but I think that's fixed in the > same commit, yes. If I understand correctly, in current code you have > > old_offset = j; > ... > tmp_array[elt_count] = old_offset; > > But j is an index in level->array. My new code does > > tmp_array[elt_count++] = g_sequence_iter_get_position (elt->visible_siter); > > So it takes the position couting only visible elements. Aha, good catch. The current code does take into account that some entries might not be in the array, but it does not take into account that entries which are invisible could be in the array. Nevertheless, it was pretty hard to construct a failing unit test for this, because typically invisible entries are not kept in the array. Unless the entry is the last one remaining in a level that needs to be kept cached and for this case, the unit test indeed failed. Fixing this properly in the current code is hard, so I will just not do that and work on merging your patch instead. I did "kind of" fix it by not emitting the rows-reordered signal when the number of visible nodes in a level is 0, which agrees with the above described situation (1 item remaining in level which is invisible).
(In reply to comment #8) > Unfortunately rebase had conflicts this time. I pushed rebased branch there: > > http://git.collabora.co.uk/?p=user/xclaesse/gtk.git;a=shortlog;h=refs/heads/sequence2 > > I hope I did not introduced any regression when rebasing, tests still pass at > least. I have rebased the patches on top of my treemodel-fix branch now and made the other necessary changes for this. Currently I am working out the last bugs so that all unit tests (including the various new ones I wrote over the last months) will pass.
Created attachment 193375 [details] [review] Updated patch #1
Created attachment 193376 [details] [review] Updated patch #2
The two patches I just attached can only be applied on top of the treemodel-fix branch, which is still local on my disk but will be merged into master soon. Due to the many changes in the filter model I made over the last few months, a large part of the merge had to happen manually. Not many changes were needed however -- I am quite happy with the quality of the original patch. I had my doubts about using visible_siter instead of a boolean and having a separate visible_seq first, but right now I agree that these are likely the best solutions. After some additional debugging, the patch passes all unit tests, including all new ones I wrote recently. The performance is really significantly improved, which is great! Next, I will write similar patches for GtkTreeModelSort.
Great, thanks for the updates :D
Created attachment 194281 [details] [review] similar patch for GtkTreeModelSort This is the patch I wrote 1,5 weeks ago to use GSequence in GtkTreeModelSort. Getting the sorting part right again was tricky, but it seems to work properly now. As with the filter model patches, this patch is based on my treemodel-fix branch.
This has been merged into master today.
Great! you did an awesome work on this, thanks.
And sorry that it had to take so long -- but I really had to improve the unit tests first to increase my confidence in applying any patches touching this code.