From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: [PATCH] use tail pointer for LOOP Date: Fri, 18 Jun 2010 09:40:01 -0400 Message-ID: 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> <87eig4rf8l.fsf@lola.goethe.zz> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1276868421 3442 80.91.229.12 (18 Jun 2010 13:40:21 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 18 Jun 2010 13:40:21 +0000 (UTC) Cc: emacs-devel@gnu.org To: David Kastrup Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Jun 18 15:40:20 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 1OPbnt-0002bQ-UG for ged-emacs-devel@m.gmane.org; Fri, 18 Jun 2010 15:40:18 +0200 Original-Received: from localhost ([127.0.0.1]:42364 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OPbnt-0003da-AD for ged-emacs-devel@m.gmane.org; Fri, 18 Jun 2010 09:40:17 -0400 Original-Received: from [140.186.70.92] (port=59384 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OPbnn-0003cx-Va for emacs-devel@gnu.org; Fri, 18 Jun 2010 09:40:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OPbnj-0001ft-OK for emacs-devel@gnu.org; Fri, 18 Jun 2010 09:40:11 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.183]:47981 helo=ironport2-out.pppoe.ca) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OPbnf-0001ex-0g; Fri, 18 Jun 2010 09:40:03 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvsEAJcTG0xLd+Hj/2dsb2JhbACfDnLBWIUbBI0Y X-IronPort-AV: E=Sophos;i="4.53,439,1272859200"; d="scan'208";a="68345883" Original-Received: from 75-119-225-227.dsl.teksavvy.com (HELO pastel.home) ([75.119.225.227]) by ironport2-out.pppoe.ca with ESMTP; 18 Jun 2010 09:40:02 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id 526A97F26; Fri, 18 Jun 2010 09:40:01 -0400 (EDT) In-Reply-To: <87eig4rf8l.fsf@lola.goethe.zz> (David Kastrup's message of "Fri, 18 Jun 2010 09:07:06 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. 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:126152 Archived-At: > 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. Doesn't have to be as drastic as "virtual memory". If the list is long enough to overflow some level of the memory hierarchy, then the tail-pointer approach has a fighting change. Hopefully such lists are really rare (lists that overflow the L1 cache are probably fairly common (about 1000 elements), but the speed difference between L1 and L2 cache is probably not sufficient to defeat nreverse). Stefan