pop3 speedup

pop3 speedup

[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.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Re: pop3 speedup

[Matthias Andree]

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

Re: pop3 speedup

[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?

> 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/

Re: pop3 speedup

[Antoine Levitt]

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

Re: pop3 speedup

[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.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Re: pop3 speedup

[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.)

Re: pop3 speedup

[Matthias Andree]

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

Re: pop3 speedup

[Matthias Andree]

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