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

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

[Stefan Monnier]

> +/* On hosts where VALBITS is greater than the pointer width in bits,
> +   USE_LSB_TAG is:
> +    a. unnecessary, because the top bits of an EMACS_INT are unused,
> +    b. slower, because it typically requires extra masking, and

Is this just a gut-feeling, or is there some actual measurement behind
this assertion?

What kind of extra masking are you referring to?  The XFASTINT?
Note that the LSB masking can be cheaper than the MSB masking (because
the mask is a smaller value which fits more easily in an immediate
value).

I haven't made any measurements (the motivation for LSB tags was not
speed but addressing range), but I'd find it surprising if LSB tags are
generally slower.

> +    c. harmful, because it can create Lisp_Object values that are so scrambled
> +       that mark_maybe_object cannot decipher them.  mark_maybe_object assumes
> +       that EMACS_INT values are contiguous, but a host where EMACS_INT is
> +       wider than a pointer might allocate the top half of an EMACS_INT in
> +       (say) a 32-bit word on the stack, putting the bottom half in a 32-bit
> +       register that is saved elsewhere in a jmp_buf.  When this happens,
> +       since USE_LSB_TAG is not defined the bottom half alone is a valid
> +       pointer that mark_maybe_pointer can follow; but if USE_LSB_TAG were
> +       defined, the bottom half would not be a valid pointer and neither
> +       mark_maybe_object nor mark_maybe_pointer would follow it.

I see.  So "VALBITS is greater than the pointer width in bits" is not
the exactly right condition (e.g. if we have 48bit pointers and 61
VALBITS then the problem should not appear).

Maybe a better fix is to add code to the stack marking loop, conditional
on WIDE_EMACS_INT and USE_LSB_TAGS, which passes pointer-sized
words to mark_maybe_object after expanding them to EMACS_INT size.


        Stefan

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

[Paul Eggert]

On 02/22/2012 12:25 PM, Stefan Monnier wrote:
>> +/* On hosts where VALBITS is greater than the pointer width in bits,
>> +   USE_LSB_TAG is:
>> +    a. unnecessary, because the top bits of an EMACS_INT are unused,
>> +    b. slower, because it typically requires extra masking, and
> 
> Is this just a gut-feeling, or is there some actual measurement behind
> this assertion?

Originally the former, but (now that you asked) the latter.

On my host the expression (benchmark 1000000) ran about 8% faster
without USE_LSB_TAG.  This benchmark merely tests the speed of 'aset';
it is defined by the source code at the end of this message (not
byte-compiled); this was a random benchmark I was using for something
else.  I benchmarked Emacs trunk bzr 107379 configured
--with-wide-int, using gcc -m32 (GCC 4.6.2), and a Fedora 15 x86-64
kernel (2.6.41.1-1.fc15.x86_64 SMP).

The executable size is measurably larger, too: src/temacs's text size
is 0.94% larger when USE_LSB_TAG is defined.

I'm pretty sure I'll get similar results with other benchmarks.
I don't see how USE_LSB_TAG could outperform !USE_LSB_TAG on my platform.


> What kind of extra masking are you referring to?  The XFASTINT?
> Note that the LSB masking can be cheaper than the MSB masking

No, it's XPNTR that's faster, because its masking comes for free --
zero runtime overhead on my platform.


> So "VALBITS is greater than the pointer width in bits" is not
> the exactly right condition (e.g. if we have 48bit pointers and 61
> VALBITS then the problem should not appear).

Most likely not, true.  The current code is conservative.  I don't
know of any real platform where the conservatism matters, though.


> Maybe a better fix is to add code to the stack marking loop, conditional
> on WIDE_EMACS_INT and USE_LSB_TAGS, which passes pointer-sized
> words to mark_maybe_object after expanding them to EMACS_INT size.

That patch would be more intrusive.  Plus, the following (further)
patch is simpler and faster.  This patch is purely a performance
improvement so I didn't install it (was planning to do it after 24.1
comes out, but if you like I can do it now....).

=== modified file 'src/alloc.c'
--- src/alloc.c	2012-01-19 07:21:25 +0000
+++ src/alloc.c	2012-02-23 01:10:15 +0000
@@ -4268,10 +4268,12 @@
       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));
+#endif
 
   /* Mark Lisp data pointed to.  This is necessary because, in some
      situations, the C compiler optimizes Lisp objects away, so that



Here's the benchmark code I mentioned earlier.

(defun benchmark-with-aset (n)
  (let ((start (float-time (get-internal-run-time)))
        (v (make-vector 1 0))
        (i 0))
    (while (< i n)
      (aset v 0 1)
      (setq i (1+ i)))
    (- (float-time (get-internal-run-time)) start)))

(defun benchmark-without-aset (n)
  (let ((start (float-time (get-internal-run-time)))
        (v (make-vector 1 0))
        (i 0))
    (while (< i n)
      (setq i (1+ i)))
    (- (float-time (get-internal-run-time)) start)))

(defun benchmark (n)
  (- (benchmark-with-aset n)
     (benchmark-without-aset n)))

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

[Stefan Monnier]

>> What kind of extra masking are you referring to?  The XFASTINT?
>> Note that the LSB masking can be cheaper than the MSB masking
> No, it's XPNTR that's faster, because its masking comes for free --
> zero runtime overhead on my platform.

Oh, interesting.  The masking code is not null, but the compiler manages
to compile it away because it masks bits that are outside the range
of pointers.

>> So "VALBITS is greater than the pointer width in bits" is not
>> the exactly right condition (e.g. if we have 48bit pointers and 61
>> VALBITS then the problem should not appear).
> Most likely not, true.  The current code is conservative.  I don't
> know of any real platform where the conservatism matters, though.

No, indeed it doesn't matter in practical terms, it only matters if
you try to understand what's really going on.

>> Maybe a better fix is to add code to the stack marking loop, conditional
>> on WIDE_EMACS_INT and USE_LSB_TAGS, which passes pointer-sized
>> words to mark_maybe_object after expanding them to EMACS_INT size.
> 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.  IOW it makes it less likely that
someone later on won't understand what's going on.

> Plus, the following (further) patch is simpler and faster.  This patch
> is purely a performance improvement so I didn't install it (was
> planning to do it after 24.1 comes out, but if you like I can do it
> now....).

> +#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));
> +#endif
 
I'm not sure why you think this patch is "simpler and faster", since
AFAICT it does not solve the original problem, whereas the change
I suggested does (or at least, should), so they're
basically incomparable.

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).  So I'm not in favor of this
optimization as it is (of course not for 24.1, but probably not for 24.2
either).


        Stefan

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

[YAMAMOTO Mitsuharu]

>>>>> On Wed, 22 Feb 2012 17:20:21 -0800, Paul Eggert <paul.eggert@verizon.net> said:

> I'm pretty sure I'll get similar results with other benchmarks.  I
> don't see how USE_LSB_TAG could outperform !USE_LSB_TAG on my
> platform.


>> What kind of extra masking are you referring to?  The XFASTINT?
>> Note that the LSB masking can be cheaper than the MSB masking

> No, it's XPNTR that's faster, because its masking comes for free --
> zero runtime overhead on my platform.

Does "untagging by subtraction instead of masking" improve the
performance of USE_LSB_TAG in your platform?  The intention is to hide
the masking of XPNTR into the dereference and struct member access
that typically follow.

http://lists.gnu.org/archive/html/emacs-devel/2008-01/msg01876.html

The patch below is against Emacs 24.0.93.

				     YAMAMOTO Mitsuharu
				mituharu@math.s.chiba-u.ac.jp

=== modified file 'src/font.h'
*** src/font.h	2012-01-19 07:21:25 +0000
--- src/font.h	2012-02-15 04:22:59 +0000
*************** struct font_bitmap
*** 469,479 ****
    } while (0)
  
  #define XFONT_SPEC(p)	\
!   (eassert (FONT_SPEC_P(p)), (struct font_spec *) XPNTR (p))
  #define XFONT_ENTITY(p)	\
!   (eassert (FONT_ENTITY_P(p)), (struct font_entity *) XPNTR (p))
  #define XFONT_OBJECT(p)	\
!   (eassert (FONT_OBJECT_P(p)), (struct font *) XPNTR (p))
  #define XSETFONT(a, b) (XSETPSEUDOVECTOR (a, b, PVEC_FONT))
  
  /* Number of pt per inch (from the TeXbook).  */
