From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Wojciech Meyer Newsgroups: gmane.emacs.devel Subject: Re: Pushing the `gnus-range-*' functions down into the C layer Date: Thu, 09 Sep 2010 23:21:30 +0100 Message-ID: <878w3azhg5.fsf@gmail.com> References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1284070916 4402 80.91.229.12 (9 Sep 2010 22:21:56 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 9 Sep 2010 22:21:56 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Sep 10 00:21:55 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 1OtpVD-0006Aa-0V for ged-emacs-devel@m.gmane.org; Fri, 10 Sep 2010 00:21:55 +0200 Original-Received: from localhost ([127.0.0.1]:37596 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OtpVC-0001ML-FY for ged-emacs-devel@m.gmane.org; Thu, 09 Sep 2010 18:21:54 -0400 Original-Received: from [140.186.70.92] (port=50348 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OtpV6-0001Kd-8l for emacs-devel@gnu.org; Thu, 09 Sep 2010 18:21:49 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OtpV2-0003SS-EU for emacs-devel@gnu.org; Thu, 09 Sep 2010 18:21:48 -0400 Original-Received: from mail-ww0-f49.google.com ([74.125.82.49]:45391) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OtpV2-0003SJ-AS for emacs-devel@gnu.org; Thu, 09 Sep 2010 18:21:44 -0400 Original-Received: by wwb24 with SMTP id 24so2181106wwb.30 for ; Thu, 09 Sep 2010 15:21:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=domainkey-signature:received:received:from:to:subject:references :date:in-reply-to:message-id:user-agent:mime-version:content-type; bh=X4WrZF4HZRNiIS98mPJpq/tKJ1mIBiorLx6kpgvmba0=; b=V4BZ9FBzAzhOst6ohqaBDxJw8ds1t0M7MG1I4t3O6US/ZW6/3eY4zVPzG/MRhNK3fM XxevoL4VjH61hWRHWEyG/nzwc0T+f5FlklMggCnBwLS98e6E88pA77mIlfNZLKXRe/Yw 1JZlU1CVsOEtHV2z44xQfNolJL+DefmP/+Y0Q= DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=from:to:subject:references:date:in-reply-to:message-id:user-agent :mime-version:content-type; b=fZwdb9tMC3v3z7cCqG8rPoihnI3AcnBShDueGoVMiSIXcJ5dU17zaaT+Fs0nsmNkut fIihUzT+nhvCZeKvG9TDJj476fLEdLp2cFB4g9RXMqpF484RHvLPEl3hedFs2yawR3tO tJze9jFrhm1LDtPcH+hjDQHX43p/v+zjPUfnk= Original-Received: by 10.227.156.11 with SMTP id u11mr18514wbw.146.1284070903204; Thu, 09 Sep 2010 15:21:43 -0700 (PDT) Original-Received: from spec-desktop.specuu.com (host86-147-138-117.range86-147.btcentralplus.com [86.147.138.117]) by mx.google.com with ESMTPS id k15sm1242101wer.23.2010.09.09.15.21.40 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 09 Sep 2010 15:21:42 -0700 (PDT) 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 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) 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:129838 Archived-At: Lars Magne Ingebrigtsen writes: > 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. > > 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) > > (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. However, Emacs > Lisp isn't really fast at doing this, so if you exit from a group that > needs lots (I mean *lots*) of range handling, you get an annoying wait > while it sits there computing. > > So I'm proposing implementing a set of useful functions in C, like > `range-memq', `range-add', `range-intersection' and stuff. > > Thoughts? Hi, In my opinion your algorithm might need to change, but that's maybe I that I don't understand the problem domain correctly :). You don't really need to care about ranges or intervals. You load them into array of chars, each char index representing one article index and set to 0 or 1, if article was read. (ideally a bit array) Then at exit perform operation at array in the same way as you loaded, and save it back to ranges. It has linear complexity. You trade off space complexity for computational complexity. As a bonus you get the minimal representation in intervals. So I don't think you would need a specific core support (but that's my personal opinion). If you really want a clean solution, then there are algorithms. (I know they exist, but unfortunately I don't remember the name of it). Just mine two cents, Wojciech