After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 331479 - Slow O(N^2) behaviour when scanning imap server folders makes evolution unusable
Slow O(N^2) behaviour when scanning imap server folders makes evolution unusable
Status: RESOLVED FIXED
Product: evolution-data-server
Classification: Platform
Component: Mailer
1.12.x (obsolete)
Other Linux
: Normal major
: ---
Assigned To: evolution-mail-maintainers
Evolution QA team
Depends on:
Blocks:
 
 
Reported: 2006-02-16 23:37 UTC by Stephen Tweedie
Modified: 2011-02-10 11:28 UTC
See Also:
GNOME target: ---
GNOME version: ---



Description Stephen Tweedie 2006-02-16 23:37:17 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).
Comment 1 Frej Soya 2006-03-15 10:27:04 UTC
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.
Comment 2 Gilles Dartiguelongue 2007-04-30 09:41:21 UTC
this seem to be still true in svn head
Comment 3 Matthew Barnes 2008-03-11 01:00:17 UTC
Bumping version to a stable release.
Comment 4 Kjartan Maraas 2010-12-16 19:37:43 UTC
The new imapx provider in 2.32.x should not suffer from this problem. Anyone want to confirm that?
Comment 5 Stephen Tweedie 2011-01-04 11:38:40 UTC
I'm using a completely different server now, unable to confirm either way.
Comment 6 Akhil Laddha 2011-02-10 11:28:59 UTC
Please feel free to reopen the bug if the problem still occurs with a newer
version of GNOME 2.32.1 or later, thanks.