* 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: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
* 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
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).