From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Pushing the `gnus-range-*' functions down into the C layer Date: Fri, 10 Sep 2010 12:43:11 +0200 Message-ID: References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1284115406 26386 80.91.229.12 (10 Sep 2010 10:43:26 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 10 Sep 2010 10:43:26 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Sep 10 12:43:25 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 1Ou14n-0007Aj-CJ for ged-emacs-devel@m.gmane.org; Fri, 10 Sep 2010 12:43:25 +0200 Original-Received: from localhost ([127.0.0.1]:36973 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Ou14m-0001Iv-B0 for ged-emacs-devel@m.gmane.org; Fri, 10 Sep 2010 06:43:24 -0400 Original-Received: from [140.186.70.92] (port=38864 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Ou14e-0001IR-Fk for emacs-devel@gnu.org; Fri, 10 Sep 2010 06:43:17 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1Ou14d-0003YS-E7 for emacs-devel@gnu.org; Fri, 10 Sep 2010 06:43:16 -0400 Original-Received: from impaqm5.telefonica.net ([213.4.138.5]:34347) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Ou14d-0003Xv-36 for emacs-devel@gnu.org; Fri, 10 Sep 2010 06:43:15 -0400 Original-Received: from IMPmailhost1.adm.correo ([10.20.102.38]) by IMPaqm5.telefonica.net with bizsmtp id 4v3y1f00v0piX6q3RyjDNC; Fri, 10 Sep 2010 12:43:13 +0200 Original-Received: from ceviche.home ([83.61.42.227]) by IMPmailhost1.adm.correo with BIZ IMP id 4yjB1f00G4u4RdP1hyjCWJ; Fri, 10 Sep 2010 12:43:13 +0200 X-Brightmail-Tracker: AAAAAA== X-TE-authinfo: authemail="monnier$movistar.es" |auth_email="monnier@movistar.es" X-TE-AcuTerraCos: auth_cuTerraCos="cosuitnetc01" Original-Received: by ceviche.home (Postfix, from userid 20848) id 75FE2660D2; Fri, 10 Sep 2010 12:43:11 +0200 (CEST) In-Reply-To: (Lars Magne Ingebrigtsen's message of "Thu, 09 Sep 2010 17:16:56 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. 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:129875 Archived-At: > Would anyone mind if I implemented the `gnus-range-*' functions in C for > Emacs 24? Gnus spends significant time on group entry/exit doing range > handling/compressing/etc, and I think the functions are (slightly) > generally useful. I wouldn't rule it out, but I'm reluctant to move Elisp code to C for the same kinds of reason Andy just gave. Especially for such a thing as range/interval algorithms where the best algorithm depends a fair bit on the particular shape of your data. OTOH, speeding up Elisp is not something I expect to happen soon (although moving to lexical bindings is a step in the right direction). Maybe once we have dyn-loading in place, Gnus can provide its own C functions outside of Emacs's own C code. > Gnus addresses articles by their number, so you have things like the > "marked" list of articles that looks like > (3 4 5 6 7 11 14 15 16 17 18) What algorithm does Gnus use currently? I guess you call `sort' and then scan the list looking for contiguous points? That would make it O(n log n), which isn't too bad, but it also means that the C part of the code is O(n log n) and the Elisp part is O(n), so the speed of Elisp should not be a big issue. > (or something). To save loading/saving time, these are stored in the > .newsrc.eld file as range structures, which look like this: > ((3 . 7) 11 (14 . 18)) > To handle this, Gnus has a set of functions for computing > intersections/differences/etc on the range structures. Ah, so you don't just convert to/from lists of points to intervals, but you also work directly on intervals. 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)? > However, Emacs Lisp isn't really fast at doing this, It's not fast at other things either ;-) Stefan