Tag Bits vs. Spaces

[David Gadbois]

   Date: Thu, 21 May 1998 12:06:20 -0400 (EDT)
   From: "Mark J. Dulcey" <mdulcey@host2-86.caiwireless.net>

   The cost of this sort of type scheme in a modern Lisp, because of
   the extra memory lookup to get the type of an object, would
   probably be too high, unless you had special hardware assistance -
   something along the lines of the K-machine's scheme of doing the
   operation on the most common case of data type in parallel with
   doing the type check, but with the page table stored in a special
   high-speed cache. It doesn't look good for implementations on
   conventional architectures.

Well, at the risk of playing empirical air guitar, the Spaces or BiBoP
scheme is not too awful.  For example, one Lisp system I hack on uses
64KB "pages" and uses 8-bit descriptors.  Covering 1GB worth of
address space only takes up 16KB, which can easily fit in current L2
caches.  And reasonably modern compilation techniques can hoist or
optimize out a lot of the type tests.

I don't think it would be worthwhile to have a special parallel type
extractor.  After all, a trip out to memory is a trip out to memory,
If there is to be an extra load pipe, it would be better to make it
generally available rather than restrict it to a special use.

Special caches would be dandy, but I have found that mentioning such
things to architects is an excellent way of making their eyes glaze
over.  But a TLB with sufficiently large software-controlled fields in
its entries would serve this particular purpose very nicely.

The alternative is storing the tags in object references.  For 64-bit
machines, that is probably the way to go.  On 32-bit machines, it is a
tight fit, and there are close tradeoffs between the number of tag
bits and the address space size.

(I should also mention that segregating objects by types can have nice
pathlength benefits for some operations, especially for fixed-sized
objects.)

As you point out, given most Lisps' infinitely extensible type system
(and variable-sized objects), there has to be some kind of allowance
for type information stored in objects themselves.  The fewer of
these, the better, since type checks require trips out to memory
without the locality benefits of the page-associated tags.  (On the
other hand, if code size or implementation complexity are of concern,
using object-side type info could win:  Check out SIOD, for example.)

BTW, a book that has lots of good information about Lisp
implementation is "Topics in Advanced Language Implementation", Peter
Lee, ed., MIT Press 1991, ISBN: 0262121514).  In particular, it has a
paper that pretty much nails the tag bit issues to the floor.

--David Gadbois