I have seen analyzes of the trade off between putting tags in the low vs
high bits of words. On current hardware low bits seems to win and most
Lisp implementations seem to put them there.
I have not not read about any implementation that puts tags in a
separate array. Does anyone have any experience with, know an
implementation that uses, or seen a paper that analyzes this technique.
You would seem to win on portability and the ability to keep floats
"unboxed."
John McClain
Date: 23 Feb 94 09:56:00
From: ····@ai.mit.edu (John McClain)
I have not not read about any implementation that puts tags in a
separate array. Does anyone have any experience with, know an
implementation that uses, or seen a paper that analyzes this technique.
You would seem to win on portability and the ability to keep floats
"unboxed."
One common way to do this is called "BIBOP" (Big Bag Of Pages) which
was used in maclisp. A pointer is a machine pointer; the upper n bits
are used as an index into an array of 2^n elements. That divides
memory into contiguous subranges each of a certain type.
This was especially cute on the PDP-10 since a page was 377 words;
with 18-bit pointers that gave you 9 bits of type field and 9 bits of
index into the (single page) type array. The array elements were
symbols (eg CONS) indicating the type.
The disadvantage is that you have to do two memory reference to
determine something's type. On a modern RISC machine, with larger
address space than we used to have, it's not worth the compactness.
With only one value of the type field per type you can inline type
tests.
In article <···················@mexican.cygnus.com>,
D. V. Henkel-Wallace <·····@mexican.cygnus.com> wrote:
> Date: 23 Feb 94 09:56:00
> From: ····@ai.mit.edu (John McClain)
>
> I have not not read about any implementation that puts tags in a
> separate array. Does anyone have any experience with, know an
> implementation that uses, or seen a paper that analyzes this
> technique.
> You would seem to win on portability and the ability to keep
> floats "unboxed."
>
>One common way to do this is called "BIBOP" (Big Bag Of Pages) which
>was used in maclisp.
>
>The disadvantage is that you have to do two memory reference to
>determine something's type. On a modern RISC machine, with larger
>address space than we used to have, it's not worth the compactness.
>With only one value of the type field per type you can inline type
>tests.
You have to do *separate* memory references to determine the type and
to dereference a pointer. This is indeed bad unless 1) the space
savings over tagged pointers are more important than speed, or 2) the
compiler is good enough that most of the type tests are elided. Even
so, if the descriptors are all in one place the extra reference may
not be so bad locality-wise.
With respect to 1), the putting-the-tags-in-the-pointer approach
usually allows for only a few bits worth of tag, so you have to allow
for storing type info in the object itself for everything that does
not get its own tag. With BiBoP, it is practical to have a descriptor
for each type. (I just finished re-engineering an implementation to
use a BiBoP because the space savings made a big difference for the
particular application -- there were more than a few bits worth of
heavily used types and so a lot of memory was wasted being on
secondary descriptors.) Also, there is no need to mask the tag bits
out of a reference before dereferencing its pointer.
The technology to do 2) is still immature, though the Python compiler
makes it worth betting on to at least show in the long run.
Other than that, BiBoP can be wasteful of address space since the pool
of available space is divvied up amongst all the pages. This would
not be too bad if you could just partition a large enough address
space among the types without having to allocate memory for parts that
have not been used yet, but most OSes conspire against such an
approach.
Back to the original question: The Symbolics virtual Ivory
implementation for the AXP appears to do what you suggest by keeping
the tags separate from the pointers and immediate objects. As I
understanded it, the rational for doing it this way was to allow for
full 32-bit "virtual virtual" word addresses to be stored in a natural
way and so it wasn't necessary to box and unbox data shared with
external programs. The guy I talked to claimed that this was not as
awful as it sounds since the tag fetch could be interleaved around
other work being done by the emulator, though he did bitch about the
direct-mapped cache on the 21064.
There was a pretty complete survey of run-time type representations
published last year, but I have not been able to track down a full
reference.
--David Gadbois
The extra fetch in BiBoP slows things down, but the greater compactness
of the data should give you less-frequent garbage collections, speeding
things up. So which way does it really go?
Date: Thu, 24 Feb 1994 08:58:56 GMT
From: ······@well.sf.ca.us (Darius Bacon)
The extra fetch in BiBoP slows things down, but the greater compactness
of the data should give you less-frequent garbage collections, speeding
things up. So which way does it really go?
It's impossible to answer a priori.
The data aren't really more compact in terms of taking up less space;
memory is more _dense_ which is a different matter. _n_ objects will
still take up approximately _n_ words of pointers either way. But
BIBOP could be a win for systems (like most unix implementations) with
poor VM architectures that don't allow holes in the address space.
By the way, I wasn't explicit enough on the theoretically poor
reference characteristics of BIBOP. It isn't just that you need to do
at least two memory references to do type-of, but that they are
necessarily serial.
Rather shockingly (to me) this illustrates one example of an advantge
of RISC for lisp implementations: on the PDP-10 I would just do an
indirect reference, which is of course impossible on most RISC
machines; I have to do two explicit references. Modern compilers will
reorder my code to avoid a pipeline stall.
In article <··········@peaches.cs.utexas.edu> ·······@cs.utexas.edu (David Gadbois) writes:
== Date: 23 Feb 94 09:56:00
== From: ····@ai.mit.edu (John McClain)
==
== I have not not read about any implementation that puts tags in a
== separate array. Does anyone have any experience with, know an
== implementation that uses, or seen a paper that analyzes this
== technique.
=
= Back to the original question: The Symbolics virtual Ivory
= implementation for the AXP appears to do what you suggest by keeping
= the tags separate from the pointers and immediate objects.
Does anyone have any more information on the Symbolics virtual Ivory,
I would be _REALLY_ interested to find out how well this worked.
= There was a pretty complete survey of run-time type representations
= published last year, but I have not been able to track down a full
= reference.
Any one else have a reference to this paper, a name, a place?
John McClain