In article <··········@apollo.hp.com>,
Bill Sommerfeld <··········@apollo.hp.com> wrote:
>
>With respect to using a subfield of the address as a type tag: given a
>sufficiently large sparse address space, you can "just do it" by
>allocating different primitive types in different parts of the address
>space.
We did this in early versions of CMU Common Lisp (Spice Lisp) that ran under
Accent and Mach. I suspect there are noticeable memory locality penalties,
since objects of different types can't be located on the same page. The
steady-state working set for large applications probably doesn't change, but:
-- page-in times when an application starts up are worse, since more pages
need to be touched, and
-- as workstation cache line sizes become larger, cache locality degradation
might become a factor, and
-- probably more significantly, you'll tend to thrash the TLB. Modern TLBs
are quite small compared to the size of the address space, and can really
hurt code that widely scatters its memory references.
However, the reason we ultimately went to using low-tag bits was not mainly the
locality issue, but that:
1] Most flavors of Unix don't support sparse allocation well. Even Mach
"optimized" it's VM lookup by doing a linear search of allocated chunks,
since "there's never more than a few chunks."
2] 32 bits of address space is too darn small to fragment it out the wazoo.
3] The efficiency gain of having the high-tag bits wasn't all that compelling,
since usually when you indirect an object you already know what type it is,
and can subtract out the tag with the index offset, like:
load ptr, -7
By the way, there is a non-obvious advantage of high-tag bits over low-tag
bits, which is that you can have more high-tag bits, since they only waste
address space, whereas more than two low-tag bits starts to waste actual
memory. Since Lisp has user-defined types, in general it will be necessary
indirect to the object header to determine it's type, but if you have enough
tag bits, you can do more efficient type tests for important primitive data
types.
In CMU CL, we use three low-tag bits and 64-bit align all objects. Dual-word
alignment doesn't waste too much space, since most memory is used by
medium-to-large objects, and the most important small objects (list cells) are
exactly two words.
For Dylan, we're looking into using two words to represent general object
references, with no pointer tag bits at all. The reason for this is that we
want to avoid the dilemma of either:
-- "stealing" bits from hardware supported datatypes like byte pointers,
integers and single-floats (which causes semantic problems, especially when
talking to other languages), and
-- heap allocating these object types (which causes serious performance
problems.)
We have ported CMU CL to the Alpha. We kept Lisp head pointers as 32 bits, but
support 64bit foreign pointers and integers. Going to a full 64bit model would
be a moderately big leap, since it would double the size of object references
in all applications. However, for many applications, then penalty is probably
well less than 100%, since much of the heap is likely to be filled with
non-pointer data (like code and strings.) As I recall, we found that it would
be ~25% for the default Lisp image.
The complexity of a Lisp runtime makes support for more than one pointer model
is somewhat daunting (and it would have to be chosen at compile-time on a
per-application basis.)
Rob