GNOME Bugzilla – Bug 774494
ENameSelectorDialog slow with large address books
Last modified: 2017-01-11 18:57:27 UTC
When populating and modifying the contact list, some tasks are o(n^2). Thus, in the case of a very large contact list, clicking the To: or CC: buttons from within the composer appears to hang evolution. A SLE customer ran into this, since their university has a global address list with over 50,000 users. There are two problems: - Adding items to the contact list while a GtkTreeModelSort is attached causes gtk to continuously update each iter's offset, which is slow. It would be faster to connect the GtkTreeModelSort after the items are added to the contact list. - Updating the contact list as a result of a search is also slow, both because of the previous issue and because the code to determine the changes is o(m*n); there is a comment to this effect in the code.
Created attachment 339964 [details] [review] Proposed patch (1/2)
Created attachment 339965 [details] [review] Proposed patch (2/2)
Thanks for a bug report and patches. This is basically bug #630504. I'm adding it to the dependencies.
Review of attachment 339964 [details] [review]: There are some minor issues with this patch, but otherwise it seems to do what it should do, thus I'll make the changes myself and commit it. ::: src/e-util/e-contact-store.c @@ +459,3 @@ + contacts = source->contacts_pending; /* Pending view */ + +hash = g_hash_table_new (g_str_hash, g_str_equal); coding-style: missing tab @@ +466,3 @@ + + if (uid) + g_hash_table_insert (hash, uid, (gpointer)(gulong)i); it's `GINT_TO_POINTER (i)` @@ +710,1 @@ + if (!g_hash_table_lookup (hash, old_uid)) { g_hash_table_lookup() returns the value, which for index 0 is NULL, which is not correct. g_hash_table_contains() is what you need, or do not store the index in the hash table. I'll use the former.
Review of attachment 339965 [details] [review]: This one has also some minor issues. I'll fix it and commit. I'll not keep the patches split, I'll merge them into one. ::: src/e-util/e-contact-store.c @@ +200,3 @@ + G_OBJECT_CLASS_TYPE (object_class), + G_SIGNAL_RUN_LAST, + G_STRUCT_OFFSET (EContactStoreClass, start_update), stop_update, right? ::: src/e-util/e-contact-store.h @@ +70,3 @@ + void (*start_update) (EContactStore *contact_store, + EBookClientView *client_view); + void (*stop_update) (EContactStore *contact_store, coding-style: missing tab before the first argument ::: src/e-util/e-name-selector-dialog.c @@ +1142,3 @@ + + if (!dialog->priv->contact_sort) { + dialog->priv->contact_sort = GTK_TREE_MODEL_SORT ( coding-style: wrong indentation ::: src/e-util/e-tree-model-generator.c @@ +425,3 @@ + if (node->n_generated > 1) + tree_model_generator->priv->nested = TRUE; it's never set to FALSE (apart of the 'priv' structure allocation).
The first patch also produces a compiler warning: evolution/src/e-util/e-contact-store.c:490:31: warning: passing argument 2 of ‘g_hash_table_insert’ discards ‘const’ qualifier from pointer target type
The change in src/e-util/e-tree-model-generator.c breaks the things in runtime, I'm reverting (not going to use) that part. That's used for contacts which have filled several email addresses. I tried the changes and my "large" book, which consists of 4872 contacts and total of 19488 email addresses, takes some time to fill the name selector. It even looks like there was no performance change when opening the To/CC/Bcc dialog, because the view_complete() ends at the top with "/* If current view finished, do nothing */". The changed/added code in view_complete() is not triggered even in the auto-completion case in the message composer. Weird. I tend to mark this as a duplicate of the older bug and not commit anything, because it doesn't change anything, sadly.
Created attachment 340543 [details] your patch with fixed issues This is a merge of your patches with fixed issues as found during the review and testing of the changes in runtime.
(In reply to Milan Crha from comment #7) Thanks for the review and testing. > The change in src/e-util/e-tree-model-generator.c breaks the things in > runtime, I'm reverting (not going to use) that part. That's used for > contacts which have filled several email addresses. I'd been testing with an address book that only had one email address per user, so I hadn't caught that. I think that I wasn't setting nested in some places where it needed to be set, although, even with that fixed, the change won't be very useful, since it only improves things if no contacts have multiple email addresses. However, some kind of optimization would be helpful, since, for a large address book, it is very slow to count rows every time a value needs to be fetched, and this greatly affects the time required to sort the list. > I tried the changes and my "large" book, which consists of 4872 contacts and > total of 19488 email addresses, takes some time to fill the name selector. > It even looks like there was no performance change when opening the > To/CC/Bcc dialog, because the view_complete() ends at the top with "/* If > current view finished, do nothing */". > > The changed/added code in view_complete() is not triggered even in the > auto-completion case in the message composer. Weird. Interesting; it improves things for me, although I've reworked the ETreeModelGenerator changes to optimize generated_offset_to_child_offset a different way. > I tend to mark this as a duplicate of the older bug and not commit anything, > because it doesn't change anything, sadly. I hadn't noticed the older bug; perhaps I should attach a revised patch there.
That's okay, just use this bug report. When I added debug prints above your changes in view_complete(), then they were never hit. To test, create a new On This Computer address book and fill it with 1.000+ contains (mine has like 10.000). Remote address books can work differently, because they can pass contacts more slowly than the local address book.
Created attachment 341269 [details] [review] Updated patch. I've added a partial cache into e-tree-model-generator.c, to avoid needing to iterate through the whole list to find the correct row from which a value should be fetched. Wrt the changes to view_complete(), they come into play for me when a ENameSelectorDialog is active and I enter or remove text in the search field and the view changes. They don't come into play when the dialog is first open, but other changes ijn e-name-selector-dialog.c cause the creation of the GtkTreeModelSort to be delayed in that case.
Review of attachment 341269 [details] [review]: Thanks for the update. I'm wondering what compiler options you use, eventually what compiler, because gcc provides so many compiler warnings that they just cannot be overlooked. I think so at least. Thus I'm sorry, but as it produces so many compiler warnings (while it should not provide any), then I'm simply rejecting the patch. I can understand that some things are overlooked in the code changes, using the same coding style is as the project itself is also a pita and understandable, but when the compiler tells that something is wrong, then one should listen to it and fix it. ::: src/e-util/e-tree-model-generator.c @@ +319,3 @@ + + i = 0; + success = FALSE; the 'success' is already FALSE @@ +324,3 @@ + last_cached_offset = 0; + for (; cache; cache = cache->next) { + cache_last = cache; coding style: wrong indentation @@ +325,3 @@ + for (; cache; cache = cache->next) { + cache_last = cache; + CacheItem *item = cache->data; do not mix declaration and code (one of the compiler warnings) @@ +343,3 @@ + last_cached_offset = accum_offset; + if (cache_last) + cache_last = g_slist_append (cache_last, item); using the append means for a large groups that the whole (sub-)list (of the newly added items) is traversed again and again
(In reply to Mike Gorse from comment #11) > Wrt the changes to view_complete(), they come into play for me when a > ENameSelectorDialog is active and I enter or remove text in the search field > and the view changes. They don't come into play when the dialog is first > open, but other changes ijn e-name-selector-dialog.c cause the creation of > the GtkTreeModelSort to be delayed in that case. Do you mean that you cannot cover also the initial filling? That's the main pita, because it's always done when you select the respective book for the first time. Your changes for subsequent searches in the selected book are a big performance improvements, but when it takes like 5-times longer to fill the book for the first time, then it degrades the outcome. There should be also made special attention when closing the dialog and/or changing books. I see a UI freeze for several seconds when moving from a large address book to a small one.
Created attachment 342226 [details] [review] Updated patch. Right. Sorry; I was inattentive and hadn't noticed those warnings. I think that I've fixed all of them (mostly mixing GList and GSList). Also, I've disabled the GtkTreeModelSort while switching models; previously it was still attached in that case while individual rows were deleted and inserted. I'm curious whether this will fix all of the performance issues that you were encountering; for me, populating the initial view is much faster than it is without the patch.
Review of attachment 342226 [details] [review]: Thanks for the update. I didn't find anything fatal this time, there is no compiler warning and the one thing I found below is too easy to fix that I'm not going to request a patch resend only due to it. I found one problem though, it seems I'm able to create an inconsistent state in the left side of the dialog. I do it when changing the search term when the search is still ongoing. It results in the list of the contacts not being sorted at all and when I scroll down and select there a contact it will add it to the to/cc part, but then the removal from the left side shows an odd value, like the same as there were before I moved it to the right, the contacts at the top doesn't scroll down. That's when I have like four address per each 10K contacts. It looks like the internal structures and the "sorted" model do not agree. ::: src/e-util/e-name-selector-dialog.c @@ +1691,3 @@ g_signal_connect (contact_store, "stop-client-view", G_CALLBACK (stop_client_view_cb), name_selector_dialog); + g_signal_connect (contact_store, "start-update", G_CALLBACK (start_update_cb), name_selector_dialog); + g_signal_connect (contact_store, "stop-update", G_CALLBACK (stop_update_cb), name_selector_dialog); You forgot to disconnect the two handlers too, the same as the previous two are.
To be complete, with the previous patch it behaves significantly faster, only that glitch (see the previous comment) is very unfortunate and requires fixing first.
Created attachment 343195 [details] [review] Patch with fixed signals. Thanks for testing. I haven't been able to reproduce what you are describing so far; I'm curious if it persists, or if it is a temporary state that resolves itself after a few seconds. Anyhow, I tried modifying enable_sort() to first disable any existing sort model, rather than doing nothing if one exists. I'm hoping that this might help.
Thanks for the update. Unfortunately the issue is still there. I have a local book with 10K contacts. Each has multiple addresses. My reproducer is: a) click the To button in the composer b) select the large book c) once it's done, type search "aaaa" d) before the search completes use backspace to delete the typed search; I press it 4 times with a ~1 second delay, I do not keep it pressed After this moving the contacts from the bottom to the To/Cc part doesn't redraw the left part properly and eventually the added contacts do not match the one which had been selected on the left. I can try to find out what it is, if you are not able to reproduce. Just let me know, please.
Created attachment 343268 [details] [review] Fix a caching issue. I'm still having trouble reproducing, but I did find a problem with the e-tree-model-generator change. When a row is inserted or deleted, the cache is meant to be freed so that it is regenerated the next time generated_offset_to_child_offset is called, but there was a case where this was not happening, so the cache would get out of synch when an address is added to To or CC and removed from the list.
Thanks for the update. I tried with it and it seems to be it, I wasn't able to reproduce the issue with the latest patch. As it looks fine too (try also `git diff --check` command), I'm committing it to the sources. Created commit cffd6b5 in evo master (3.23.4+)