From: jwz@lucid.com (Jamie Zawinski)
Subject: Re: tagging schemes
Organization: GNUs Not Usenet
Distribution: gnu
Date: Sun, 12 Apr 1992 20:57:55 GMT

In message <9204112140.AA06782@thymus.synaptics> daveg@thymus.synaptics.com wrote:
>
> In fact, you haven't accounted for the GC mark bit that also lives
> in each Lisp pointer.  

The mark bit doesn't live in each pointer, it lives in each object; you can
put the mark bit anywhere, including on an untagged slot (like size), if you
know that one of the bits will not be used.  It happens that emacs currently
allocates space for the mark bit in each pointer, but pointers aren't what
gets marked.

> Let's see, my Emacs process has 423615 cons cells allocated
> (used+free) right now.  I think that's unusually large, but still,
> keeping tags out of cons cells would save a lot!  Maybe they do
> deserve their own tag, with the GC mark bit moving somewhere else.

That's almost 10x what mine has, and it's been up for a few days.  (I've
toyed around with the idea of implementing CDR-coding, just for its pure
hack value, but it wouldn't actually save very much.)  Oh, one reason that
my emacs has so many fewer conses than yours is that in v19, compiled-
function objects are made of vector-like Lisp_Compiled objects instead
of lambdas built from conses, saving half a dozen words per function.

> It probably wouldn't hurt too much to require all Lisp objects
> to be aligned to a multiple of 8, not just 4.  

That's true, in fact, that's what our lisp does (we've got 8 primary tags
instead of the 4 that I described).  I wonder how easy it is to do portably,
however.  I suppose if we require emacs to use GNU malloc, the answer to
that is "very."

>> Making lisp integers be compound structures is a really bad idea.
> 
> Kyoto Common Lisp does this, but they make a special case of integers
> in the range -1024 .. 1023.  They allocate a canonical object for each
> number in this range and always return it rather than consing up a new
> one.  Consing only occurs when you use larger integers.  

I'm seriously grossed out by that idea.  The idea that consing could occur
while doing fixnum arithmetic is pretty contrary to my religion. :-)  It may
be that it wouldn't kill emacs, but I still think it's pretty lame.

> On the other hand, Emacs makes pretty heavy use of large integers.
> It's probably worth doing a bit of profiling to see how heavy the
> hit would be.

Remember that this would mean that you'd have to cons an object every time
you moved point past 1024 characters.  Either that or you'd have to cons an
object every time you called Fpoint().

Also, this means that any C local variable that holds a Lisp_Int while
running elisp code needs to be GCPRO'd just like a "real" lisp pointer, and
I'm sure there are hundreds if not thousands of places that would need to be
changed.  Good luck finding them all!

In order to implement fixnums this way, I think your only option would be to
implement a conservative garbage collector (walk the stack and mark anything
that looks like a pointer to a lisp object, eliminating the need for GCPRO.)
Though this is not necessarily a bad idea, it's a huge amount of work, well
beyond what I was describing (or, given the cost/benefit analysis, what I
would want to take on.)

> So this brings us back to the original suggestion, of putting a type
> tag into the objects and having few or no tag bits in the pointer.
> Is there any reason not to use your Named_Vector abstraction for
> *everything*, aside from fixnums and maybe cons cells?

I would want fixnums to be immediate and conses to be two words, but other
than that I don't see any reason for everything not to be implemented in
terms of Named_Vectors (which RMS points out would be better called
Typed_Vectors.)  The nice thing is that this can be done incrementally:
first introduce the Typed_Vector, without changing anything else; then
start reimplementing things in terms of it (still keeping the tags in the
high bits.)  Once you've gotten the type-space small enough, you can move
the tag down to the bottom of the pointer.

> You could save some memory by replacing your "size" and "marked_size"
> fields by components of the thing that "type_name" points to, i.e.,

Good idea!

> Of course, the garbage collector can then be seriously hosed if someone
> setcar's one of these tag conses, but this is not going to happen unless
> someone deliberately decides to crash their Emacs!

I don't think "don't go like that" is a very good solution.  The obvious
implementation would be to store the sizes on the plist of the type-symbol,
but we want to protect against the user accidentally doing something stupid.
You can't make elements of the plist be read-only, and you don't want to
commandeer the function or value cell either, because that means that 
symbols like `buffer' can't be defined or bound.  

Of course, the builtins could just be special-cased, and the garbage-
collector could simply "know" how big buffers, processes, etc are.  
That's a little tacky.

> Effectively, then, every Lisp object would have a 32-bit tag overhead
> and nothing more.

You still need the "next" slot to chain these together for the "sweep" pass,
unless you allocate them like Lisp_Strings, and chain together blocks of a
few hundred at a time, or allocate them in some tricky way so that you can
just walk through memory and know what you're looking at.

	-- Jamie

Newsgroups: gnu.emacs.bug