Tag Bits vs. Spaces

[Mark J. Dulcey]

On Thu, 21 May 1998, David Tillman wrote:

>     Am I correct in my understanding that the Spaces method
>     used by MacLisp does away with the need for tag bits?

Yes. You still need some way of tagging non-primitive objects like
structures and object instances, however. Of course, those things weren't
a factor in MacLisp's day, and modern implementations don't use tag bits
for structures and objects anyway; they mostly use an extra semi-hidden
structure element.

>     Is this method of allocation and type checking still considered
>     to be a Good Thing or is it too much trouble to make sure that
>     you don't run out of a certain type of space?

Running out of a certain kind of space wasn't really a problem; they would
just allocate more. The way it worked is that they maintained a table of
pages used by Lisp; each one had a type code associated with it. Any
memory page could be dedicated to any data type. True, there could be a
certain amount of wasted space because of the pages not being entirely
full (and even more if you generated a lot of objects of one type at one
point in a program, but didn't need so many later), but it wasn't a major
problem in practice.

But the type checking was relatively expensive, because they had to look
up the object in the page table to see what kind of objects were stored in
that page, so you had an extra memory fetch every time you fetched data
and type-checked it.

MacLisp programmers tended to bypass most of the type-checking by using
type declarations in their code. This has its problems, however; it makes
writing programs more work, and it can introduce subtle bugs. (What
happens when the object you pass to a function ISN'T the type you say it
is? Anything from wrong answers to system crashes.)

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.


Mark J. Dulcey               mdulcey@bospo.caiwireless.net
Visit my home page:          http://www.ziplink.net/~mark/
Visit my house's home page:  http://www.ziplink.net/~mark/buttery/