Introducing Shenandoah Traversal mode – part I
July 5, 2018 19 Comments
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:
- Concurrent mark: traversal all live objects, starting from roots, and mark each visited object as live.
- Concurrent evacuation: based on liveness information from concurrent marking, select a number of regions, compact all live objects in that region into fresh regions.
- 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:
- 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.
- 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:
- Visit each live object, starting from roots
- When encountering an object that is in the collection-set, evacuate it to a fresh compaction region
- 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.