Tagging

[bryce at kampjes.demon.co.uk]

I'd doubt that using the top bits has any significant advantages
over using the bottom bits with a zero integer tag. Using the top
bits adds the problem of getting the OS to allocate memory to fit
around that policy.

Jason Johnson writes:
 > Thanks Bryce and Andrew for your quick and informative responses.
 > Comments/questions below.
 > 
 > On 8/4/07, bryce at kampjes.demon.co.uk <bryce at kampjes.demon.co.uk> wrote:
 > >
 > >
 > > You don't need to shift the numbers for addition and subtraction, just
 > > make sure the bottom bits are 0. Even with the tag being 1, you
 > > only need to detag one argument and if that's a constant the
 > > detagging can be done at compile time.
 > >
 > > With multiplication and division only one argument needs to be
 > > shifted.
 > 
 > 
 > 
 > Interesting.  Well, I assume that in Smalltalk object access is much more
 > often then integer access, but does anyone have any data that proves this?
 > If it is the case then I guess that's the death of my MSB tagging idea. :)
 > 
 > Doesn't Strongtalk use 0 tagged SmallIntegers?  And if so, why?  I looked in
 > the source code a bit but I haven't figured out yet where that would be.

Yes.

The trick is detagging pointers can be  done using offet addressing so
that's  free   as  well  as  detagging     integers for  addition  and
subtraction. So by using a zero tag there's no overhead for common
operations. There's a single shift for multiplication and division but
both these operations can be slow.



 > 
 > > It was used by some Lisp systems in the mid 80's. I think CMU Common
 > > Lisp from memory.
 > >
 > > There are two disadvantages of using the top bit:
 > > 1) You need to control the address space to make sure all objects
 > > live. Controlling the address space to that degree is unlikely to
 > > be something that can be done portably.
 > > 2) You loose half your address space.
 > 
 > 
 > 
 > Well, I suppose I could shift the pointers up one (which would make the
 > first bit zero) to reclaim the space, but as I believe it must be the case
 > that object access is much more common then number access, that would be a
 > bad trade-off.
 > 
 > 
 > Alignment. Words are aligned to 4 byte boundaries which is always
 > > required for performance and required by some CPU architectures.
 > 
 > 
 > 
 > I see, I didn't realize the bottom 2 bits had to be zero.  That answers a
 > lot of my questions. :)
 > 
 > There is a large literature on garbage collection. These day's I'd try
 > > citeseer as well as Google. Scanning PLDI and OOPSLA proceedings from
 > > the late 70s and 80s will provide plenty of information if you've
 > > either got ACM membership or access to a university library.
 > >
 > > Bryce
 > 
 > 
 > 
 > I have the "Garbage Collection" book from Jones & Lins, but I will try to
 > look on those sites as well.  I just need to go to the "ACM digital
 > library", no?

ACM digital library should work. I'm not a member so can't say
for sure. Most papers are availible for free for recent stuff and
the key classics are slowly appearing too.

Bryce