--- 469,480 ----
    } while (0)
  
  #define XFONT_SPEC(p)	\
!   (eassert (FONT_SPEC_P(p)), (struct font_spec *) XUNTAG (p, Lisp_Vectorlike))
  #define XFONT_ENTITY(p)	\
!   (eassert (FONT_ENTITY_P(p)), \
!    (struct font_entity *) XUNTAG (p, Lisp_Vectorlike))
  #define XFONT_OBJECT(p)	\
!   (eassert (FONT_OBJECT_P(p)), (struct font *) XUNTAG (p, Lisp_Vectorlike))
  #define XSETFONT(a, b) (XSETPSEUDOVECTOR (a, b, PVEC_FONT))
  
  /* Number of pt per inch (from the TeXbook).  */

=== modified file 'src/frame.h'
*** src/frame.h	2012-01-19 07:21:25 +0000
--- src/frame.h	2012-02-01 12:37:39 +0000
*************** struct frame
*** 501,507 ****
  
  typedef struct frame *FRAME_PTR;
  
! #define XFRAME(p) (eassert (FRAMEP(p)),(struct frame *) XPNTR (p))
  #define XSETFRAME(a, b) (XSETPSEUDOVECTOR (a, b, PVEC_FRAME))
  
  /* Given a window, return its frame as a Lisp_Object.  */
