From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: [PATCH] use tail pointer for LOOP Date: Wed, 16 Jun 2010 20:10:48 +0200 Organization: Organization?!? Message-ID: <87fx0msv9z.fsf@lola.goethe.zz> References: <4C018D79.7040409@censorshipresearch.org> <4C018FD3.1020305@censorshipresearch.org> <4C01AA28.6030002@censorshipresearch.org> <9718A5AD-7A74-470B-A32D-DA14266506A3@raeburn.org> <4C01B609.6070303@censorshipresearch.org> <20100616174420.GA2847@tomas> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1276711891 20255 80.91.229.12 (16 Jun 2010 18:11:31 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 16 Jun 2010 18:11:31 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Jun 16 20:11:30 2010 connect(): No such file or directory 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 1OOx5F-0003lR-Hb for ged-emacs-devel@m.gmane.org; Wed, 16 Jun 2010 20:11:29 +0200 Original-Received: from localhost ([127.0.0.1]:35029 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OOx5E-0005Sb-HS for ged-emacs-devel@m.gmane.org; Wed, 16 Jun 2010 14:11:28 -0400 Original-Received: from [140.186.70.92] (port=44923 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OOx4v-0005G9-0r for emacs-devel@gnu.org; Wed, 16 Jun 2010 14:11:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OOx4o-0006jy-JR for emacs-devel@gnu.org; Wed, 16 Jun 2010 14:11:07 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:36010) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OOx4o-0006jT-8R for emacs-devel@gnu.org; Wed, 16 Jun 2010 14:11:02 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1OOx4l-0003Ym-CT for emacs-devel@gnu.org; Wed, 16 Jun 2010 20:10:59 +0200 Original-Received: from p508ed3bc.dip.t-dialin.net ([80.142.211.188]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Wed, 16 Jun 2010 20:10:59 +0200 Original-Received: from dak by p508ed3bc.dip.t-dialin.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Wed, 16 Jun 2010 20:10:59 +0200 X-Injected-Via-Gmane: http://gmane.org/ connect(): No such file or directory Original-Lines: 64 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: p508ed3bc.dip.t-dialin.net X-Face: 2FEFf>]>q>2iw=B6, xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN; i"; /yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) Cancel-Lock: sha1:ooWMCA+VrzWFG1hDt6WhZ0PoYjQ= 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:126027 Archived-At: tomas@tuxteam.de writes: > On Sat, May 29, 2010 at 08:49:13PM -0400, Daniel Colascione wrote: >> On 5/29/10 8:45 PM, Ken Raeburn wrote: > > [...] > >> > Is it any faster to build the list in order? (Simply avoiding nreverse >> > obviously makes things a little faster, but are you doing more work each >> > time around the loop to maintain and use the tail pointer?) >> >> It's only a little bit more work to use the tail pointer [...] > > This has intrigued me for quite a while. > > Since I really should be doing tax declarations, I couldn't hold back for > longer -- here is my (very unscientific) approach, to help you all > procrastinate a bit too: > > | (defun copy1 (lst) > | "Build up a copy of lst by consing up in reverse order, then > | reversing" > | (let ((res)) > | (while lst > | (setq res (cons (car lst) res) > | lst (cdr lst))) > | (nreverse res))) > | > | (defun copy2 (lst) > | "Build up a copy of lst by consing up in order, keeping a tail > | pointer" > | (when lst > | (let ((res) (tail)) > | (setq res (cons (car lst) nil) > | tail res > | lst (cdr lst)) > | (while lst > | (setcdr tail (cons (car lst) nil)) > | (setq tail (cdr tail) > | lst (cdr lst))) > | res))) > | > | (defun runtwo (n) > | (let ((lst)) > | (while (> n 0) > | (setq lst (cons n lst) > | n (1- n))) > | (garbage-collect) > | (cons (benchmark-run (copy1 lst)) > | (benchmark-run (copy2 lst))))) > | > | (runtwo 1000000) > > (Maybe the tail pointer version could be done more elegantly: I'd be > delighted to be taught more :) > > Turns out that the nreverse version is a tad faster (on my hardware, one > of those Atom based netbooks, in case it matters) -- about 2.1 versus > 2.7 seconds for a list of size 10^6. Garbage collections are comparable. Did you byte-compile? -- David Kastrup