From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/80036 Path: news.gmane.org!not-for-mail From: Matthias Andree Newsgroups: gmane.emacs.gnus.general Subject: Re: pop3 speedup Date: Mon, 26 Sep 2011 22:01:47 +0200 Message-ID: <4E80DA2B.1020409@dt.e-technik.uni-dortmund.de> References: <4E80CFAA.9050601@dt.e-technik.uni-dortmund.de> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1317067335 32758 80.91.229.12 (26 Sep 2011 20:02:15 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 26 Sep 2011 20:02:15 +0000 (UTC) Cc: ding@gnus.org To: Lars Magne Ingebrigtsen Original-X-From: ding-owner+M28329@lists.math.uh.edu Mon Sep 26 22:02:11 2011 Return-path: Envelope-to: ding-account@gmane.org Original-Received: from util0.math.uh.edu ([129.7.128.18]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1R8HNR-0002XP-QE for ding-account@gmane.org; Mon, 26 Sep 2011 22:02:10 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.math.uh.edu) by util0.math.uh.edu with smtp (Exim 4.63) (envelope-from ) id 1R8HNG-0004cH-9d; Mon, 26 Sep 2011 15:01:58 -0500 Original-Received: from mx2.math.uh.edu ([129.7.128.33]) by util0.math.uh.edu with esmtps (TLSv1:AES256-SHA:256) (Exim 4.63) (envelope-from ) id 1R8HNE-0004c1-VI for ding@lists.math.uh.edu; Mon, 26 Sep 2011 15:01:56 -0500 Original-Received: from quimby.gnus.org ([80.91.231.51]) by mx2.math.uh.edu with esmtps (TLSv1:AES256-SHA:256) (Exim 4.76) (envelope-from ) id 1R8HNE-0003V1-3k for ding@lists.math.uh.edu; Mon, 26 Sep 2011 15:01:56 -0500 Original-Received: from krusty.dt.e-technik.uni-dortmund.de ([129.217.163.1] helo=krusty.dt.e-technik.tu-dortmund.de) by quimby.gnus.org with esmtp (Exim 4.72) (envelope-from ) id 1R8HNC-00069T-NX; Mon, 26 Sep 2011 22:01:54 +0200 Original-Received: from [192.168.0.4] (g225194011.adsl.alicedsl.de [92.225.194.11]) by mail.dt.e-technik.tu-dortmund.de (Postfix) with ESMTPSA id 61B9298366; Mon, 26 Sep 2011 22:01:49 +0200 (CEST) User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2 In-Reply-To: X-Spam-Score: -2.4 (--) List-ID: Precedence: bulk Xref: news.gmane.org gmane.emacs.gnus.general:80036 Archived-At: Am 26.09.2011 21:29, schrieb Lars Magne Ingebrigtsen: > Matthias Andree 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