Shenandoah GC: Brooks pointers

I didn’t write about Shenandoah in a while. We first needed to clear up some issues around it, which is done now. The project is not dead yet, quite the contrary, we’re working feverishly. Just now, we are about concurrent evacuation to work :-)

Last time I wrote about concurrent marking. Before I carry on, I want to introduce a new concept: Brooks pointers. The idea is that each object on the heap has one additional reference field. This field either points to the object itself, or, as soon as the object gets copied to a new location, to that new location. This will enable us to evacuate objects concurrently with mutator threads (how exactly this is done is a topic for a separate post).

One problem of course is that as soon as we have two copies of an object (one in from-space, one in to-space), we need to be careful to maintain consistency. This means that any changes to objects must happen in the to-space copy. This is achieved by putting barriers in various places (everything that writes to objects, or runtime code that uses objects) that resolve the object before writing into it or using it. If we don’t do that, we might end up with some threads using the old copy, and some threads using the new copy, which is, obviously, a problem. The barrier simply reads the brooks pointer field and returns the forwarded object to any code that uses it. In terms of machine code instructions, this means one additional read instruction for each write operation into the heap (and some read operations by the runtime). Infact, we currently need two instructions, the reason for which I’ll explain later.

Eventually, when evacuation is done, we need to somehow update all references to objects to point to the to-space locations. We do that by piggy-backing on the concurrent marking phase. When we traverse the heap for marking, we see all live objects and references, and whenever we visit an object, we update all its object references to point to the new locations of the referents.

There’s two tradeoffs with using brooks pointers: we need more heap space (ideally, one word per object), and we need more instructions to read and write objects.

Next time, I’ll start explaining how concurrent evacuation works.

Because there have been many requests: yes, Shenandoah will be open source. Our plan is to propose a JEP as soon as we can, and make it an OpenJDK project if possible.

About these ads

6 Responses to Shenandoah GC: Brooks pointers

  1. Clemens Eisserer says:

    I already wondered how all the nice features mentioned in the last blog posts will be implement, now I realized there is no magic involved ;)

  2. Its unfortunate that this blog post hasn’t described the locality of reference impact that forwarding pointers introduce. During the period of time that you’ve got the forwarding pointer in place you’ve a pointer-chasing indirection overhead. Obviously the sooner that you repair the object pointers that refer to your forwarding pointer the quicker you reduce that indirection overhead.

    In the blog post itself you specifically talk about tradeoffs as well stating, “There‚Äôs two tradeoffs with using brooks pointers: we need more heap space (ideally, one word per object), and we need more instructions to read and write objects.” Its not just more instructions, its more indirection, albeit temporary indirection.

    It may be obvious to programmers who professionally work on GC implementation that these costs exist but I think its the kind of subtle point that a casual reader might well gloss over. Pointer chasing isn’t insignificant either due to the higher likelihood of cache misses.

    I hope this doesn’t come across overly critical of the blog post btw. I think its great that you guys are taking the time to share and explain implementation detail!

  3. sirinath says:

    Where is the code now?

  4. sirinath says:

    Perhaps this can also be contributed to Mono and VMKit with slight modification. Think about licensing implications also.

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

Follow

Get every new post delivered to your Inbox.

Join 159 other followers

%d bloggers like this: