tags in the 3 lowest bits

tags in the 3 lowest bits

[Stefan Monnier]

Here is my proposed patch which adds a new macro USE_LSB_TAG:
if the macro is undefined, we behave as before, otherwise we
use the lowest 3 bits of words for tags.

Additionally to the above patch we will need to #define USE_LSB_TAG
when appropriate: it seems that we'll have to put it into the
[sm]/*.h files.

Any objection to my installing this patch ?


        Stefan


PS: The point of putting the tag in the LSB is that we can then use
    the whole address space, which can be important on some systems
    such as FreeBSD.


Index: lread.c
===================================================================
RCS file: /cvsroot/emacs/emacs/src/lread.c,v
retrieving revision 1.318
diff -u -r1.318 lread.c
--- lread.c	1 Sep 2003 15:45:56 -0000	1.318
+++ lread.c	19 Nov 2003 19:09:00 -0000
@@ -3407,6 +3407,16 @@
      struct Lisp_Subr *sname;
 {
   Lisp_Object sym;
+#ifdef USE_LSB_TAG
+  /* Make sure the object has multiple-of-8 alignment.  */
+  if (XTYPE (sname) != 0)
+    {
+      struct Lisp_Subr *old_sname = sname;
+      sname = (struct Lisp_Subr *) (4 + (char*) sname);
+      memmove (sname, old_sname, sizeof (*sname) - 4);
+      eassert (XTYPE (sname) == 0);
+    }
+#endif
   sym = intern (sname->symbol_name);
   XSETSUBR (XSYMBOL (sym)->function, sname);
 }
Index: lisp.h
===================================================================
RCS file: /cvsroot/emacs/emacs/src/lisp.h,v
retrieving revision 1.472
diff -u -r1.472 lisp.h
--- lisp.h	17 Nov 2003 23:29:30 -0000	1.472
+++ lisp.h	19 Nov 2003 19:09:00 -0000
@@ -68,9 +68,6 @@
 			   : die ((msg), __FILE__, __LINE__)),	\
 			  0)
 
-/* Let's get some compile-time checking too.  */
-#undef NO_UNION_TYPE
-
 #else
 
 /* Produce same side effects and result, but don't complain.  */
@@ -299,6 +296,26 @@
 
 #ifdef NO_UNION_TYPE
 
+#ifdef USE_LSB_TAG
+
+#define TYPEMASK ((((EMACS_INT) 1) << GCTYPEBITS) - 1)
+#define XTYPE(a) ((enum Lisp_Type) (((EMACS_UINT) (a)) & TYPEMASK))
+#define XINT(a) (((EMACS_INT) (a)) >> GCTYPEBITS)
+#define XUINT(a) (((EMACS_UINT) (a)) >> GCTYPEBITS)
+#define XSET(var, type, ptr)				\
+  (eassert ((((EMACS_UINT) (ptr)) & TYPEMASK) == 0),	\
+   (var) = ((EMACS_INT) (type)) + ((EMACS_INT) (ptr)))
+#define make_number(N) (((EMACS_INT) (N)) << GCTYPEBITS)
+
+#define XPNTR(a) ((a) & (((EMACS_INT) -1) << GCTYPEBITS))
+
+/* For integers known to be positive, XFASTINT used to provide fast retrieval
+   and XSETFASTINT fast storage.  */
+#define XFASTINT(a) XINT (a)
+#define XSETFASTINT(a, b) ((a) = make_number (b))
+
+#else  /* not USE_LSB_TAG */
+
 #define VALMASK ((((EMACS_INT) 1) << VALBITS) - 1)
 
 /* One need to override this if there must be high bits set in data space
@@ -337,6 +354,8 @@
 #define make_number(N)		\
   ((((EMACS_INT) (N)) & VALMASK) | ((EMACS_INT) Lisp_Int) << VALBITS)
 
+#endif /* not USE_LSB_TAG */
+
 #define EQ(x, y) ((x) == (y))
 
 #else /* not NO_UNION_TYPE */
@@ -384,6 +403,7 @@
 #define XGCTYPE(a) XTYPE (a)
 #endif
 
+/* In the USE_LSB_TAG case, XPNTR is defined further above.  */
 #ifndef XPNTR
 #ifdef HAVE_SHM
 /* In this representation, data is found in two widely separated segments.  */
@@ -752,6 +772,13 @@
     char *symbol_name;
     char *prompt;
     char *doc;
+#ifdef USE_LSB_TAG
+    /* Lisp_Subrs are statically allocated, so we cannot rely on malloc
+       giving us a multiple-of-8 alignment.  Instead, we assume that we
+       get a multiple-of-4 alignment, and we memmove the object by 4 bytes
+       if needed.  The memmove is in lread.c:defsubr.  */
+    char padding[4];
+#endif
   };
 
 \f
@@ -1150,6 +1177,13 @@
     unsigned gcmarkbit : 1;
     int spacer : 15;
     union Lisp_Misc *chain;
+#ifdef USE_LSB_TAG
+    /* Try to make sure that sizeof(Lisp_Misc) is a multiple of 8.
+       This assumes that Lisp_Marker is the largest of the alternatives and
+       that Lisp_Intfwd has the same size as Lisp_Free without padding.  */
+    char padding[8 * ((sizeof (struct Lisp_Marker) - 1) / 8 + 1)
+		 - sizeof (struct Lisp_Intfwd)];
+#endif
   };
 
 /* To get the type field of a union Lisp_Misc, use XMISCTYPE.
Index: alloc.c
===================================================================
RCS file: /cvsroot/emacs/emacs/src/alloc.c,v
retrieving revision 1.328
diff -u -r1.328 alloc.c
--- alloc.c	18 Nov 2003 00:39:13 -0000	1.328
+++ alloc.c	19 Nov 2003 19:09:00 -0000
@@ -598,6 +598,7 @@
 
   val = (void *) malloc (nbytes);
 
+#ifndef USE_LSB_TAG
   /* If the memory just allocated cannot be addressed thru a Lisp
      object's pointer, and it needs to be,
      that's equivalent to running out of memory.  */
@@ -612,6 +613,7 @@
 	  val = 0;
 	}
     }
+#endif
 
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
   if (val && type != MEM_TYPE_NON_LISP)
@@ -772,6 +774,7 @@
       mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
 #endif
 
+#ifndef USE_LSB_TAG
       /* If the memory just allocated cannot be addressed thru a Lisp
 	 object's pointer, and it needs to be, that's equivalent to
 	 running out of memory.  */
@@ -788,6 +791,7 @@
 	      memory_full ();
 	    }
 	}
+#endif
 
       /* Initialize the blocks and put them on the free list.
 	 Is `base' was not properly aligned, we can't use the last block.  */
@@ -1343,8 +1347,8 @@
 
 struct string_block
 {
-  struct string_block *next;
   struct Lisp_String strings[STRING_BLOCK_SIZE];
+  struct string_block *next;
 };
 
 /* Head and tail of the list of sblock structures holding Lisp string
@@ -2749,8 +2753,8 @@
 
 struct symbol_block
 {
-  struct symbol_block *next;
   struct Lisp_Symbol symbols[SYMBOL_BLOCK_SIZE];
+  struct symbol_block *next;
 };
 
 /* Current symbol block and index of first unused Lisp_Symbol
@@ -2841,8 +2845,8 @@
 
 struct marker_block
 {
-  struct marker_block *next;
   union Lisp_Misc markers[MARKER_BLOCK_SIZE];
+  struct marker_block *next;
 };
 
 struct marker_block *marker_block;
@@ -3422,6 +3426,7 @@
       /* P must point to the start of a Lisp_String structure, and it
 	 must not be on the free-list.  */
       return (offset >= 0
+	      && offset < (STRING_BLOCK_SIZE * sizeof b->strings[0])
 	      && offset % sizeof b->strings[0] == 0
 	      && ((struct Lisp_String *) p)->data != NULL);
     }
