[Gc] Question about two-level tree

Boehm, Hans hans_boehm@hp.com
Thu, 16 Jan 2003 11:51:03 -0800

IIRC, there is no strong argument for the current approach.  What you suggested is probably simpler.  It may or may not be faster.

I think the performance tradeoff isn't completely clear one way or the other.  If several entries map to the same block header, you would have to look up the block starting address in the header, or something along those lines.  That would add some overhead.  And you'd have to be careful that it didn't add overhead to the common case (which probaby occurs 99.999% of the time), in which the pointer references the first page of a block.

This was never changed, mostly because the comparison with the other technique was never done, and I suspect it doesn't make much difference either way.


-----Original Message-----
From: Mike Spivey
To: gc@napali.hpl.hp.com
Sent: 1/16/03 10:37 AM
Subject: [Gc] Question about two-level tree

I have been studying the data structures used by the GC, and I'm
puzzled about the two-level tree that's used to find the start of an
object given an interior pointer.  Why is it a good idea to describe
large objects by giving a displacement to the beginning of the object,
rather than having all the entries for the object point to a single
block header for the whole object?  It seems to me that the
displacement idea is just a more complicated way of finding the same

-- Mike
Gc mailing list