From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.devel Subject: Re: [Emacs-diffs] /srv/bzr/emacs/trunk r107377: * src/lisp.h: Improve comment about USE_LSB_TAG. Date: Wed, 22 Feb 2012 22:31:55 -0800 Organization: UCLA Computer Science Department Message-ID: <4F45DD5B.3010801@cs.ucla.edu> References: <4F459455.8070206@verizon.net> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1329978727 29840 80.91.229.3 (23 Feb 2012 06:32:07 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 23 Feb 2012 06:32:07 +0000 (UTC) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Feb 23 07:32:06 2012 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1S0SDm-0001Re-2O for ged-emacs-devel@m.gmane.org; Thu, 23 Feb 2012 07:32:06 +0100 Original-Received: from localhost ([::1]:56012 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S0SDl-0002Os-Hb for ged-emacs-devel@m.gmane.org; Thu, 23 Feb 2012 01:32:05 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:42597) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S0SDe-0002OY-DU for emacs-devel@gnu.org; Thu, 23 Feb 2012 01:32:04 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1S0SDa-0000UH-2X for emacs-devel@gnu.org; Thu, 23 Feb 2012 01:31:58 -0500 Original-Received: from smtp.cs.ucla.edu ([131.179.128.62]:37842) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S0SDZ-0000Tz-Rp for emacs-devel@gnu.org; Thu, 23 Feb 2012 01:31:54 -0500 Original-Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id B679FA60001; Wed, 22 Feb 2012 22:31:52 -0800 (PST) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Original-Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id oC9Zs14SFyrU; Wed, 22 Feb 2012 22:31:51 -0800 (PST) Original-Received: from [192.168.1.10] (pool-71-189-109-235.lsanca.fios.verizon.net [71.189.109.235]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 09BEE39E8007; Wed, 22 Feb 2012 22:31:51 -0800 (PST) User-Agent: Mozilla/5.0 (X11; Linux i686; rv:10.0.2) Gecko/20120216 Thunderbird/10.0.2 In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 131.179.128.62 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:148720 Archived-At: On 02/22/2012 07:15 PM, Stefan Monnier wrote: >> > That patch would be more intrusive. > Arguably, yes, but it would have the advantage to attack more precisely > the actual core of the problem, so it "reifies" in the code our > deeper understanding of the problem. I don't know what you mean by "actual core". As I understand it the change you're proposing would require an O(N**2) pass through a stack with N 32-bit words (assuming 32-bit registers and 64-bit EMACS_INT). This is because EMACS_INT halves may be stored independently, and we have no control over where the halves go. So we have to check all pairs of halves. (In a weird machine with 32-bit registers and 128-bit EMACS_INT, the algorithm would be O(N**4); more generally the algorithm would be O(N**K) where K is the number of registers needed to represent an EMACS_INT.) Such an approach would be tricky and slow compared to the current approach, which is a simple O(N) pass through the stack. Regardless of whether the O(N**K) algorithm would be a better "reification", this one is an easy call: let's just keep doing things the O(N) way, as that's simpler and faster. > I'm not sure why you think this patch is "simpler and faster", > since AFAICT it does not solve the original problem, The current Emacs trunk already solves the original problem (Bug#10780), since it has the patch in bzr 107358, and we've verified that that patch fixes Bug#10780. This further patch does not (and is not intended to) solve the original problem. It merely makes Emacs faster and smaller, while continuing to solve the original problem. This is because when (defined USE_LSB_TAG || UINTPTR_MAX >> VALBITS != 0) is false, the mark_maybe_object loop doesn't mark anything that isn't already being marked by the mark_maybe_pointer loop, so the mark_maybe_object loop can be elided safely. > As for that change, the reasoning for why it's correct doesn't seem > obvious to me (I understand why it's correct in the current > WIDE_EMACS_INT case, but generalizing from that to the case > "UINTPTR_MAX >> VALBITS != 0" seems risky). I don't understand what you mean by "generalizing"; can you give an example of the more-general situation you're worried about? Are you worried that pointers might be aligned more-strictly than EMACS_INT values? No current Emacs porting target does that, and it's hard to imagine that any ever will; but if that's the worry, there's a simple way to check for it, at zero runtime cost. Please see the following improved version of the patch, which also adds a comment to try to explain better why the patch is valid. --- src/alloc.c 2012-01-19 07:21:25 +0000 +++ src/alloc.c 2012-02-23 05:43:52 +0000 @@ -4268,10 +4268,19 @@ mark_memory (void *start, void *end) end = tem; } +#if defined USE_LSB_TAG || UINTPTR_MAX >> VALBITS != 0 /* Mark Lisp_Objects. */ for (p = start; (void *) p < end; p++) for (i = 0; i < sizeof *p; i += GC_LISP_OBJECT_ALIGNMENT) mark_maybe_object (*(Lisp_Object *) ((char *) p + i)); +#else + /* The mark_maybe_pointer loop will suffice, since it will recognize + the bottom bits of any Lisp_Object containing a pointer, if we + can assume that Lisp_Object values are aligned at least as + strictly as pointers. Although this assumption is true on all + practical Emacs porting targets, check it anyway, to be safer. */ + { verify (GC_LISP_OBJECT_ALIGNMENT % GC_POINTER_ALIGNMENT == 0); } +#endif /* Mark Lisp data pointed to. This is necessary because, in some situations, the C compiler optimizes Lisp objects away, so that