--- 505,512 ----
  
  typedef struct frame *FRAME_PTR;
  
! #define XFRAME(p) (eassert (FRAMEP(p)), \
! 		   (struct frame *) XUNTAG (p, Lisp_Vectorlike))
  #define XSETFRAME(a, b) (XSETPSEUDOVECTOR (a, b, PVEC_FRAME))
  
  /* Given a window, return its frame as a Lisp_Object.  */

=== modified file 'src/lisp.h'
*** src/lisp.h	2012-01-19 07:21:25 +0000
--- src/lisp.h	2012-02-23 03:46:12 +0000
*************** enum pvec_type
*** 469,474 ****
--- 469,475 ----
       (var) = (type) | (intptr_t) (ptr))
  
  #define XPNTR(a) ((intptr_t) ((a) & ~TYPEMASK))
+ #define XUNTAG(a, type) ((uintptr_t) (a) - (type))
  
  #else  /* not USE_LSB_TAG */
  
*************** enum pvec_type
*** 511,516 ****
--- 512,518 ----
  #else
  #define XPNTR(a) ((uintptr_t) ((a) & VALMASK))
  #endif
+ #define XUNTAG(a, type) XPNTR (a)
  
  #endif /* not USE_LSB_TAG */
  
*************** extern Lisp_Object make_number (EMACS_IN
*** 601,615 ****
  
  /* Extract a value or address from a Lisp_Object.  */
  
! #define XCONS(a) (eassert (CONSP (a)), (struct Lisp_Cons *) XPNTR (a))
! #define XVECTOR(a) (eassert (VECTORLIKEP (a)), (struct Lisp_Vector *) XPNTR (a))
! #define XSTRING(a) (eassert (STRINGP (a)), (struct Lisp_String *) XPNTR (a))
! #define XSYMBOL(a) (eassert (SYMBOLP (a)), (struct Lisp_Symbol *) XPNTR (a))
! #define XFLOAT(a) (eassert (FLOATP (a)), (struct Lisp_Float *) XPNTR (a))
  
  /* Misc types.  */
  
! #define XMISC(a)   ((union Lisp_Misc *) XPNTR (a))
  #define XMISCANY(a)	(eassert (MISCP (a)), &(XMISC (a)->u_any))
  #define XMISCTYPE(a)   (XMISCANY (a)->type)
  #define XMARKER(a)	(eassert (MARKERP (a)), &(XMISC (a)->u_marker))
--- 603,622 ----
  
  /* Extract a value or address from a Lisp_Object.  */
  
! #define XCONS(a) (eassert (CONSP(a)), \
! 		  (struct Lisp_Cons *) XUNTAG (a, Lisp_Cons))
! #define XVECTOR(a) (eassert (VECTORLIKEP(a)), \
! 		    (struct Lisp_Vector *) XUNTAG (a, Lisp_Vectorlike))
! #define XSTRING(a) (eassert (STRINGP(a)), \
! 		    (struct Lisp_String *) XUNTAG (a, Lisp_String))
! #define XSYMBOL(a) (eassert (SYMBOLP(a)), \
! 		    (struct Lisp_Symbol *) XUNTAG (a, Lisp_Symbol))
! #define XFLOAT(a) (eassert (FLOATP(a)), \
! 		   (struct Lisp_Float *) XUNTAG (a, Lisp_Float))
  
  /* Misc types.  */
  
! #define XMISC(a)   ((union Lisp_Misc *) XUNTAG (a, Lisp_Misc))
  #define XMISCANY(a)	(eassert (MISCP (a)), &(XMISC (a)->u_any))
  #define XMISCTYPE(a)   (XMISCANY (a)->type)
  #define XMARKER(a)	(eassert (MARKERP (a)), &(XMISC (a)->u_marker))