@@ -3476,6 +3481,7 @@
 	 and not be on the free-list.  */
       return (offset >= 0
 	      && offset % sizeof b->symbols[0] == 0
+	      && offset < (SYMBOL_BLOCK_SIZE * sizeof b->symbols[0])
 	      && (b != symbol_block
 		  || offset / sizeof b->symbols[0] < symbol_block_index)
 	      && !EQ (((struct Lisp_Symbol *) p)->function, Vdead));
@@ -3529,6 +3535,7 @@
 	 and not be on the free-list.  */
       return (offset >= 0
 	      && offset % sizeof b->markers[0] == 0
+	      && offset < (MARKER_BLOCK_SIZE * sizeof b->markers[0])
 	      && (b != marker_block
 		  || offset / sizeof b->markers[0] < marker_block_index)
 	      && ((union Lisp_Misc *) p)->u_marker.type != Lisp_Misc_Free);
@@ -4063,6 +4070,10 @@
      int type;
 {
   POINTER_TYPE *result;
+#ifdef USE_LSB_TAG
+  /* Ensure a minimum of 3 bits for tags. */
+  size_t alignment = max (8, sizeof (EMACS_INT));
+#else
   size_t alignment = sizeof (EMACS_INT);
 
   /* Give Lisp_Floats an extra alignment.  */
@@ -4074,6 +4085,7 @@
       alignment = sizeof (struct Lisp_Float);
 #endif
     }
+#endif
 
  again:
   result = ALIGN (purebeg + pure_bytes_used, alignment);

Re: tags in the 3 lowest bits

[Kim F. Storm]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> Here is my proposed patch which adds a new macro USE_LSB_TAG:
> if the macro is undefined, we behave as before, otherwise we
> use the lowest 3 bits of words for tags.

So the intention is to continue using MSB tags by default, and
only use LSB on those systems which really need it (eg. FreeBSD) ?

The only reason I can see for this is that there is a small
performance penalty on XFASTINT with LSB -- but I'd prefer that
penalty rather than having to support two different methods.

Or are there systems which cannot use LSB?

 
> 
> Additionally to the above patch we will need to #define USE_LSB_TAG
> when appropriate: it seems that we'll have to put it into the
> [sm]/*.h files.
> 
> Any objection to my installing this patch ?
> 
> 
>         Stefan
> 
> 
> PS: The point of putting the tag in the LSB is that we can then use
>     the whole address space, which can be important on some systems
>     such as FreeBSD.
> 
> 
> Index: lread.c
> ===================================================================
> RCS file: /cvsroot/emacs/emacs/src/lread.c,v
> retrieving revision 1.318
> diff -u -r1.318 lread.c
> --- lread.c	1 Sep 2003 15:45:56 -0000	1.318
> +++ lread.c	19 Nov 2003 19:09:00 -0000
> @@ -3407,6 +3407,16 @@
>       struct Lisp_Subr *sname;
>  {
>    Lisp_Object sym;
> +#ifdef USE_LSB_TAG
> +  /* Make sure the object has multiple-of-8 alignment.  */
> +  if (XTYPE (sname) != 0)

Clever :-)

> +    {
> +      struct Lisp_Subr *old_sname = sname;
> +      sname = (struct Lisp_Subr *) (4 + (char*) sname);
> +      memmove (sname, old_sname, sizeof (*sname) - 4);

I suggest using sizeof(sname->padding) rather than constant 4 here.

Or even better, use the actual "mis-offset", as this will work even
if we increase GCTYPEBITS later (also see below):

        ((1 << GCTYPEBITS) - (int)XTYPE (sname))



> @@ -752,6 +772,13 @@
>      char *symbol_name;
>      char *prompt;
>      char *doc;
> +#ifdef USE_LSB_TAG
> +    /* Lisp_Subrs are statically allocated, so we cannot rely on malloc
> +       giving us a multiple-of-8 alignment.  Instead, we assume that we
> +       get a multiple-of-4 alignment, and we memmove the object by 4 bytes
> +       if needed.  The memmove is in lread.c:defsubr.  */
> +    char padding[4];

Suppose we later increase GCTYPEBITS, this is more correct:

        char padding[(1 << GCTYPEBITS) - 4];


> +#endif
>    };
>  
>  \f
> @@ -1150,6 +1177,13 @@
>      unsigned gcmarkbit : 1;
>      int spacer : 15;
>      union Lisp_Misc *chain;
> +#ifdef USE_LSB_TAG
> +    /* Try to make sure that sizeof(Lisp_Misc) is a multiple of 8.
> +       This assumes that Lisp_Marker is the largest of the alternatives and
> +       that Lisp_Intfwd has the same size as Lisp_Free without padding.  */
> +    char padding[8 * ((sizeof (struct Lisp_Marker) - 1) / 8 + 1)
> +		 - sizeof (struct Lisp_Intfwd)];

