From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Daniel Pittman Newsgroups: gmane.emacs.devel Subject: Re: Pushing the `gnus-range-*' functions down into the C layer Date: Sat, 11 Sep 2010 13:18:15 +1000 Message-ID: <87aanp6k94.fsf@rimspace.net> References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1284177422 7519 80.91.229.12 (11 Sep 2010 03:57:02 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sat, 11 Sep 2010 03:57:02 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Sep 11 05:57:01 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1OuHD1-0003CC-Vy for ged-emacs-devel@m.gmane.org; Sat, 11 Sep 2010 05:57:00 +0200 Original-Received: from localhost ([127.0.0.1]:47369 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OuHD1-0006LL-FW for ged-emacs-devel@m.gmane.org; Fri, 10 Sep 2010 23:56:59 -0400 Original-Received: from [140.186.70.92] (port=35001 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OuGs5-0000mE-Nq for emacs-devel@gnu.org; Fri, 10 Sep 2010 23:35:23 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OuGrw-0001pj-7i for emacs-devel@gnu.org; Fri, 10 Sep 2010 23:35:16 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:60723) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OuGrv-0001pZ-RQ for emacs-devel@gnu.org; Fri, 10 Sep 2010 23:35:12 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1OuGrn-0006l7-UI for emacs-devel@gnu.org; Sat, 11 Sep 2010 05:35:03 +0200 Original-Received: from ppp59-167-189-244.static.internode.on.net ([59.167.189.244]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 11 Sep 2010 05:35:03 +0200 Original-Received: from daniel by ppp59-167-189-244.static.internode.on.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 11 Sep 2010 05:35:03 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 34 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: ppp59-167-189-244.static.internode.on.net User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) Cancel-Lock: sha1:SyLvi8JLZW8QCEbPYTf7AoYLBBw= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:129944 Archived-At: Lars Magne Ingebrigtsen writes: > Stefan Monnier writes: [...] >> What algorithms do you use there? These should be O(n), right? What do >> you know about the usual shape of your data? E.g. what's the expected >> difference between the smallest and the largest element (if it's not too >> large, we could store them in bitvectors and then provide bitwise or/and on >> bitvectors)? > > It varies a bit. The "read" range is usually on the form `(1 . 24254214)', > and this is (of course) never uncompressed. But you'd usually have > additional ranges for, say, ticked, and these would be quite sparse, like > `(45 (90 . 96) (200 . 259))' Or something like that. Oh, wouldn't it be lovely if there were all so polite. One of the problems my IMAP server delivers is that I get this data for long-lived folders with sparse email as is available here — because it is 8K in size. http://daniel.rimspace.net/gnus.el This is the nice version, incidentally, where I use a copy of the source into Dovecot because it returns a nicer set of UID values. The original spaces, for me, many email UIDs by ~ 100, ensuring that there are *no* contiguous numbers available in the sparse set that Gnus is working with. (It also leads to mailboxes with ~ 1000 numbered items across a range from 1 through 750,000 or so.) Daniel -- ✣ Daniel Pittman ✉ daniel@rimspace.net ☎ +61 401 155 707 ♽ made with 100 percent post-consumer electrons