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: Fri, 18 Jun 2010 09:07:06 +0200 Organization: Organization?!? Message-ID: <87eig4rf8l.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> <87fx0msv9z.fsf@lola.goethe.zz> <20100617051021.GA26623@tomas> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1276844976 15837 80.91.229.12 (18 Jun 2010 07:09:36 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 18 Jun 2010 07:09:36 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Jun 18 09:09:31 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 1OPVhj-00080W-7h for ged-emacs-devel@m.gmane.org; Fri, 18 Jun 2010 09:09:31 +0200 Original-Received: from localhost ([127.0.0.1]:37074 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OPVhi-0006pZ-FU for ged-emacs-devel@m.gmane.org; Fri, 18 Jun 2010 03:09:30 -0400 Original-Received: from [140.186.70.92] (port=44559 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OPVff-0005Lu-BE for emacs-devel@gnu.org; Fri, 18 Jun 2010 03:07:24 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OPVfc-0003vl-Ji for emacs-devel@gnu.org; Fri, 18 Jun 2010 03:07:22 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:54277) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OPVfc-0003vC-EQ for emacs-devel@gnu.org; Fri, 18 Jun 2010 03:07:20 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1OPVfa-00076i-7I for emacs-devel@gnu.org; Fri, 18 Jun 2010 09:07:18 +0200 Original-Received: from p508ec48d.dip.t-dialin.net ([80.142.196.141]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 18 Jun 2010 09:07:18 +0200 Original-Received: from dak by p508ec48d.dip.t-dialin.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 18 Jun 2010 09:07:18 +0200 X-Injected-Via-Gmane: http://gmane.org/ connect(): No such file or directory Original-Lines: 21 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: p508ec48d.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:Q1FuyuEgg4+FCHFY2aQlqSn01i8= 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:126128 Archived-At: Stefan Monnier writes: >> Reverse: (1.006534 3 0.682734) >> Tail pointer: (1.305476 4 0.9159619999999986) > >> Still, reversing seems to be worth it (by some 30 percent). Unless we >> find some way to streamline the tail pointer better. > > That's really not surprising: count the number of function calls and > you'll see that the nreverse way is likely to win every time, simply > because it suffers about half as much from the interpretation overhead. nreverse is also cons-neutral. The only situation where I'd expect it to be able to lose is under virtual memory pressure, where the nreverse approach has to cons the list forwards when building, and again backwards when reversing the conses. A tail pointer approach will traverse the list just once. So if it does not fit in real memory, tail pointers may cause half the page faults than nreverse does. -- David Kastrup