Matthias Andree <ma(_at_)dt(_dot_)e-technik(_dot_)uni-dortmund(_dot_)de>:
The UIDL handling in fetchmail is VERY inefficient in this case, it
takes quite some time for duplicate elimination even on a Duron/700 with
plenty of RAM. I can imagine people using 486's, m68k's and 32bit sparcs
suffer big time when the server has longer UID lists.
The causes for uid.c's slowness are:
1/ for each UID, a linear search on an unsorted list is done
-> causes O(n^2) complexity, where O(log n) would suffice
2/ lists are handled recursively rather than iteratively in uid.c
-> causes function call overhead that could easily be saved by using
an iterative approach. AFAIK, gcc does not do tail recursion
elimination, and it's not possible in all functions either.
As I see it, the list functions of uid.c are used in fetchmail, driver
and checkalias, so the pop3 part of the uid module would better be split
off if it uses other mechanisms than linear singly-linked lists.
Any comments?
I'm afraid to touch that code; it seems to break worse every time I do.
If you have a clean patch to offer, I'll consider it.
--
<a href="http://www.tuxedo.org/~esr/";>Eric S. Raymond</a>
Militias, when properly formed, are in fact the people themselves and
include all men capable of bearing arms. [...] To preserve liberty it is
essential that the whole body of the people always possess arms and be
taught alike, especially when young, how to use them.
-- Senator Richard Henry Lee, 1788, on "militia" in the 2nd Amendment