Re: [Emacs-diffs] /srv/bzr/emacs/trunk r107377: * src/lisp.h: Improve comment about USE_LSB_TAG.

[Paul Eggert <eggert@cs.ucla.edu>]

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