From: daveg@thymus.synaptics.COM
Subject: Re: tagging schemes
Reply-To: daveg@synaptics.com
Organization: GNUs Not Usenet
Distribution: gnu
Date: Mon, 13 Apr 1992 08:50:39 GMT

The saga continues...

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

I was wondering about that.  I guess if you're going to be able to mark
a cons cell, you have no choice but to reserve a mark bit in your pointers
since there's nothing in a cons cell *but* pointers.  Pretty ugly!

Well, okay, that's not strictly true.  Cons cells are allocated in blocks.
It shouldn't be too hard to keep a separate packed bitmap of mark bits
for the corresponding cons cells in a block.

>> Let's see, my Emacs process has 423615 cons cells allocated ...
> That's almost 10x what mine has, and it's been up for a few days.

Mine has been up since March 30, and I've been doing a lot of hacking
in it including loading all of Calc into memory.  As I said, 400k conses
is unusual, but it's clearly not unheard-of.

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

I've been trying to find a way to juggle the tags around that could be
put into Emacs with minimal impact.  CDR-coding sure is cute, but it
would break *everything* to add it now!

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

Let's see, most modern RISC-style machines require doubles to be allocated
on multiples of 8, so their mallocs are all going to return aligned storage.
If you're on a machine where you aren't sure, you could always (groan)
allocate four bytes more than you need and then bump the pointer if it's
not fully aligned.  I think most storage in Emacs is in buffers, cons
cells, and strings, all of which are malloc'd in bulk so the four-byte
overhead wouldn't hurt too much.  And, of course, there's the GNU malloc
option as you said.

Are there machines where malloc won't even return a 4-aligned address?

>>> 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.
> I'm seriously grossed out by that idea.  The idea that consing could occur
> while doing fixnum arithmetic is pretty contrary to my religion. :-)

True, but KCL really is fast.  On our application at work we've compared
KCL with Lucid Lisp and found KCL to be faster in many ways.  Everything
in KCL is a plain pointer to an object that contains an integer tag.
Lucid spends lots of instructions unravelling the several layers of tags
where KCL simply follows the pointer and looks at a single integer.
KCL's simpler data structures allow it to compile in-line many more
Lisp primitives than Lucid can, and that's where the big win is.

But, you're right, Emacs uses large-ish integers far too often to make
this consing acceptable.

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

KCL's collector works this way.  They do it by allocating collectible
objects of various sizes in different blocks of memory according to
size.  For each 32-bit value on the stack, they first check if it's
in the right range for a memory address, then check which block it is
in, then round it back to the beginning of an object boundary in the
block (which is easy to find since everything in that block has the
same size).  Then they mark the thing on the assumption that it is
being pointed to.  Sometimes they mark things that are not actually
referenced, but that doesn't hurt anything short of making a few
objects stay around in memory longer than necessary.  In return, they
get to throw out all that GC_PRO business once and for all, which makes
all their compiled code simpler and faster, and I wouldn't be surprised
if it also comes out to be a performance win in the long run.  (In my
observations, KCL's garbage collector is quite fast.)

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

That's why I thought of using conses instead of symbols as tags.  You
could still make symbols like "buffer-tag", but they'd just be variables
whose *values* were the conses that represented buffers.  Those conses
could be put into read-only (pure) storage where they'd be safe.

Whenever you use symbols, you always have the danger that two people
will pick the same symbol, or that someone will do something that
traverses the whole symbol table and blunders into your magic symbol.
I'd feel safer having cons cells.  Maybe they should be short lists,
i.e., (TAG-NAME TOTAL-SIZE NUM-PTRS) where TAG-NAME is a symbol like
"buffer", there purely for human readability.  That's pretty much a
frill, though.

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

Sure, I just meant that there would be no more overhead than for any
other scheme where the tags live in the objects themselves.  Things
will still need "next" pointers, or else they will have to be stored
in blocks like cons cells, symbols, and markers are now.

								-- Dave

Newsgroups: gnu.emacs.bug