I would prefer if this was also expressed in terms of GCTYPEBITS.

> +	      && offset < (STRING_BLOCK_SIZE * sizeof b->strings[0])

Why not offset < sizeof b->strings ?

> +	      && offset < (SYMBOL_BLOCK_SIZE * sizeof b->symbols[0])

Why not offset < sizeof b->symbols ?

> +	      && offset < (MARKER_BLOCK_SIZE * sizeof b->markers[0])

Ditto

> +#ifdef USE_LSB_TAG
> +  /* Ensure a minimum of 3 bits for tags. */
> +  size_t alignment = max (8, sizeof (EMACS_INT));

I suggest:

  /* Ensure a minimum of GCTYPEBITS bits for tags. */
  size_t alignment = max ((1 << GCTYPEBITS), sizeof (EMACS_INT));

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk

Re: tags in the 3 lowest bits

[Miles Bader]

On Thu, Nov 20, 2003 at 01:28:56AM +0100, Kim F. Storm wrote:
> So the intention is to continue using MSB tags by default, and
> only use LSB on those systems which really need it (eg. FreeBSD) ?

I'd prefer to just entirely switch to LSB tags too, but I interpreted
Stefan's message as simple caution -- let's get some experience first before
committing to anything, and in the process be able to support some more
systems.

Personally I'll turn them on unconditionally when I compile my own emacs.
I think for testing, it would be good if it's simple to do this (e.g., with a
configure option).

-Miles
-- 
80% of success is just showing up.  --Woody Allen

Re: tags in the 3 lowest bits

[Stefan Monnier]

> The only reason I can see for this is that there is a small
> performance penalty on XFASTINT with LSB -- but I'd prefer that
> penalty rather than having to support two different methods.

I doubt the performance penalty is an issue.  After all, manipulating MSB
is generally slightly more costly than LSB, so the performance impact might
even be positive.  But I expect it's a wash.

> Or are there systems which cannot use LSB?

The LSB code needs pointers values that are multiples of 8.
On some systems, malloc does not guarantee it.  Probably we can use
gmalloc.c for those systems, but we'll need to make sure that's an option
and we'll need to figure out when that's nmecessary.  Also, there might be
systems that are word-addressed rather than byte-addressed.  I don't know
if such systems are still in use and whether Emacs runs on them, but if
yes, we'll probably need to find some other way to deal with them,
maybe keeping the old behavior.

I also hope we can switch to LSB everywhere, but I don't think we can
do that right now.

I suggest to start with something like along the lines of

#if defined GLIBC || defined GNU_MALLOC
#define USE_LSB_TAG
#endif

And then slowly increase the number of systems where we use LSB.

Basically, the same as is/was done for the conservative stack marking (that
was recently turned on in MacOS).

BTW, the patch has only seen fairly light testing.  It works for me
with PCL-CVS, Gnus, and bunch of other things but there might still be
bugs lurking.  I strongly suggest to run it with ENABLE_CHECKING (which my
patch decouples from NO_UNION_TYPE).


        Stefan

Re: tags in the 3 lowest bits

[Kim F. Storm]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> > The only reason I can see for this is that there is a small
> > performance penalty on XFASTINT with LSB -- but I'd prefer that
> > penalty rather than having to support two different methods.
> 
> I doubt the performance penalty is an issue.  After all, manipulating MSB
> is generally slightly more costly than LSB, so the performance impact might
> even be positive.  But I expect it's a wash.

