Threading A Graph

One operation that moving garbage collectors (among other things) have to concern themselves with is updating of references. Once you move object X from position P0 to P1, you’ll also need to update all references to X accordingly. To be able to do this, you first need to somehow maintain a list of words that point to a specific object. There are obvious ways of this, of course — maintaining a hash-table that maps a object to a list of words that store references to it is one. There is a more elegant way to do this, however; if the set of objects you’re working with satisfies the following constraints:

  • Each object has a (header or otherwise) pointer-sized field which stores some information that can be differentiated from a pointer. On a system that is aligns words to two or four byte boundaries, we could set the LSB of non-pointer data stored in the field. We’ll call this field info.
  • Pointers to objects always point to the beginning of some object. No pointing to a field stored somewhere in the middle.

The algorithm is extremely simple and elegant. All you have to do is this: every time you see a slot (a field, if you like) S point to an object O, change Os info field to point to slot S and set S to whatever value (pointer or non-pointer) info held before it was set to point to S. If you try this out with pen and paper (I’m too lazy to draw a diagram here), you’ll see that this simple action, when applied to every slot in the graph, transforms the predicate “Slots S0, S1 and S2 point to object O” to “O‘s info slot contains a pointer to S2, S2 contains a pointer to S1, S1 contains a pointer to S0 and S0 contains the data O‘s info field originally held”. Since we can always distinguish a data word stored in info from a pointer, we can traverse this list and get a list of the slots. The slots can then be filled with new location of the object.

This is one of the main concepts behind Jonker’s compaction algorithm, except that it intelligently divides the compaction into two phases of updating forward pointers and updating backward pointers while moving objects.

I wrote a simple and tiny implementation of threading a graph, which you can find at https://github.com/sanjoy/Snippets/blob/master/Thread.cc. Note how the main threading algorithm only takes thirteen lines of C++.

Advertisements
This entry was posted in Computers and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s