DFS or BFS traversal in Parallel Scavenge (or Parallel new) GC

[Jon Masamitsu]

Junjie,

If you want a definitive answer, you really have to go
look at the code.   If you're willing to take my best
recollection then read on.

On 02/23/2015 02:28 PM, Junjie Qian wrote:
> Dear all,
>
> I am reading the Parallel scavenge GC implementation in OpenJDK1.7, 
> and having a question regarding the way how the parallel GC threads 
> traverse the heap graph to mark the live objects.
>
> The question is, does one GC thread traverse the graph in DFS or BFS 
> way in Parallel scavenge (or parallel new)?
UseParallelGC had both DFS and BFS under a flag.  I think the BFS was 
removed in 7.

>
> There are two conflicting sources suggesting the answer:
> 1. the paper on ASPLOS'13, "A study of the scalability of 
> stop-the-world garbage collectors on multicores", in Section 2.3.3. 
> the author says "A GC thread performs a breadth-first traversal (BFT) 
> of the graph of live objects".
>
> 2. the reply in this mailist, "Request for review (S): 8005972: ParNew 
> should not update the tenuring threshold when promotion failed has 
> occurred" , Ramki said "ParNew's slightly more DFS-like evacuation 
> compared with DefNew's considerably more BFS-like evacuation because 
> of the latter's use of a pure Cheney scan compared with the use of (a) 
> marking stack(s) in the former"

Trust Ramki's description at that time, but I would have called 
UseParNewGC predominantly BFS.
>
> A lot of references online explains Parnew uses the same parallel GC 
> algorithm as ParallelScavenge, please correct me if I made a mistake 
> on this one.

UseParallelGC and UseParNewGC are both copying collectors that use 
multiple threads so
in that since they use the same algorithm.    They share very little 
code.  UseParNewGC
works with CMS and makes some accommodations for CMS.   Kinda of like a Ford
and a Chevy are both cars.

Jon

> Thanks!
> Best
> Junjie
>
>
> _______________________________________________
> hotspot-gc-use mailing list
> hotspot-gc-use at openjdk.java.net
> http://mail.openjdk.java.net/mailman/listinfo/hotspot-gc-use

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-gc-use/attachments/20150224/f844d9f0/attachment.html>