[Users] [PATCH] Optimize remove_numbered_files_not_in_list() complexity from O(n^2) to O(n)

Michael Rasmussen mir at miras.org
Wed Oct 10 00:08:59 CEST 2012

Hi Igor,

On Tue, 9 Oct 2012 22:45:54 +0200
Igor Mammedov <imammedo at redhat.com> wrote:

> If imap folder holds more then 55K messages, claws-mail may freeze for 5 or
> more seconds scanning folder. Following call chain has
> O(n^2) complexity: 
>   folder_item_scan_full()
>    -> imap_get_num_list()
>        -> remove_numbered_files_not_in_list()
> Converting it to O(n) significantly[1] cuts amount of executed
> instructions and reduces folder re-scanning time to ~1sec.
>  1) instruction fetch cut by factor 85, execution time cut from 44 to 0.7%.
It does seems to increase speed of imap folder scanning considerably.
The patch did have a corner case where it segfaulted. If the msgnumlist
provided for the scan - meaning the folder was empty - the lookup
failed since numberlist->data contains an invalid address. Patch
attached this mail solves this issue.

If the rest of the developers agree to this patch I will commit it.

That you very much for the patch.

Michael Rasmussen

Get my public GnuPG keys:
michael <at> rasmussen <dot> cc
mir <at> datanom <dot> net
mir <at> miras <dot> org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: optimize_scan.patch
Type: text/x-patch
Size: 1555 bytes
Desc: not available
URL: <http://lists.claws-mail.org/pipermail/users/attachments/20121010/d1059ef6/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <http://lists.claws-mail.org/pipermail/users/attachments/20121010/d1059ef6/attachment.sig>

More information about the Users mailing list