From: Paul Eggert <eggert@cs.ucla.edu>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: emacs-devel@gnu.org
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 [thread overview]
Message-ID: <4F45DD5B.3010801@cs.ucla.edu> (raw)
In-Reply-To: <jwvaa4axnig.fsf-monnier+emacs@gnu.org>
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
next prev parent reply other threads:[~2012-02-23 6:31 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <E1S0EsZ-0006bE-5w@vcs.savannah.gnu.org>
2012-02-22 20:25 ` [Emacs-diffs] /srv/bzr/emacs/trunk r107377: * src/lisp.h: Improve comment about USE_LSB_TAG Stefan Monnier
2012-02-23 1:20 ` Paul Eggert
2012-02-23 3:15 ` Stefan Monnier
2012-02-23 6:31 ` Paul Eggert [this message]
2012-02-23 7:42 ` Stefan Monnier
2012-02-25 7:00 ` Paul Eggert
2012-02-25 10:06 ` Stefan Monnier
2012-02-25 19:46 ` Paul Eggert
2012-02-23 3:57 ` YAMAMOTO Mitsuharu
2012-02-23 6:28 ` Paul Eggert
2012-05-09 17:56 ` Paul Eggert
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4F45DD5B.3010801@cs.ucla.edu \
--to=eggert@cs.ucla.edu \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.