*************** extern Lisp_Object make_number (EMACS_IN
*** 629,642 ****
  
  /* Pseudovector types.  */
  
! #define XPROCESS(a) (eassert (PROCESSP (a)), (struct Lisp_Process *) XPNTR (a))
! #define XWINDOW(a) (eassert (WINDOWP (a)), (struct window *) XPNTR (a))
! #define XTERMINAL(a) (eassert (TERMINALP (a)), (struct terminal *) XPNTR (a))
! #define XSUBR(a) (eassert (SUBRP (a)), (struct Lisp_Subr *) XPNTR (a))
! #define XBUFFER(a) (eassert (BUFFERP (a)), (struct buffer *) XPNTR (a))
! #define XCHAR_TABLE(a) (eassert (CHAR_TABLE_P (a)), (struct Lisp_Char_Table *) XPNTR (a))
! #define XSUB_CHAR_TABLE(a) (eassert (SUB_CHAR_TABLE_P (a)), (struct Lisp_Sub_Char_Table *) XPNTR (a))
! #define XBOOL_VECTOR(a) (eassert (BOOL_VECTOR_P (a)), (struct Lisp_Bool_Vector *) XPNTR (a))
  
  /* Construct a Lisp_Object from a value or address.  */
  
--- 636,657 ----
  
  /* Pseudovector types.  */
  
! #define XPROCESS(a) (eassert (PROCESSP(a)), \
! 		     (struct Lisp_Process *) XUNTAG (a, Lisp_Vectorlike))
! #define XWINDOW(a) (eassert (WINDOWP(a)), \
! 		    (struct window *) XUNTAG (a, Lisp_Vectorlike))
! #define XTERMINAL(a) (eassert (TERMINALP(a)), \
! 		      (struct terminal *) XUNTAG (a, Lisp_Vectorlike))
! #define XSUBR(a) (eassert (SUBRP(a)), \
! 		  (struct Lisp_Subr *) XUNTAG (a, Lisp_Vectorlike))
! #define XBUFFER(a) (eassert (BUFFERP(a)), \
! 		    (struct buffer *) XUNTAG (a, Lisp_Vectorlike))
! #define XCHAR_TABLE(a) (eassert (CHAR_TABLE_P (a)), \
! 			(struct Lisp_Char_Table *) XUNTAG (a, Lisp_Vectorlike))
! #define XSUB_CHAR_TABLE(a) (eassert (SUB_CHAR_TABLE_P (a)), \
! 			    (struct Lisp_Sub_Char_Table *) XUNTAG (a, Lisp_Vectorlike))
! #define XBOOL_VECTOR(a) (eassert (BOOL_VECTOR_P (a)), \
! 			 (struct Lisp_Bool_Vector *) XUNTAG (a, Lisp_Vectorlike))
  
  /* Construct a Lisp_Object from a value or address.  */
  
