Potential optimization to the GC termination protocol in JDK8

[Thomas Schatzl]

Hi,

  sorry for being somewhat late in that thread... busy lately...

On Thu, 2018-04-26 at 08:53 +0200, Roman Kennke wrote:
> > > [Problem]
> > > The work stealing during the GC takes lots of time to terminate.
> > > The Parallel Scavenge in JDK 8 uses a distributed termination
> > > protocol to synchronize GC threads. After 2 ∗ N consecutive
> > > unsuccessful steal attempts (steal_best_of_2 function), a GC
> > > thread enters the termination procedure, where N is the number of
> > > GC threads.
> > > 
> > > Suppose there are N GC threads, it takes 2 * N * N failed
> > > attempts before a GC stops. It is inefficient and takes too much
> > > time, especially when there are very few GC threads alive. If
> > > there are hundreds or thousands of GC happen during the app
> > > execution, that is a big waste of time.
> > > 
> > > [Solution]
> > > Is that possible to reduce the number of steal attempt during the
> > > end of GC? My idea is to record the number of active GC threads
> > > (i.e., N_live) that are not yet in the termination protocol. A
> > > thread only steals from the pool of active GC threads because the
> > > inactive GC threads have no task to be stolen. Accordingly, the
> > > criteria for thread termination becomes 2 ∗ N_live consecutive
> > > failed steal attempts. It can reduce the steal attempts to half.
> > > 
> > > Good forward for others' feedbacks.

Sure we are interested in such an enhancement and would appreciate a
contribution. However new work should be conducted in the latest
version only, i.e. at this time JDK 11 (and probably JDK 12 by the time
such a change would be pushed given the FC date of end of June).

Maybe by coincidence you might be one of the authors of a recent paper
[1] demonstrating this? If you are interested in contributing, please
have a look at the corresponding wiki page [4].

> > > Thanks.
> > > Tony
> 
> Hi Tony,
> in Shenandoah we have implemented an improved termination protocol.
> See the comment here:
> 
> http://hg.openjdk.java.net/shenandoah/jdk/file/b4a3595f7c56/src/hotsp
> ot/share/gc/shenandoah/shenandoahTaskqueue.hpp#l93
> 
> We intend to upstream this stuff very soon, at which point it can be
> used by all other GCs if they wish. It's a drop-in replacement for
> the existing task queue code.
> 
> It sounds like it's similar to what you have in mind. Right?

The ShenandoahTaskTerminator is different in that it optimizes the
amount of woken up threads and the detection of that there is work to
steal.

The suggestion presented here improves work stealing itself, i.e. how
the woken up threads search for threads.

Note that I think that with the ShenandoahTaskTerminator such an
implementation would be easier to implement than with the existing
ParallelTaskTerminator.

There are other ideas and information about known not-optimal-
implementation floating around in literature (e.g. [1][2][3], but
recently I looked there are a lots) to improve this even further.

Thanks,
  Thomas

[1] Kun Suo, Jia Rao, Hong Jiang, and Witawas Srisa-an. 2018.
Characterizing and optimizing hotspot parallel garbage collection on
multicore systems. In Proceedings of the Thirteenth EuroSys Conference
(EuroSys '18). ACM, New York, NY, USA, Article 35, 15 pages. DOI: https
://doi.org/10.1145/3190508.3190512
[2] Junjie Qian, Witawas Srisa-an, Du Li, Hong Jiang, Sharad Seth, and
Yaodong Yang. 2015. SmartStealing: Analysis and Optimization of Work
Stealing in Parallel Garbage Collection for Java VM. In Proceedings of
the Principles and Practices of Programming on The Java Platform (PPPJ
'15). ACM, New York, NY, USA, 170-181. DOI: http://dx.doi.org/10.1145/2
807426.2807441
[3] Lokesh Gidra, Gaël Thomas, Julien Sopena, Marc Shapiro, and Nhan
Nguyen. 2015. NumaGiC: a Garbage Collector for Big Data on Big NUMA
Machines. In Proceedings of the Twentieth International Conference on
Architectural Support for Programming Languages and Operating Systems
(ASPLOS '15). ACM, New York, NY, USA, 661-673. DOI: https://doi.org/10.
1145/2694344.2694361
[4] http://openjdk.java.net/contribute/