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

[Michael Rasmussen]

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.

-- 
Hilsen/Regards
Michael Rasmussen

Get my public GnuPG keys:
michael <at> rasmussen <dot> cc
http://pgp.mit.edu:11371/pks/lookup?op=get&search=0xD3C9A00E
mir <at> datanom <dot> net
http://pgp.mit.edu:11371/pks/lookup?op=get&search=0xE501F51C
mir <at> miras <dot> org
http://pgp.mit.edu:11371/pks/lookup?op=get&search=0xE3E80917
--------------------------------------------------------------
-------------- 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>