Shenandoah GC in JDK 13, Part 1: Load reference barriers

In this series of articles, I will introduce some new developments of the Shenandoah GC coming up in JDK 13. Perhaps the most significant, although not directly user-visible, change is the switch of Shenandoah's barrier model to load reference barriers. This change resolves one major point of criticism against Shenandoah—the expensive primitive read-barriers. Here, I'll explain more about what this change means.

Shenandoah (as well as other collectors) employs barriers to ensure heap consistency. More specifically, Shenandoah GC employs barriers to ensure what we call "to-space-invariant." This means when Shenandoah is collecting, it is copying objects from so-called "from-space" to "to-space," and it does so while Java threads are running (concurrently).

Thus, there may be two copies of any object floating around in the JVM. To maintain heap consistency, we need to ensure either that:

• writes happen into to-space copy + reads can happen from both copies, subject to memory model constraints = weak to-space invariant, or that
• writes and reads always happen into/from the to-space copy = strong to-space invariant.

The way we ensure this is by employing the corresponding type of barriers whenever reads and writes happen. Consider this pseudocode:

void example(Foo foo) {
  Bar b1 = foo.bar;             // Read
  while (..) {
    Baz baz = b1.baz;           // Read
    b1.x = makeSomeValue(baz);  // Write
}

Employing the Shenandoah barriers, it would look like this (what the JVM+GC would do under the hood):

void example(Foo foo) {
  Bar b1 = readBarrier(foo).bar;             // Read
  while (..) {
    Baz baz = readBarrier(b1).baz;           // Read
    X value = makeSomeValue(baz);
    writeBarrier(b1).x = readBarrier(value); // Write
}

In other words, wherever we read from an object, we first resolve the object via a read-barrier, and wherever we write to an object, we possibly copy the object to to-space. I won't go into the details here; let's just say that both operations are somewhat costly.

Notice also that we need a read-barrier on the value of the write here to ensure that we only ever write to-space-references into fields while heap references get updated (another nuisance of Shenandoah's old barrier model).

Because those barriers are a costly affair, we worked quite hard to optimize them. An important optimization is to hoist barriers out of loops. In this example, we see that b1 is defined outside the loop but only used inside the loop. We can just as well do the barriers outside the loop, once, instead of many times inside the loop:

void example(Foo foo) {
  Bar b1 = readBarrier(foo).bar;  // Read
  Bar b1' = readBarrier(b1);
  Bar b1'' = writeBarrier(b1);
  while (..) {
    Baz baz = b1'.baz;            // Read
    X value = makeSomeValue(baz);
    b1''.x = readBarrier(value);  // Write
}

And, because write-barriers are stronger than read-barriers, we can fold the two up:

void example(Foo foo) {
  Bar b1 = readBarrier(foo).bar; // Read
  Bar b1' = writeBarrier(b1);
  while (..) {
    Baz baz = b1'.baz;           // Read
    X value = makeSomeValue(baz);
    b1'.x = readBarrier(value);  // Write
}

This is all nice and works fairly well, but it is also troublesome, in that the optimization passes for this are very complex. The fact that both from-space and two-space-copies of any objects can float around the JVM at any time is a major source of headaches and complexity. For example, we need extra barriers for comparing objects in case we compare an object to a different copy of itself. Read-barriers and write-barriers need to be inserted for *any* read or write, including primitive reads or writes, which are very frequent.

So, why not optimize this and strongly ensure to-space-invariance right when an object is loaded from memory? That is where load reference barriers come in. They work mostly like our previous write-barriers, but are not employed at use-sites (when reading from or storing to the object). Instead, they are used much earlier when objects are loaded (at their definition-site):

void example(Foo foo) {
  Bar b1' = loadReferenceBarrier(foo.bar);
  while (..) {
    Baz baz = loadReferenceBarrier(b1'.baz); // Read
    X value = makeSomeValue(baz);
    b1'.x = value;                           // Write
}

You can see that the code is basically the same as before —after our optimizations—except that we didn't need to optimize anything yet. Also, the read-barrier for the store-value is gone, because we now know (because of the strong to-space-invariant) that whatever makeSomeValue() did, it must already have employed the load-reference-barrier if needed. The new load-reference-barrier is almost 100 percent the same as our previous write-barrier.

The advantages of this barrier model are many (for us GC developers):

• Strong invariant means it's a lot easier to reason about the state of GC and objects.
• Much simpler barrier interface. In fact, a lot of stuff that we added to GC barrier interfaces after JDK11 will now become unused: no need for barriers on primitives, no need for object equality barriers, etc.
• Optimization is much easier (see above). Barriers are naturally placed at the least-hot locations: their def-sites, instead of their most-hot locations: their use-sites, and then attempted to optimize them away from there (and not always successfully).
• No more need for object equals barriers.
• No more need for "resolve" barriers (a somewhat exotic kind of barriers used mostly in intrinsics and places that do read-like or write-like operations).
• All barriers are now conditional, which opens up opportunities for further optimization later.
• We can re-enable a bunch of optimizations, like fast JNI getters that needed to be disabled before because they did not play well with possible from-space references.

For users, this change is mostly invisible, but the bottom line is that it improves Shenandoah's overall performance. It also opens the way for additional improvements, such as elimination of the forwarding pointer, which I'll get to in a follow-up article.

Load reference barriers were integrated into JDK 13 development repository in April 2019. We will start backporting it to Shenandoah's JDK 11 and JDK 8 backports soon. If you don't want to wait, you can already have it: check out the Shenandoah GC Wiki for details.

Read more

Shenandoah GC in JDK 13, Part 2: Eliminating the forward pointer word

Shenandoah GC in JDK 13, Part 3: Architectures and operating systems