From: daveg@thymus.synaptics.COM
Subject: Re: tagging schemes
Reply-To: daveg@synaptics.com
Organization: GNUs Not Usenet
Distribution: gnu
Date: Sat, 11 Apr 1992 07:40:03 GMT

Jamie Zawinski writes:
> ... Thus you can store a type-tag in these two bits without intruding
> on the address space.  One possible set of tags would be
> 
> 	00  - cons
> 	01  - even fixnum
> 	10  - odd fixnum
> 	11  - compound structure

Much better would be to assign 01 and 11 to fixnums, making them
easier to detect and to build out of C integers.

I assume you made a special tag for cons cells so that they could be
stored without a separate tag field in the cell.  Except for that it
would be easier to assign 00 to all pointers and leave 10 undefined.

In fact, you haven't accounted for the GC mark bit that also lives
in each Lisp pointer.  That would be a good use for the 10 tag.
I believe things can only be GC-marked during garbage collection
(if not, it would be easy to arrange).  This means that only routines
inside the garbage collector would have to be aware of 10 tags.
Everything else would deal only with fixnums and with pointers
whose values can be used directly.

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.

It might be better to assign 10 to cons cells and 00 to other objects.
I'll bet Emacs refers to non-cons objects more often than to conses.

It probably wouldn't hurt too much to require all Lisp objects
to be aligned to a multiple of 8, not just 4.  Cons cells are
8 bytes long, and everything else is both longer and much rarer.
This would give you three low bits at your disposal, and then you
could use the third bit as a mark bit and the low two bits to
decide among cons cells, general objects, and fixnums (which of
course don't need mark bits).

> If the tag is 01 or 10, then shift it right by one bit.  This
> give you 31-bit fixnums.

The horrible truth is that C does not provide a signed right-shift
operator; ">>" on signed integers is allowed to be an arithmetic or
logical shift.  What a pain!

I notice that the XINT macro in lisp.h assumes arithmetic shifts,
with a comment implying that particular m-*.h files override this as
necessary.  You could always use "(x-1)/2" as a machine-independent
definition.  On my Sparc both cc and gcc compile this into pretty
decent code.

> 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.  This is a
decent compromise, and it sure does speed up their tag-checking logic!
(As well as allowing a 100% portable, "kosher" C implementation.)

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.

>> It shouldn't take more than a week of hacking.
> I really don't think so...

I agree!  You wouldn't want to make a change like this by "hacking"
anyhow, you'd want to do it by sitting down and doing some very
careful thinking and coding.  If a week's worth of hacking could do
it *safely*, it would already have been done by now.

> ... there is a compromise that can be made as a first step that
> has some of the benefits of the above; I may be implementing something
> like the following soon.
> 
> Add a new type, Named_Vector, which looks like:
> ...

This would be really, *really* nice to have.  I second the motion!

> This lets you eliminate about a dozen primary type-tags (actually, chase
> them into the structure from the pointer) and, if the Lisp_Void,
> Lisp_Internal, and Lisp_Internal_Stream types were gotten rid of (which 
> I don't think would be too hard) then the remaining types would fit into
> four bits.

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?

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.,
require it to be a symbol and store the size and marked_size in two
cells of the symbol, or require it to be a cons cell and store them
in the car and cdr (as fixnums).  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!  (Besides, in a dumped Emacs you could
put all those cons cells into read-only store.)

Effectively, then, every Lisp object would have a 32-bit tag overhead
and nothing more.  Alignment restrictions would probably have forced
you to reserve 32 bits for an in-object tag anyhow.  So totally for
free, we've gained the ability to add new primitive object types to
Emacs Lisp!  Now if only it had a dynamic loader (nudge, nudge), Emacs
would be truly extensible at run-time.

								-- Dave

Newsgroups: gnu.emacs.bug