[gclist] Re: finding object prefix from infix pointer

[Hans Boehm]

On Jul 9,  2:15pm, marc.shapiro@inria.fr wrote:
> Subject: [gclist] Re: finding object prefix from infix pointer
>  || Date: Fri, 9 Jul 1999 08:07:03 +0200
>  || From: Francois-Rene Rideau <fare@tunes.org>
>  || Subject: [gclist] finding object prefix from infix pointer
>  ||
>  || But it looks like we've moved from the topic of implementing read/write
>  || barriers to a _completely_ different (and orthogonal, it seems to me)
>  || topic of identifying object head from an infix pointer (assuming your
>  || implementation uses unguarded infix pointers).
>
> I'm interested in a discussion of the alternatives: this is a costly
> operation.
>
> Hans, how does the conservative collector do this?
>
Each block (roughly page) of the heap contains objects of a fixed size.  The
block has an associated descriptor which can be found by looking up the high
order bits of the address in a two level tree.  Once you know the size of
objects in the block, you can map to the beginning of the object with
essentially a remainder operation on the low order bits.  Since integer
division tends to be slow, this is really replaced by a table lookup.

I believe the cost in the 32-bit case is something like 5 memory accesses, a
couple of predictable branches, and a few shifts and ANDs.  For pointers into
the interior of large objects, or with 64-bit pointers, it takes slightly
longer.  Interestingly, the presence of the table lookup means that it doesn't
matter whether you recognize all interior pointers or only pointers to certain
fixed offsets within the object.  Only table initialization is affected.

Most of this work is also useful for getting to the mark bit table, which is in
the same block descriptor.  Even if you didn't allow any interior pointers, you
would have to do most of the work, or keep mark bits with objects.  The latter
is usually a very bad idea, as I learned the hard way.

You could do slightly better if you assumed a contiguous, or near-contiguous,
heap.

I've been thinking about adding an optional mostly-copied nursery for small
objects with known layout to my collector.  It will probably use a different
data structure, since its goals and constraints are very different.

The data structure is described in more detail in

http://reality.sgi.com/boehm/tree.html

Hans


-- 
Hans-J. Boehm
boehm@sgi.com