*************** extern Lisp_Object make_number (EMACS_IN
*** 663,669 ****
  /* The cast to struct vectorlike_header * avoids aliasing issues.  */
  #define XSETPSEUDOVECTOR(a, b, code) \
    XSETTYPED_PSEUDOVECTOR(a, b,       \
! 			 ((struct vectorlike_header *) XPNTR (a))->size, \
  			 code)
  #define XSETTYPED_PSEUDOVECTOR(a, b, size, code)			\
    (XSETVECTOR (a, b),							\
--- 678,684 ----
  /* The cast to struct vectorlike_header * avoids aliasing issues.  */
  #define XSETPSEUDOVECTOR(a, b, code) \
    XSETTYPED_PSEUDOVECTOR(a, b,       \
! 			 ((struct vectorlike_header *) XUNTAG (a, Lisp_Vectorlike))->size, \
  			 code)
  #define XSETTYPED_PSEUDOVECTOR(a, b, size, code)			\
    (XSETVECTOR (a, b),							\
*************** struct Lisp_Hash_Table
*** 1271,1277 ****
  
  
  #define XHASH_TABLE(OBJ) \
!      ((struct Lisp_Hash_Table *) XPNTR (OBJ))
  
  #define XSET_HASH_TABLE(VAR, PTR) \
       (XSETPSEUDOVECTOR (VAR, PTR, PVEC_HASH_TABLE))
--- 1286,1292 ----
  
  
  #define XHASH_TABLE(OBJ) \
!      ((struct Lisp_Hash_Table *) XUNTAG (OBJ, Lisp_Vectorlike))
  
  #define XSET_HASH_TABLE(VAR, PTR) \
       (XSETPSEUDOVECTOR (VAR, PTR, PVEC_HASH_TABLE))
*************** typedef struct {
*** 1738,1744 ****
     code is CODE.  */
  #define TYPED_PSEUDOVECTORP(x, t, code)				\
    (VECTORLIKEP (x)						\
!    && (((((struct t *) XPNTR (x))->size				\
  	 & (PSEUDOVECTOR_FLAG | (code))))			\
         == (PSEUDOVECTOR_FLAG | (code))))
  
--- 1763,1769 ----
     code is CODE.  */
  #define TYPED_PSEUDOVECTORP(x, t, code)				\
    (VECTORLIKEP (x)						\
!    && (((((struct t *) XUNTAG (x, Lisp_Vectorlike))->size	\
  	 & (PSEUDOVECTOR_FLAG | (code))))			\
         == (PSEUDOVECTOR_FLAG | (code))))
  

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

[Paul Eggert]

On 02/22/2012 07:57 PM, YAMAMOTO Mitsuharu wrote:
> Does "untagging by subtraction instead of masking" improve the
> performance of USE_LSB_TAG in your platform?

I'm sure it would, though I haven't measured it.
I'm surprised that this hasn't been implemented in Emacs already.
It's a standard technique (I first saw it in the 1980s), and it's clearly
faster that what Emacs is doing now.  We should look into incorporating it
after 24.1 comes out.

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

[Paul Eggert]

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

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

[Stefan Monnier]

>>> > 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).

No, that would be a "real fix".  What I suggest is just to take the O(N)
pointer-sized entities on the stack, cast them to EMACS_INT, and pass
them to mark_maybe_object.

>> 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?

No, the problem is theoretical: what is the logical justification?

> Are you worried that pointers might be aligned more-strictly
> than EMACS_INT values?

Not really.  I'm just trying to construct a proof in my head that your
optimization is correct, and I can't seem to connect your
hypothesis "UINTPTR_MAX >> VALBITS != 0" with the conclusion.
Your additional alignment hypothesis might be the key, but I'm still
struggling to see how the proof would work.

> +  /* 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); }

I really don't think such complexity is warranted for such a minor
optimization of a compilation option which is currently not enabled
by default.  If/when we enable it by default, we may revisit this
choice, but for now, I'd rather not go there.


        Stefan

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

[Paul Eggert]

On 02/22/2012 11:42 PM, Stefan Monnier wrote:

> What I suggest is just to take the O(N) pointer-sized entities on
> the stack, cast them to EMACS_INT, and pass them to
> mark_maybe_object.

Thanks, I see now.  Something like the following, then.
Yes, that does simplify things.


Generalize fix for crash due to non-contiguous EMACS_INT (Bug#10780).
Suggested by Stefan Monnier in
<http://lists.gnu.org/archive/html/emacs-devel/2012-02/msg00638.html>.
* alloc.c (widen_to_Lisp_Object): New static function.
(POINTERS_MIGHT_HIDE_IN_OBJECTS): New macro.
(mark_memory): Mark Lisp_Objects by fetching pointer words
and widening them to Lisp_Objects.  This works better with
wide integers, and works even if USE_USB_TAG is not defined.
Mark Lisp_Objects only if pointers might hide in objects,
as mark_maybe_pointer will catch them otherwise.
(GC_LISP_OBJECT_ALIGNMENT): Remove; no longer needed.
* s/gnu-linux.h (GC_LISP_OBJECT_ALIGNMENT) [__mc68000__]: Likewise.
=== modified file 'src/alloc.c'
--- src/alloc.c	2012-02-10 18:58:48 +0000
+++ src/alloc.c	2012-02-25 06:48:29 +0000
@@ -1582,6 +1582,21 @@
 }
 #endif
 \f
+/* Convert the pointer-sized word P to EMACS_INT while preserving its
+   type and ptr fields.  */
+static Lisp_Object
+widen_to_Lisp_Object (void *p)
+{
+  intptr_t i = (intptr_t) p;
+#ifdef USE_LISP_UNION_TYPE
+  Lisp_Object obj;
+  obj.i = i;
+  return obj;
+#else
+  return i;
+#endif
+}
+\f
 /***********************************************************************
 			  String Allocation
  ***********************************************************************/
@@ -4236,23 +4251,35 @@
 }


-/* Alignment of Lisp_Object and pointer values.  Use offsetof, as it
-   sometimes returns a smaller alignment than GCC's __alignof__ and
-   mark_memory might miss objects if __alignof__ were used.  For
-   example, on x86 with WIDE_EMACS_INT, __alignof__ (Lisp_Object) is 8
-   but GC_LISP_OBJECT_ALIGNMENT should be 4.  */
-#ifndef GC_LISP_OBJECT_ALIGNMENT
-# define GC_LISP_OBJECT_ALIGNMENT offsetof (struct {char a; Lisp_Object b;}, b)
-#endif
+/* Alignment of pointer values.  Use offsetof, as it sometimes returns
+   a smaller alignment than GCC's __alignof__ and mark_memory might
+   miss objects if __alignof__ were used.  */
 #define GC_POINTER_ALIGNMENT offsetof (struct {char a; void *b;}, b)

+/* Define POINTERS_MIGHT_HIDE_IN_OBJECTS to 1 if marking via C pointers does
+   not suffice, which is the typical case.  */
+#if defined USE_LSB_TAG || UINTPTR_MAX >> VALBITS != 0
+# if !defined USE_LSB_TAG && UINTPTR_MAX >> VALBITS >> GCTYPEBITS != 0
+  /* If tag bits straddle pointer-word boundaries, neither mark_maybe_pointer
+     nor mark_maybe_object can follow the pointers.  This should not occur on
+     any practical porting target.  */
+#  error "MSB type bits straddle pointer-word boundaries"
+# endif
+  /* Marking via C pointers does not suffice, because Lisp_Objects contain
+     pointer words that hold pointers ORed with type bits.  */
+# define POINTERS_MIGHT_HIDE_IN_OBJECTS 1
+#else
+  /* Marking via C pointers suffices, because Lisp_Objects contain pointer
+     words that hold unmodified pointers.  */
+# define POINTERS_MIGHT_HIDE_IN_OBJECTS 0
+#endif
+
 /* Mark Lisp objects referenced from the address range START+OFFSET..END
    or END+OFFSET..START. */

 static void
 mark_memory (void *start, void *end)
 {
-  Lisp_Object *p;
   void **pp;
   int i;

@@ -4269,11 +4296,6 @@
       end = tem;
     }

-  /* 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));
-
   /* Mark Lisp data pointed to.  This is necessary because, in some
      situations, the C compiler optimizes Lisp objects away, so that
      only a pointer to them remains.  Example:
@@ -4294,7 +4316,12 @@

   for (pp = start; (void *) pp < end; pp++)
     for (i = 0; i < sizeof *pp; i += GC_POINTER_ALIGNMENT)
-      mark_maybe_pointer (*(void **) ((char *) pp + i));
+      {
+	void *p = *(void **) ((char *) pp + i);
+	mark_maybe_pointer (p);
+	if (POINTERS_MIGHT_HIDE_IN_OBJECTS)
+	  mark_maybe_object (widen_to_Lisp_Object (p));
+      }
 }

 /* setjmp will work with GCC unless NON_SAVING_SETJMP is defined in

=== modified file 'src/s/gnu-linux.h'
--- src/s/gnu-linux.h	2012-01-19 07:21:25 +0000
+++ src/s/gnu-linux.h	2012-02-25 06:48:29 +0000
@@ -146,9 +146,6 @@
     || defined __ia64__ || defined __sh__
 #define GC_SETJMP_WORKS 1
 #define GC_MARK_STACK GC_MAKE_GCPROS_NOOPS
-#ifdef __mc68000__
-#define GC_LISP_OBJECT_ALIGNMENT 2
-#endif
 #ifdef __ia64__
 #define GC_MARK_SECONDARY_STACK()				\
   do {								\

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

[Stefan Monnier]

>> What I suggest is just to take the O(N) pointer-sized entities on
>> the stack, cast them to EMACS_INT, and pass them to
>> mark_maybe_object.
> Thanks, I see now.  Something like the following, then.
> Yes, that does simplify things.

Your patch doesn't look bad, but is too intrusive for 24.1.
I think for 24.1 we can install one that just does:

>    for (pp = start; (void *) pp < end; pp++)
>      for (i = 0; i < sizeof *pp; i += GC_POINTER_ALIGNMENT)
> -      mark_maybe_pointer (*(void **) ((char *) pp + i));
> +      {
> +	void *p = *(void **) ((char *) pp + i);
> +	mark_maybe_pointer (p);
> + #ifdef WIDE_EMACS_INT
> +	  mark_maybe_object (widen_to_Lisp_Object (p));
> + #endif
> +      }
>  }

With an appropriate comment (mostly moved from the USE_LSB_TAG comment
which can be trimmed down since the avoidance of USE_LSB_TAG on
WIDE_EMACS_INT is not performed for correctness reasons any more).


        Stefan

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

[Paul Eggert]

OK, thanks, I installed a patch along the lines you suggested
into the trunk, as bzr 107429.  The patch differs from your
suggestion only in that it uses a different name for the local
variable (to avoid shadowing warnings) and it uses the test
(sizeof (void *) < sizeof (Lisp_Object)) rather than
(defined WIDE_EMACS_INT) as this identifies the
problem more accurately (the problem can occur even
if WIDE_EMACS_INT is not defined).

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

[Paul Eggert]

On 02/22/2012 10:28 PM, Paul Eggert wrote:
> On 02/22/2012 07:57 PM, YAMAMOTO Mitsuharu wrote:
>> Does "untagging by subtraction instead of masking" improve the
>> performance of USE_LSB_TAG in your platform?
> 
> I'm sure it would, though I haven't measured it.
> I'm surprised that this hasn't been implemented in Emacs already.

I finally got around to measuring it, and it's a significant
win on at least x86-64 and x86.  I can't imagine a realistic
platform where it would lose.  So I installed the following patch
on the trunk.  Thanks again for reminding us about this.

======

Untag more efficiently if USE_LSB_TAG.
This is based on a proposal by YAMAMOTO Mitsuharu in
<http://lists.gnu.org/archive/html/emacs-devel/2008-01/msg01876.html>.
For an admittedly artificial (nth 8000 longlist) benchmark on
Fedora 15 x86-64, this yields a 25% CPU speedup.  Also, it shrinks
Emacs's overall text size by 1%.
* lisp.h (XUNTAG): New macro.
(XCONS, XVECTOR, XSTRING, XSYMBOL, XFLOAT, XMISC, XPROCESS, XWINDOW)
(XTERMINAL, XSUBR, XBUFFER, XCHAR_TABLE, XSUB_CHAR_TABLE, XBOOL_VECTOR)
(XSETTYPED_PSEUDOVECTOR, XHASH_TABLE, TYPED_PSEUDOVECTORP): Use it.
* eval.c (Fautoload):
* font.h (XFONT_SPEC, XFONT_ENTITY, XFONT_OBJECT):
* frame.h (XFRAME): Use XUNTAG.
=== modified file 'src/eval.c'
--- src/eval.c	2012-04-09 13:05:48 +0000
+++ src/eval.c	2012-05-09 17:17:30 +0000
@@ -2048,7 +2048,7 @@
        We used to use 0 here, but that leads to accidental sharing in
        purecopy's hash-consing, so we use a (hopefully) unique integer
        instead.  */
-    docstring = make_number (XPNTR (function));
+    docstring = make_number (XUNTAG (function, Lisp_Symbol));
   return Ffset (function,
 		Fpurecopy (list5 (Qautoload, file, docstring,
 				  interactive, type)));

=== modified file 'src/font.h'
--- src/font.h	2012-01-19 07:21:25 +0000
+++ src/font.h	2012-05-09 17:17:30 +0000
@@ -469,11 +469,12 @@
   } while (0)

 #define XFONT_SPEC(p)	\
-  (eassert (FONT_SPEC_P(p)), (struct font_spec *) XPNTR (p))
+  (eassert (FONT_SPEC_P (p)), (struct font_spec *) XUNTAG (p, Lisp_Vectorlike))
 #define XFONT_ENTITY(p)	\
-  (eassert (FONT_ENTITY_P(p)), (struct font_entity *) XPNTR (p))
+  (eassert (FONT_ENTITY_P (p)), \
+   (struct font_entity *) XUNTAG (p, Lisp_Vectorlike))
 #define XFONT_OBJECT(p)	\
-  (eassert (FONT_OBJECT_P(p)), (struct font *) XPNTR (p))
+  (eassert (FONT_OBJECT_P (p)), (struct font *) XUNTAG (p, Lisp_Vectorlike))
 #define XSETFONT(a, b) (XSETPSEUDOVECTOR (a, b, PVEC_FONT))

 /* Number of pt per inch (from the TeXbook).  */

=== modified file 'src/frame.h'
--- src/frame.h	2012-01-19 07:21:25 +0000
+++ src/frame.h	2012-05-09 17:17:30 +0000
@@ -501,7 +501,8 @@

 typedef struct frame *FRAME_PTR;

-#define XFRAME(p) (eassert (FRAMEP(p)),(struct frame *) XPNTR (p))
+#define XFRAME(p) \
+  (eassert (FRAMEP (p)), (struct frame *) XUNTAG (p, Lisp_Vectorlike))
 #define XSETFRAME(a, b) (XSETPSEUDOVECTOR (a, b, PVEC_FRAME))

 /* Given a window, return its frame as a Lisp_Object.  */

=== modified file 'src/lisp.h'
--- src/lisp.h	2012-05-04 23:16:47 +0000
+++ src/lisp.h	2012-05-09 17:49:17 +0000
@@ -475,6 +475,7 @@
      (var) = (type) | (intptr_t) (ptr))

 #define XPNTR(a) ((intptr_t) ((a) & ~TYPEMASK))
