From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Luc Teirlinck Newsgroups: gmane.emacs.devel Subject: Re: lists.texi Date: Tue, 21 Jun 2005 14:00:47 -0500 (CDT) Message-ID: <200506211900.j5LJ0ls23408@raven.dms.auburn.edu> References: <200506182319.j5INJWF08937@raven.dms.auburn.edu> <200506190015.j5J0FQk09223@raven.dms.auburn.edu> <200506190037.j5J0b9Y09287@raven.dms.auburn.edu> <200506191747.j5JHlha11521@raven.dms.auburn.edu> <200506202312.j5KNCct19091@raven.dms.auburn.edu> NNTP-Posting-Host: main.gmane.org X-Trace: sea.gmane.org 1119382892 23850 80.91.229.2 (21 Jun 2005 19:41:32 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Tue, 21 Jun 2005 19:41:32 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Jun 21 21:41:31 2005 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1Dkobs-00016I-Cx for ged-emacs-devel@m.gmane.org; Tue, 21 Jun 2005 21:40:36 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DkoiM-0004oa-3H for ged-emacs-devel@m.gmane.org; Tue, 21 Jun 2005 15:47:18 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Dkofl-0003KP-Fr for emacs-devel@gnu.org; Tue, 21 Jun 2005 15:44:37 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Dkofk-0003Jq-NG for emacs-devel@gnu.org; Tue, 21 Jun 2005 15:44:37 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DkoWy-0000PZ-5h for emacs-devel@gnu.org; Tue, 21 Jun 2005 15:35:32 -0400 Original-Received: from [131.204.53.104] (helo=manatee.dms.auburn.edu) by monty-python.gnu.org with esmtp (Exim 4.34) id 1Dko3h-0000Q9-L5; Tue, 21 Jun 2005 15:05:17 -0400 Original-Received: from raven.dms.auburn.edu (raven.dms.auburn.edu [131.204.53.29]) by manatee.dms.auburn.edu (8.12.10/8.12.10) with ESMTP id j5LJ2GCK024760; Tue, 21 Jun 2005 14:02:16 -0500 (CDT) Original-Received: (from teirllm@localhost) by raven.dms.auburn.edu (8.11.7p1+Sun/8.11.7) id j5LJ0ls23408; Tue, 21 Jun 2005 14:00:47 -0500 (CDT) X-Authentication-Warning: raven.dms.auburn.edu: teirllm set sender to teirllm@dms.auburn.edu using -f Original-To: ttn@gnu.org In-reply-to: (message from Thien-Thi Nguyen on 21 Jun 2005 12:35:39 -0400) 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:39244 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:39244 Thien-Thi Nguyen wrote: an index of -1 returns the "oldest" element. so you could just `(ring-ref ring -1)' until the ring is exhausted, obviating both `nreverse' and `var' reference, while keeping the abstraction. ring-ref does not rotate the ring, nor does it "exhaust" it. Maybe you mean `ring-remove', but that would force me to copy the ring first. The abstraction involves overhead, slowing the function down by a factor of slightly more than 2.2. Apparently the abstraction does more to confuse people (making them believe the algorithm is quadratic) than to enlighten them. The aref makes it clear that the algorithm is linear. I still propose to install the function I proposed in my last message. Here are timings for different versions, running ring-elements ten thousand times on a ring of length 1000 on a 1.7 GHZ dual Intel Xeon: Original "abstract" nreverse version: (defun old-ring-elements (ring) "Return a list of the elements of RING in order, newest first." (let (lst) (dotimes (var (ring-length ring)) (push (ring-ref ring var) lst)) (nreverse lst))) 50 secomds Avoiding nreverse, keeping "abstraction": (defun my-ring-elements (ring) "Return a list of the elements of RING in order, newest first." (let (lst) (dotimes (var (ring-length ring) lst) (push (ring-ref ring (- -1 var)) lst)))) 51 seconds. nreverse is a primitive running a very efficient algorithm, it makes no sense to avoid it just for efficiency reasons. This is the function I still propose to install: (defun ring-elements (ring) "Return a list of the elements of RING, in order, newest first." (let ((start (car ring)) (size (ring-size ring)) (vect (cddr ring)) lst) (dotimes (var (cadr ring) lst) (push (aref vect (mod (+ start var) size)) lst)))) 23 seconds, better by a factor of 2.2. The following does still _slightly_ better for this test case, but at a real price in transparency. I believe that it performs a lot more operations than the function I propose to install, but it runs slightly faster, because more operations are performed inside primitives. (defun new-ring-elements (ring) "Return a list of the elements of RING in order, newest first." (let ((lst (mapcar #'identity (cddr ring))) (tot (+ (car ring) (cadr ring))) (size (ring-size ring))) (if (>= size tot) (nreverse (nbutlast (nthcdr (car ring) lst) (- size tot))) (nconc (nreverse (butlast lst (- (* 2 size) tot))) (nreverse (nthcdr (car ring) lst)))))) 20 seconds. If one _really_ cares about efficiency, the thing to do would be to take the function I propose to install and write it in C, but given the fact that `ring-elements' is not even used anywhere in the Emacs sources, this would not seem warranted. Sincerely, Luc.