Once LSB is in place, I would like us to get rid of XFASTINT
all-together.  It's a potential danger lurking to hit us.


> 
> > Or are there systems which cannot use LSB?
> 
> The LSB code needs pointers values that are multiples of 8.
> On some systems, malloc does not guarantee it.  Probably we can use
> gmalloc.c for those systems, but we'll need to make sure that's an option
> and we'll need to figure out when that's nmecessary.  

We could wrap malloc and free on such systems to force 8 byte alignment like
this  (it's a little costly in memory, but no big deal):

char *malloc_wrap(size_t len)
{
        char *p = malloc(len + 16);
        char *p1 = p;
        p = (char *)((unsigned)(p + 15) & ~0x7);
        *(char **)(p - 8) = p1;
        return p;
}

char free_wrap(char *p)
{
        free(*(char **)(p - 8));
}


>                                                       Also, there might be
> systems that are word-addressed rather than byte-addressed.  I don't know
> if such systems are still in use and whether Emacs runs on them, but if
> yes, we'll probably need to find some other way to deal with them,
> maybe keeping the old behavior.
> 
> I also hope we can switch to LSB everywhere, but I don't think we can
> do that right now.
> 
> I suggest to start with something like along the lines of
> 
> #if defined GLIBC || defined GNU_MALLOC
> #define USE_LSB_TAG
> #endif

That's a good starting point, yes.
Or we could use the above trick like this:

#if !(defined GLIBC || defined GNU_MALLOC)
#define malloc malloc_wrap
#define free free_wrap
#endif

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk

Re: tags in the 3 lowest bits

[Miles Bader]

storm@cua.dk (Kim F. Storm) writes:
> Once LSB is in place, I would like us to get rid of XFASTINT
> all-together.  It's a potential danger lurking to hit us.

Um, in the LSB code, XFASTINT is the same as XINT...

-Miles
-- 
"Whatever you do will be insignificant, but it is very important that
 you do it."  Mahatma Gandhi

Re: tags in the 3 lowest bits

[Kim F. Storm]

Miles Bader <miles@lsi.nec.co.jp> writes:

> storm@cua.dk (Kim F. Storm) writes:
> > Once LSB is in place, I would like us to get rid of XFASTINT
> > all-together.  It's a potential danger lurking to hit us.
> 
> Um, in the LSB code, XFASTINT is the same as XINT...
> 

Exactly!

Which is why keeping it in the code when _most_ systems use
LSB could leave some mis-uses (storing a negative int there)
undetected until someone hits a border case on some non-LSB
system... which will be very hard to debug.

Better be proactive and get rid of those XFASTINT and XSETFASTINT
things all-together (or at least make them equal to XINT and XSETINT
on all systems)!

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk

Re: tags in the 3 lowest bits

[Richard Stallman]

    Better be proactive and get rid of those XFASTINT and XSETFASTINT
    things all-together (or at least make them equal to XINT and XSETINT
    on all systems)!

This could make a significant slowdown on other systems.
I'd rather not.

Re: tags in the 3 lowest bits

[Stefan Monnier]

> We could wrap malloc and free on such systems to force 8 byte alignment like
> this  (it's a little costly in memory, but no big deal):

The cost is zero for cons cells and floats (which are already wrapped to
ensure alignment, for other reasons), it's negligible for strings, markers,
and symbols, but it's a bit heavy for small arrays.

OTOH, small arrays are already inefficient (because each array, no matter
how small, is added to the memory-map (a binary tree) used for conservative
stack marking).  So maybe we should begin by changing the handling of small
arrays (similar to what is done for strings, although I'm not quite sure
what it would look like).


        Stefan

Re: tags in the 3 lowest bits

[Stefan Monnier]

> OTOH, small arrays are already inefficient (because each array, no matter
> how small, is added to the memory-map (a binary tree) used for conservative
> stack marking).  So maybe we should begin by changing the handling of small
> arrays (similar to what is done for strings, although I'm not quite sure
> what it would look like).

Of course, an alternative would be to switch to BoehmGC.
Dave Love has started work on this and it would be interesting to see
how it works out in practice (what kind of impact it has on memory
footprint and CPU usage).


        Stefan

Re: tags in the 3 lowest bits

[Kim F. Storm]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> > OTOH, small arrays are already inefficient (because each array, no matter
> > how small, is added to the memory-map (a binary tree) used for conservative
> > stack marking).  So maybe we should begin by changing the handling of small
> > arrays (similar to what is done for strings, although I'm not quite sure
> > what it would look like).
> 
> Of course, an alternative would be to switch to BoehmGC.

Sure, but is it a better alternative?  And why?

How does that remove the dependency on (non-aligned) mallocs?

I can understand your changes in the scope of the current GC scheme(s).
Adding another one together with your changes doesn't seem necessary to me.

> Dave Love has started work on this and it would be interesting to see
> how it works out in practice (what kind of impact it has on memory
> footprint and CPU usage).

What is the status of that effort?  Dave?

IMHO, this is not a user-visible change, so I think we have more
important things to work on.

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk

Re: tags in the 3 lowest bits

[David Kastrup]

storm@cua.dk (Kim F. Storm) writes:

> [BoehmGC]
> > Dave Love has started work on this and it would be interesting to see
> > how it works out in practice (what kind of impact it has on memory
> > footprint and CPU usage).
> 
> What is the status of that effort?  Dave?
> 
> IMHO, this is not a user-visible change, so I think we have more
> important things to work on.

Actually, the current tag work _has_ been inspired by user complaints,
and it is quite user-visible.  It changes the value of
most-positive-fixnum, and thus the maximum size of Emacs buffers.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: tags in the 3 lowest bits

[Kim F. Storm]

David Kastrup <dak@gnu.org> writes:

> storm@cua.dk (Kim F. Storm) writes:
> 
> > [BoehmGC]
> > > Dave Love has started work on this and it would be interesting to see
> > > how it works out in practice (what kind of impact it has on memory
> > > footprint and CPU usage).
> > 
> > What is the status of that effort?  Dave?
> > 
> > IMHO, this is not a user-visible change, so I think we have more
> > important things to work on.
> 
> Actually, the current tag work _has_ been inspired by user complaints,
> and it is quite user-visible.  It changes the value of
> most-positive-fixnum, and thus the maximum size of Emacs buffers.

I wasn't questioning the usefulness of the current tag work. IMO we
should move to LSB tags asap.

The objection above was related to switching to the BoehmGC -- I think
that's a much bigger effort than the proposed LSB changes, and I don't
see (know) what _additional_ benefits using BoehmGC will give us
(that's why I asked).

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk

Re: tags in the 3 lowest bits

[Stefan Monnier]

>> Of course, an alternative would be to switch to BoehmGC.
> Sure, but is it a better alternative?  And why?

It would make array allocation much cheaper.  Now that's obviously not
consdered as an important part of the elisp engine since it hasn't been
optimized, so it can't be a main motivation for switching to BoehmGC.

> How does that remove the dependency on (non-aligned) mallocs?

BoehmGC does its own malloc, so it would solve it in the same way that
using emacs/src/gmalloc.c can solve it.

> I can understand your changes in the scope of the current GC scheme(s).
> Adding another one together with your changes doesn't seem necessary to me.

The two aren't linked indeed.

>> Dave Love has started work on this and it would be interesting to see
>> how it works out in practice (what kind of impact it has on memory
>> footprint and CPU usage).

> What is the status of that effort?  Dave?

> IMHO, this is not a user-visible change, so I think we have more
> important things to work on.

The BoehmGC is a pretty good package.  Its performance can be pretty good
and it can offer things like incremental collection which can make
a visible difference to the users.
Of course it does not always work great, it all depends on the actual
application and might require some tuning.

But if the performance is there, it would also have the advantage of saving
us from worrying about GC: we could scrap the GC code and rely on
a well-maintained piece of code.

Now, that doesn't mean that it should be a top-priority objective, but just
that working on it is not necessarily a waste of time.


        Stefan