Hi,
I have one server that holds a lot of messages (actually, it's an IMAP
server that also offers POP3), and since I read mail from various places
off that server, I use POP3 to pull all unpulled mail from that
server.
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?
--
Matthias Andree
"Those who give up essential liberties for temporary safety deserve
neither liberty nor safety." - Benjamin Franklin