+#define XUNTAG(a, type) ((intptr_t) ((a) - (type)))

 #else  /* not USE_LSB_TAG */

@@ -581,6 +582,13 @@
 # define XSETFASTINT(a, b) (XSETINT (a, b))
 #endif

+/* Extract the pointer value of the Lisp object A, under the
+   assumption that A's type is TYPE.  This is a fallback
+   implementation if nothing faster is available.  */
+#ifndef XUNTAG
+# define XUNTAG(a, type) XPNTR (a)
+#endif
+
 #define EQ(x, y) (XHASH (x) == XHASH (y))

 /* Number of bits in a fixnum, including the sign bit.  */
@@ -607,15 +615,20 @@

 /* Extract a value or address from a Lisp_Object.  */

-#define XCONS(a) (eassert (CONSP (a)), (struct Lisp_Cons *) XPNTR (a))
-#define XVECTOR(a) (eassert (VECTORLIKEP (a)), (struct Lisp_Vector *) XPNTR (a))
-#define XSTRING(a) (eassert (STRINGP (a)), (struct Lisp_String *) XPNTR (a))
-#define XSYMBOL(a) (eassert (SYMBOLP (a)), (struct Lisp_Symbol *) XPNTR (a))
-#define XFLOAT(a) (eassert (FLOATP (a)), (struct Lisp_Float *) XPNTR (a))
+#define XCONS(a)   (eassert (CONSP (a)), \
+		    (struct Lisp_Cons *) XUNTAG (a, Lisp_Cons))
+#define XVECTOR(a) (eassert (VECTORLIKEP (a)), \
+		    (struct Lisp_Vector *) XUNTAG (a, Lisp_Vectorlike))
+#define XSTRING(a) (eassert (STRINGP (a)), \
+		    (struct Lisp_String *) XUNTAG (a, Lisp_String))
+#define XSYMBOL(a) (eassert (SYMBOLP (a)), \
+		    (struct Lisp_Symbol *) XUNTAG (a, Lisp_Symbol))
+#define XFLOAT(a)  (eassert (FLOATP (a)), \
+		    (struct Lisp_Float *) XUNTAG (a, Lisp_Float))

 /* Misc types.  */

