GNOME Bugzilla – Bug 657086
Contact list is slow with loads of contacts
Last modified: 2011-08-29 13:23:39 UTC
Created attachment 194380 [details] empathy_gprof.txt When connecting to an IM account with a lot of contacts, Empathy is slow to load. It has been reported here: https://bugs.meego.com/show_bug.cgi?id=20062 By running Empathy in GDB and stopping it while it's loading, I often see this stack: contact_list_store_add_contact -> contact_list_store_contact_update -> contact_list_store_find_contact It is O(n^2) with the number of contacts: for every contact to add, it iterates over the list of contacts. The attached GProf file shows it also spend time in individual_store_find_contact. But the cumulative seconds seems low compared to what it seems to me.
We could certainly design in a spinner in the contact list if the backend needs to batch the contact list so we can display something as soon as possible.
Created attachment 194704 [details] [review] [PATCH] contact list: optimize loading contacts The previous algorithm was O(n^2) with the number of contacts. Each contact can be in several groups, so when a contact is added or updated, we iterated over all the contact list to find the rows representing the contact. When connecting to an account and getting all the contacts, this was too slow. The groups are stored in the GtkTreeStore and suffer from the same problem: to look for a group, it needed to iterate on all contacts. The new algorithm maintains a hash from the contact to the list of rows representing it, and another hash from the group to the row representing it. This patch applies on EMPATHY_2_30_2. When tested on MeeGo with 300 contacts, loading the contacts is faster: roughly 9 seconds before the patch, 3 seconds after.
Created attachment 194726 [details] [review] [PATCH] contact list: optimize loading contacts (git master) The previous algorithm was O(n^2) with the number of contacts. Each contact can be in several groups, so when a contact is added or updated, we iterated over all the contact list to find the rows representing the contact. When connecting to an account and getting all the contacts, this was too slow. The groups are stored in the GtkTreeStore and suffer from the same problem: to look for a group, it needed to iterate on all contacts. The new algorithm maintains a hash from the contact to the list of rows representing it, and another hash from the group to the row representing it. On Empathy 2.30.2 when tested on MeeGo with 300 contacts, loading the contacts is faster: roughly 9 seconds before the patch, 3 seconds after. On Empathy 3.1.5, it seems to load in background so I don't know how to measure the time lost in GtkTreeStore. But before the patch, GProf says 23% is lost in individual_store_find_contact_foreach(), and after the patch it is not visible anymore. And "time" says we win 5s of CPU when starting+quitting Empathy: Before the patch: After the patch: real 0m23.485s real 0m23.460s user 0m13.805s user 0m8.305s sys 0m0.308s sys 0m0.316s
Review of attachment 194726 [details] [review]: Reviewed empathy-contact-list-store.c, assuming individual-store is just the same. ::: libempathy-gtk/empathy-contact-list-store.c @@ +663,3 @@ + g_str_equal, g_free, + (GDestroyNotify) gtk_tree_row_reference_free); + Isn't this the same as g_hash_table_remove_all() ? @@ +1036,3 @@ + list = g_list_prepend (list, row_ref); + gtk_tree_path_free (path); + g_hash_table_replace (priv->empathy_contact_cache, contact, list); lookup, steal, replace => basically 3 lookups for that contact... if you do a map EmpathyContact*->GQueue* instead you would be able to add/remove items without replacing the value in the table.
Created attachment 194835 [details] [review] [PATCH v2] contact list: optimize loading contacts (git master) Patch in Comment #3 updated with Xavier's review in Comment #4.
Created attachment 194840 [details] [review] [PATCH v2] contact list: optimize loading contacts (Empathy 2.30.2) Patch in Comment #2 updated with Xavier's review in Comment #4.
Looks good to me now. Reviewed only the patch for master though.
Review of attachment 194835 [details] [review]: I committed the patch on git master: http://git.gnome.org/browse/empathy/commit/?id=d2d6157547f7d386fea7721b4391b4d0c2b0d79b