From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Lars Magne Ingebrigtsen Newsgroups: gmane.emacs.devel Subject: Re: Pushing the `gnus-range-*' functions down into the C layer Date: Fri, 10 Sep 2010 14:35:31 +0200 Organization: Programmerer Ingebrigtsen Message-ID: References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1284122163 25155 80.91.229.12 (10 Sep 2010 12:36:03 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 10 Sep 2010 12:36:03 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Sep 10 14:36:02 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 1Ou2pk-0001gz-Mc for ged-emacs-devel@m.gmane.org; Fri, 10 Sep 2010 14:36:01 +0200 Original-Received: from localhost ([127.0.0.1]:55142 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Ou2pj-0007Sa-PD for ged-emacs-devel@m.gmane.org; Fri, 10 Sep 2010 08:35:59 -0400 Original-Received: from [140.186.70.92] (port=39377 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Ou2pW-0007Qq-Or for emacs-devel@gnu.org; Fri, 10 Sep 2010 08:35:49 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1Ou2pS-0004Qw-Ne for emacs-devel@gnu.org; Fri, 10 Sep 2010 08:35:46 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:44237) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Ou2pS-0004Qi-DN for emacs-devel@gnu.org; Fri, 10 Sep 2010 08:35:42 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1Ou2pQ-0001UE-PM for emacs-devel@gnu.org; Fri, 10 Sep 2010 14:35:40 +0200 Original-Received: from cm-84.215.34.171.getinternet.no ([84.215.34.171]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 10 Sep 2010 14:35:40 +0200 Original-Received: from larsi by cm-84.215.34.171.getinternet.no with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 10 Sep 2010 14:35:40 +0200 X-Injected-Via-Gmane: http://gmane.org/ Mail-Followup-To: emacs-devel@gnu.org Original-Lines: 68 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: cm-84.215.34.171.getinternet.no Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwBAMAAAClLOS0AAAAElBMVEUfBglPOydkUzqxmow1 IhUlEA72lSZYAAACcElEQVQ4jVVTS3bbMAxkUmlvUMw+hOwDmEz3ogPuZRe4/1U6EJ00pZ+fTQwG nwEY4lqYVZKI1lqvl7qF0JLcwoM48kWlyS8A513mPei2vwZTvfNp1i6vAOoJPK3XsASR2QxO0m0F cPlTK373JcCsFoJJv8FedHF7PS3BD4BZ+h0GZxX8pnoAM77tTelWpY4T+XBHjtAE2fh2BKol3mB1 M0JR11ZoWQeFw/APqE5ijjEf5oKCg3UzB1pcc+KvJEg+yYbks91K5JO9/APMDkZ4lPRZL88UtYSw z/iAornX+nuY11I8iI1mrH2FQbn16Hogluqh0zIA2cKTMgHI95gz15LpkHUfsVDqWRtRdKY3vof9 tax8/SgrBLyETwRcPTcOIjCfGSe/G0jsDOlqD7A/V4bruZbygWTQqKvuUxS6M3H23AT2Ero51lUM +5CwLCkLnxtm3r0e2SZHSaRxKezro5vaJKh4V3XpvUVO5H3gHI3sU29DlWtk8jA2APg0gntBiixQ FennY7oqRK4GE7hekjzHi6gU82Z3eYFWDZX4ooCFgolI3qbTFMmXQIa6SNdQjr6BOoAjkPUZzYDR yHkxzB0TcUBdzhaJUuPsffSAUamEyVF3dn8k38HxXccC4+MMokzI4YslgVLHG+kamd2efakDapsx IOy0S8jx6o8vA7jx+Y7R6QX13nyIBDeE6i0m3GvCfw91AGCYaBL82TAqs4OBcBzhlNSvb3iL3XQA KAuP3dq4bYZhxgFgHlnaWstamd9dgAc/T6g8Nh9uCWI+4jcAk/sXv6X5BwO7vRRex/X8H4Dpy7fh G1iPR/rTNMh/AV5evBm7RbtZAAAAAElFTkSuQmCC Mail-Copies-To: never X-Now-Playing: Various's _Monika =?iso-8859-1?Q?B=E4rchen=5F=3A?= "Mico - I See A Soul" User-Agent: Gnus/5.110011 (No Gnus v0.11) Emacs/24.0.50 (gnu/linux) Cancel-Lock: sha1:dQCYLr7qV7kjQXlpP5F8uTudG3Q= 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:129886 Archived-At: Stefan Monnier writes: > 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). Actually, I think Emacs could do with moving more things down into the C layer. I mean, having en elisp implementation of sha1 is quite an achievement, but linking with libgcrypt would have given you that and much more. Just to take a random example. I don't think the C layer should be considered "second class". I mean, C isn't as nice as Lisp, but it's not like the C style in Emacs is less maintainable than most Emacs-Lisp functions out there. :-) Anyway, back to the range functions. I think it's slightly generally useful. My guess would be that if there was a faster sorted-integer-list interface, it would be used by others with similar needs. `range-memq' would be much faster than `memq' on a list of integers in most use cases. > Maybe once we have dyn-loading in place, Gnus can provide its own > C functions outside of Emacs's own C code. Would that help much, though? Anyway, that reminds me -- I think the module support in XEmacs hurt XEmacs more than it helped. You have to program so very defensively because you don't know what packages are installed by the user. In Emacs, it's so much more productive programming, because you can rely on all its bits being present. > 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. In general, the ranges come from the .newsrc.eld file, and are then uncompressed before being worked on. The lists are generally kept sorted, so it's not necessary to re-sort them before compressing. But I think you kinda underestimate how slow Emacs Lisp is compared to C. An O(n) function in Emacs Lisp can be slow enough to make it unpleasant for the user. > Ah, so you don't just convert to/from lists of points to intervals, but > you also work directly on intervals. At present, they're compressed and uncompressed, because memq is much faster in the general use cases than the Lisp range-member functions. But if range-memq was present in C, then I'd never uncompress. > 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. -- (domestic pets only, the antidote for overdose, milk.) larsi@gnus.org * Lars Magne Ingebrigtsen