* pop3 speedup @ 2011-09-26 18:37 Lars Magne Ingebrigtsen 2011-09-26 19:16 ` Matthias Andree 0 siblings, 1 reply; 8+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-09-26 18:37 UTC (permalink / raw) To: ding I noticed that pop3 mail fetching took exponential time (i.e., a bit mailbox would take forever to fetch) and rewrote the fetch-and-wait function to be linear instead. The new function seems to work for me, but I thought I'd give you a heads up. If you see anything odd in this area, please tell me. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pop3 speedup 2011-09-26 18:37 pop3 speedup Lars Magne Ingebrigtsen @ 2011-09-26 19:16 ` Matthias Andree 2011-09-26 19:29 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 8+ messages in thread From: Matthias Andree @ 2011-09-26 19:16 UTC (permalink / raw) To: ding; +Cc: Lars Magne Ingebrigtsen Am 26.09.2011 20:37, schrieb Lars Magne Ingebrigtsen: > I noticed that pop3 mail fetching took exponential time (i.e., a bit > mailbox would take forever to fetch) and rewrote the fetch-and-wait > function to be linear instead. > > The new function seems to work for me, but I thought I'd give you a > heads up. If you see anything odd in this area, please tell me. _exponential_? How does an algorithm for POP3 mail fetching with such a complexity look like? (URL to some Git front-end with the diff suffices) I've seen various awkward cases in POP3 or IMAP clients as worse as O(n^2 * log n), but I can't possibly fancy how to attain O(e^n). -- Matthias Andree ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pop3 speedup 2011-09-26 19:16 ` Matthias Andree @ 2011-09-26 19:29 ` Lars Magne Ingebrigtsen 2011-09-26 19:34 ` Antoine Levitt 2011-09-26 20:01 ` Matthias Andree 0 siblings, 2 replies; 8+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-09-26 19:29 UTC (permalink / raw) To: Matthias Andree; +Cc: ding Matthias Andree <ma@dt.e-technik.uni-dortmund.de> writes: > _exponential_? How does an algorithm for POP3 mail fetching with such a > complexity look like? The old algorithm counted all the messages in the buffer from the start repeatedly while waiting for them all to arrive. So if you fetched 1000 messages, it would typically first count 10 messages, then it would count 20, then it would count 30, all the way up to 1000. Hm. Is that exponential? > I've seen various awkward cases in POP3 or IMAP clients as worse as > O(n^2 * log n), but I can't possibly fancy how to attain O(e^n). I know, I'm pretty awesome. :-) -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pop3 speedup 2011-09-26 19:29 ` Lars Magne Ingebrigtsen @ 2011-09-26 19:34 ` Antoine Levitt 2011-09-26 19:35 ` Lars Magne Ingebrigtsen 2011-09-26 20:01 ` Matthias Andree 1 sibling, 1 reply; 8+ messages in thread From: Antoine Levitt @ 2011-09-26 19:34 UTC (permalink / raw) To: ding 26/09/11 21:29, Lars Magne Ingebrigtsen > Matthias Andree <ma@dt.e-technik.uni-dortmund.de> writes: > >> _exponential_? How does an algorithm for POP3 mail fetching with such a >> complexity look like? > > The old algorithm counted all the messages in the buffer from the start > repeatedly while waiting for them all to arrive. So if you fetched 1000 > messages, it would typically first count 10 messages, then it would > count 20, then it would count 30, all the way up to 1000. > > Hm. Is that exponential? Nope, it's n^2, polynomial (1 + 2 + 3 + 4 ... + n is about n^2/2). ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pop3 speedup 2011-09-26 19:34 ` Antoine Levitt @ 2011-09-26 19:35 ` Lars Magne Ingebrigtsen 2011-09-26 19:55 ` Antoine Levitt 0 siblings, 1 reply; 8+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-09-26 19:35 UTC (permalink / raw) To: ding Antoine Levitt <antoine.levitt@gmail.com> writes: > Nope, it's n^2, polynomial (1 + 2 + 3 + 4 ... + n is about n^2/2). Darn. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pop3 speedup 2011-09-26 19:35 ` Lars Magne Ingebrigtsen @ 2011-09-26 19:55 ` Antoine Levitt 2011-09-26 20:09 ` Matthias Andree 0 siblings, 1 reply; 8+ messages in thread From: Antoine Levitt @ 2011-09-26 19:55 UTC (permalink / raw) To: ding 26/09/11 21:35, Lars Magne Ingebrigtsen > Antoine Levitt <antoine.levitt@gmail.com> writes: > >> Nope, it's n^2, polynomial (1 + 2 + 3 + 4 ... + n is about n^2/2). > > Darn. Don't worry, you'll get it next time. (actually, it's pretty hard to do something exponentially on a list structure. You'd have to run a non-trivial recursion. And then, of course, find something to do with it.) ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pop3 speedup 2011-09-26 19:55 ` Antoine Levitt @ 2011-09-26 20:09 ` Matthias Andree 0 siblings, 0 replies; 8+ messages in thread From: Matthias Andree @ 2011-09-26 20:09 UTC (permalink / raw) To: ding Am 26.09.2011 21:55, schrieb Antoine Levitt: > 26/09/11 21:35, Lars Magne Ingebrigtsen >> Antoine Levitt <antoine.levitt@gmail.com> writes: >> >>> Nope, it's n^2, polynomial (1 + 2 + 3 + 4 ... + n is about n^2/2). >> >> Darn. > > Don't worry, you'll get it next time. > > (actually, it's pretty hard to do something exponentially on a list > structure. You'd have to run a non-trivial recursion. And then, of > course, find something to do with it.) The text book example of something recursing deeply and thus massively is the two-argument Ackermann function. Typical exponential problems are certain kinds of perfect optimization problems and quite a lot of scheduling problem classes, among them the travelling salesman problem. -- Matthias Andree ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pop3 speedup 2011-09-26 19:29 ` Lars Magne Ingebrigtsen 2011-09-26 19:34 ` Antoine Levitt @ 2011-09-26 20:01 ` Matthias Andree 1 sibling, 0 replies; 8+ messages in thread From: Matthias Andree @ 2011-09-26 20:01 UTC (permalink / raw) To: Lars Magne Ingebrigtsen; +Cc: ding Am 26.09.2011 21:29, schrieb Lars Magne Ingebrigtsen: > Matthias Andree <ma@dt.e-technik.uni-dortmund.de> writes: > >> _exponential_? How does an algorithm for POP3 mail fetching with such a >> complexity look like? > > The old algorithm counted all the messages in the buffer from the start > repeatedly while waiting for them all to arrive. So if you fetched 1000 > messages, it would typically first count 10 messages, then it would > count 20, then it would count 30, all the way up to 1000. > > Hm. Is that exponential? No, squared, which is worse enough in this case. :-) Watch (disregard small constant factors such as 2 or 1/2 or 5, only the asymptotical growth matters): n n log n n^2 2^n linear lin-log squared exponential (base 2 here) 3 5 9 8 5 12 25 32 10 33 100 1,024 30 147 900 1,073,741,824 100 664 10,000 1.26E30 1000 9,965 1,000,000 1.07E300 >> I've seen various awkward cases in POP3 or IMAP clients as worse as >> O(n^2 * log n), but I can't possibly fancy how to attain O(e^n). > > I know, I'm pretty awesome. :-) O(n^2) code is easily written (two nested loops with similar upper bound) and quickly hurts when trying to scale software from the test beds -- but you've got company there. Some algorithms, such as checking UID lists for "POP3 + leave messages on server", can't get better than O(n log n) which is why I included that above. -- Matthias Andree ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2011-09-26 20:09 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-09-26 18:37 pop3 speedup Lars Magne Ingebrigtsen 2011-09-26 19:16 ` Matthias Andree 2011-09-26 19:29 ` Lars Magne Ingebrigtsen 2011-09-26 19:34 ` Antoine Levitt 2011-09-26 19:35 ` Lars Magne Ingebrigtsen 2011-09-26 19:55 ` Antoine Levitt 2011-09-26 20:09 ` Matthias Andree 2011-09-26 20:01 ` Matthias Andree
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).