GNOME Bugzilla – Bug 331479
Slow O(N^2) behaviour when scanning imap server folders makes evolution unusable
Last modified: 2011-02-10 11:28:59 UTC
Current evolution is 100% unusable when working from an imap server which serves files out of a large (many files) homedir, where only a small number are actually subscribed to as mail files. An O(N^2) performance effect on mailbox open means that it never (practically) actually finishes opening the mail account. An example is a server I use running UW imapd, on which I have a dozen or so mailboxes subscribed to but tens of thousands of other files in the homedir. An imap LIST command thus takes a long time to complete, but LSUB is fast. This worked perfectly on evolution-2.2.3 / evolution-data-server-1.2.3. But with evolution-2.5.90 and evolution-data-server-1.5.91, it is completely impossible to use evolution to access this mailbox due to an O(N^2) behaviour on startup. The problem starts in camel/providers/imap/camel-imap-store.c: get_folders_sync(): /* We do a LIST followed by LSUB, and merge the results. LSUB may not be a strict subset of LIST for some servers, so we can't use either or separately */ present = g_hash_table_new(folder_hash, folder_eq); for (j=0;j<2;j++) { response = camel_imap_command (imap_store, NULL, ex, "%s \"\" %G", j==1 ? "LSUB" : "LIST", pattern); Now, this is already a performance regression versus the older e-d-s, as this ends up doing a full LIST on account open, which takes around 5 minutes for me (older evolution was able to open the account in seconds.) But it gets *much* worse: for each folder found, we subsequently fall through the path parse_list_response_as_folder_info() ->camel_imap_store_summary_add_from_full() ->camel_imap_store_summary_full_name() which searches for an already-existing entry with the same name, by linear search. Doing this for each entry results in O(N^2) behaviour, which means that it would take days if not years for e-d-s to complete the account open in this situation. Simply turning the for (j=0;j<2;j++) { above into for (j=1;j<2;j++) { restores account access for me. Of course, this also disables the ability to subscribe to new folders through evolution, but I'll take non-functioning subscribe over non-function mail reading any day. A full fix would have to perform the LIST merge only when needed for folder subscription, and would need to do so with an algorithm rather more efficient than O(N^2).
I have experienced very slow performance with imap too. Same for my co worker, only on first initialization though. My coworker had 2.4.x i have 2.5.x.
this seem to be still true in svn head
Bumping version to a stable release.
The new imapx provider in 2.32.x should not suffer from this problem. Anyone want to confirm that?
I'm using a completely different server now, unable to confirm either way.
Please feel free to reopen the bug if the problem still occurs with a newer version of GNOME 2.32.1 or later, thanks.