Introducing Shenandoah Traversal mode – part I

In this post I want to introduce a (not so very) new GC mode that we call “Traversal GC”. It all started over a year ago when I implemented the ‘partial’ mode. The major feature of the partial mode is that it can concurrently collect a part of the heap, without the need to traverse all live objects, hence the name partial GC. I will go into details of how that works in a later post. First I would like to explain another foundation of Shenandoah’s partial GC, which is the single-traversal-GC, or short Traversal GC.

Let me first show some pictures that explain how Shenandoah works (and in-fact, more or less how other collectors work):

Shenandoah usually runs in one of two modes (switched dynamically depending on automatic ergonomic decisions): First the 3-phase mode:

The cycles are:

1. Concurrent mark: traversal all live objects, starting from roots, and mark each visited object as live.
2. Concurrent evacuation: based on liveness information from concurrent marking, select a number of regions, compact all live objects in that region into fresh regions.
3. Concurrent update-refs: scan all live objects and update their references to point to the new copies of the compacted objects.

Each concurrent phase is book-ended by a stop-the-world phase to safely scan GC roots (thread stacks) and do some housekeeping. That makes 4 (very short, but still measurable) pauses during which no Java thread can make progress.

When GC pressure is high, and GC cycles run close to back-to-back, Shenandoah switches to 2-phase operation. The idea is to skip concurrent update-refs phase, and instead piggy-back it on subsequent concurrent marking cycle:

In other words, we now have:

1. Concurrent mark: traversal all live objects, starting from roots, and mark each visited object as live. At the same time, when encountering references to from-space, update the to point to the to-space copy.
2. Concurrent evacuation: based on liveness information from concurrent marking, select a number of regions, compact all live objects in that region into fresh regions.

As before, we still have pauses before and after each phase, now totalling 3 stop-the-world pauses per cycle.

Can we do better? Turns out that we can:

Now we only have one concurrent phase during which we:

1. Visit each live object, starting from roots
2. When encountering an object that is in the collection-set, evacuate it to a fresh compaction region
3. Update all references to point to the new copies.

The single concurrent phase is book-ended by 2 very short stop-the-world phases.

This probably sounds easy and obvious, but the devil lies, as usual, in some interesting details:

• How to select the collection-set? We have no liveness information when we start traversing.
• How to ensure consistencies:
  • Traversal consistency: how to deal with changing graph shape during traversal
  • Data consistency: how to ensure writes go to the correct copy of objects, how to ensure reads don’t read stale data, etc
  • Update consistency: how to avoid races between updating of references and ordinary field updates

I will go into those details in a later post.

If you’re interested in trying out the traversal mode, it’s all already in Shenandoah (jdk10, jdk11 and dev branches) and stable enough to use. Simply pass -XX:ShenandoahGCHeuristics=traversal in addition to the usual -XX:+UseShenandoahHeap on the command line. More information about how to get and run Shenandoah GC can be found in our Shenandoah wiki.