-#define XMISC(a)   ((union Lisp_Misc *) XPNTR (a))
+#define XMISC(a)	((union Lisp_Misc *) XUNTAG (a, Lisp_Misc))
 #define XMISCANY(a)	(eassert (MISCP (a)), &(XMISC (a)->u_any))
 #define XMISCTYPE(a)   (XMISCANY (a)->type)
 #define XMARKER(a)	(eassert (MARKERP (a)), &(XMISC (a)->u_marker))
@@ -635,14 +648,24 @@

 /* Pseudovector types.  */

-#define XPROCESS(a) (eassert (PROCESSP (a)), (struct Lisp_Process *) XPNTR (a))
-#define XWINDOW(a) (eassert (WINDOWP (a)), (struct window *) XPNTR (a))
-#define XTERMINAL(a) (eassert (TERMINALP (a)), (struct terminal *) XPNTR (a))
-#define XSUBR(a) (eassert (SUBRP (a)), (struct Lisp_Subr *) XPNTR (a))
-#define XBUFFER(a) (eassert (BUFFERP (a)), (struct buffer *) XPNTR (a))
-#define XCHAR_TABLE(a) (eassert (CHAR_TABLE_P (a)), (struct Lisp_Char_Table *) XPNTR (a))
-#define XSUB_CHAR_TABLE(a) (eassert (SUB_CHAR_TABLE_P (a)), (struct Lisp_Sub_Char_Table *) XPNTR (a))
-#define XBOOL_VECTOR(a) (eassert (BOOL_VECTOR_P (a)), (struct Lisp_Bool_Vector *) XPNTR (a))
+#define XPROCESS(a) (eassert (PROCESSP (a)), \
+		     (struct Lisp_Process *) XUNTAG (a, Lisp_Vectorlike))
+#define XWINDOW(a) (eassert (WINDOWP (a)), \
+		    (struct window *) XUNTAG (a, Lisp_Vectorlike))
+#define XTERMINAL(a) (eassert (TERMINALP (a)), \
+		      (struct terminal *) XUNTAG (a, Lisp_Vectorlike))
+#define XSUBR(a) (eassert (SUBRP (a)), \
+		  (struct Lisp_Subr *) XUNTAG (a, Lisp_Vectorlike))
+#define XBUFFER(a) (eassert (BUFFERP (a)), \
+		    (struct buffer *) XUNTAG (a, Lisp_Vectorlike))
+#define XCHAR_TABLE(a) (eassert (CHAR_TABLE_P (a)), \
+			(struct Lisp_Char_Table *) XUNTAG (a, Lisp_Vectorlike))
+#define XSUB_CHAR_TABLE(a) (eassert (SUB_CHAR_TABLE_P (a)), \
+			    ((struct Lisp_Sub_Char_Table *) \
+			     XUNTAG (a, Lisp_Vectorlike)))
+#define XBOOL_VECTOR(a) (eassert (BOOL_VECTOR_P (a)), \
+			 ((struct Lisp_Bool_Vector *) \
+			  XUNTAG (a, Lisp_Vectorlike)))

 /* Construct a Lisp_Object from a value or address.  */

@@ -669,7 +692,9 @@
 /* The cast to struct vectorlike_header * avoids aliasing issues.  */
 #define XSETPSEUDOVECTOR(a, b, code) \
   XSETTYPED_PSEUDOVECTOR(a, b,       \
-			 ((struct vectorlike_header *) XPNTR (a))->size, \
+			 (((struct vectorlike_header *)	\
+			   XUNTAG (a, Lisp_Vectorlike)) \
+			  ->size),			\
 			 code)
 #define XSETTYPED_PSEUDOVECTOR(a, b, size, code)			\
   (XSETVECTOR (a, b),							\
@@ -1277,7 +1302,7 @@


 #define XHASH_TABLE(OBJ) \
-     ((struct Lisp_Hash_Table *) XPNTR (OBJ))
+     ((struct Lisp_Hash_Table *) XUNTAG (OBJ, Lisp_Vectorlike))

 #define XSET_HASH_TABLE(VAR, PTR) \
      (XSETPSEUDOVECTOR (VAR, PTR, PVEC_HASH_TABLE))
@@ -1735,7 +1760,7 @@
    code is CODE.  */
 #define TYPED_PSEUDOVECTORP(x, t, code)				\
   (VECTORLIKEP (x)						\
-   && (((((struct t *) XPNTR (x))->size				\
+   && (((((struct t *) XUNTAG (x, Lisp_Vectorlike))->size	\
 	 & (PSEUDOVECTOR_FLAG | (code))))			\
        == (PSEUDOVECTOR_FLAG | (code))))