02 December 2010

Can junk compaction be done with the Boehm GC?

Can junk compaction be done with the Boehm garbage collector?

When I first started this blog, I blogged about junk compaction, which is akin to garbage collection, but instead of throwing out objects that have no use at all, it transforms objects that have a lot of "scratch space" into a more compact form when they are inactive.

The Boehm garbage collector doesn't give us access to generational information, which was my original idea for implementing junk compaction. It does give us a fair amount of flexibility, though. So let's revise the idea: Don't try to figure out whether the junky object is stale. Just assume that it is stale if referenced only by junk-releasing references - akin to weak pointers.

The Boehm GC does give us an opening for this: Finalization can leave an object alive if it points to itself. And we can make weak links by hiding pointers.

First idea (not so hot)

  • Hold objects to be junk-collected only thru non-junk-releasing pointers and weak links.
  • So it will get finalized when it's no longer useful.
  • During finalization
    • Build the compact version (allocate it - is this OK during finalization in Boehm gc?)
    • Change the weak links into real links to the compact version.

The last is the hard part because it requires finding all links to the object, unhiding them, and changing them to point to the compact version. GCregisterdisappearinglink could probably do it "under the hood", but it doesn't expose any such functionality. It would have to be prearranged on every link anyways, which is the reverse of what we want: The non-junk-releasing pointers are special, not the junk-releasing ones.

Second idea: Handles

It could work if junk-collected objects are only held by handles and normal (non-junk-releasing) pointers. The handle would hold it by a weak pointer and it would point to the handle by a normal pointer. Thus if nothing is holding the object directly (not thru the handle), it will soon be finalized and thus compacted.

When finalized, it would make the handle point to the compact object and indicate this. And of course make the pointer to the handle disappear.

Third idea: Handles that become the compact object

This still leaves a superfluous handle. Is there some way to telescope it to actual reference? We must do so all at once, not piecemeal, so it doesn't mess up pointer comparison.

So instead, realloc the handle to be the size of the compact object and change it into that object.

This seems like it would work.

No comments:

Post a Comment