Re: [fetchmail-devel] save_str problems.

[Rainer W. <rwe...@ms...>]

"Matthias Andree" <mat...@gm...> writes:
> Rainer Weikusat wrote on 2010-04-21:
>> The company I work for uses fetchmail to download mails from various
>> POP- and IMAP-servers in order to offer an anti-spam/ anti-virus
>> scanning service for smartphone owners. Below is an oprofile excerpt
>> from the 'download server' regarding fetchmail:

[...]

> You've bumped into a design flaw of fetchmail's  UID handling.

I assume it is rather an instance of 'Learn Lisp. It will make you a
better programmer for life' :->.

[...]

> If we were being blunt and wanted a quick fix, we'd kill the list and
> use  a vector (array) and realloc(), a flag "vector is sorted", and
> qsort and  bsearch. That would bring things to O(n log n)
>
> If we were to be decent, we'd use the right structure for our purpose,
> and  that's a hash table (in C++/STL i'd use a hash_set where
> available and a  set where unavailable). We might want to keep things
> in a database on  disk, rather than load/write the table for every
> run.
>
> Your patch effort is much appreicated, but however I have serious
> doubts  about taking it. save_str and id_find are used together and
> basically  O(n^2) complexity. Even if your patch shaves save_str down
> to O(n),  id_find usage pattern itself remains O(n^2).

struct idlist * is quite pervasive in the code. It is also used for
many 'short lists' (eg, ctl->localnames) where a linked list is at
least good enough. Keeping track of the last item on the oldsaved and
newsaved lists was just a reasonably non-invasive, fairly quick fix for
the 'worst offender' case (and the IMHO most braindead ...) I could
smuggle past my boss[*] as 'immediately useful and not that much
effort'.

	[*] I am actually supposed to add UID-support the IMAP
	protocol driver and this case of 'walk until your shoes fall
	off' just angered me ...