Depth first object copying for all GC?

[Tangwei (Euler)]

I am just curious why no option to control the copy policy at beginning. Anyway, thanks a lot for your detailed explanation.

wei

-----Original Message-----
From: Peter B. Kessler [mailto:Peter.B.Kessler at Oracle.COM] 
Sent: Saturday, May 09, 2015 4:26 AM
To: Tangwei (Euler); hotspot-gc-dev at openjdk.java.net
Subject: Re: Depth first object copying for all GC?

On 05/ 8/15 02:02 AM, Tangwei (Euler) wrote:
> As I mentioned at start, the slides shows some performance gain to hashMap if GC copies object in Depth first.
>
>>> http://www.oracle.com/technetwork/server-storage/ts-6434-159339.pdf
>
> The BZ shows OpenJDK has already tracked the object copying issue, although I failed to find it from commit log.
> I just want to confirm if such policy has been applied in ParallelGC. From Jon's comments, it is true.
> My understanding is depth first will benefit to cache locality, is there any other consideration on copy order choosing?

If your application traverses your data depth-first (e.g., HashMap lookup, as in http://www.oracle.com/technetwork/server-storage/ts-6434-159339.pdf, slide 41), then depth-first copying by the collector will probably be good for you.  (And it will improve the cache behavior of subsequent depth-first copying by the collector. :-)  If your application uses your data breadth-first, then depth-first copying may spread out the objects at each level where you might prefer to have them closer together.  This discussion is about the scavenging parts of the collectors; the sliding compacting parts of the collectors do not reorder objects.

You might be able to construct an example with a data structure where you spend your time walking across siblings at each level before dropping down to the next level.  If you build such a data structure breadth-first (allocating the nodes at one level before allocating any of the nodes at the next level down), you can probably observe the change in traversal performance before and after the first depth-first copying collection.

Benchmarking the collectors is hard.  Among other reasons: if the only data structure you have is your test data structure, then the parallel copying collectors are likely to fight over it and distribute it around memory.

The summary is: It depends on your application.  Over time, if people find that depth-first data structures perform better than breadth-first data structures, then they will prefer depth-first data structures, and when VM engineers write new collectors they will find that depth-first copying gets them better benchmark scores than breadth-first copying.

			... peter

>>> https://bugs.openjdk.java.net/browse/JDK-6450584: Improve object 
>>> copying order in parallel scavenge
>
> -----Original Message-----
> From: Peter B. Kessler [mailto:Peter.B.Kessler at Oracle.COM]
> Sent: Friday, May 08, 2015 5:00 AM
> To: Tangwei (Euler Architecture & Design Dept); 
> hotspot-gc-dev at openjdk.java.net
> Subject: Re: Depth first object copying for all GC?
>
> I think the UseParallelGC collector does something other than strict depth-first or breadth-first for processing large arrays of object references.  A worker can claim part of the array to work on (depth-first?) before going back to claim the next part of the array (breadth-first).  Part of the motivation was to partition the large array among several workers, but part of the motivation was to avoid blowing out the marking stack by pushing all the elements of a large array.
>
> This might be PSPromotionManager::process_array_chunk(oop). but it's been too long since I was really in that code.  It looks like the last N elements of the array are claimed, then the length of the forwarding copy of the array is shortened so subsequent steals will claim chunks from the new end of the array.  So that's like breadth-first within a chunk, but backwards breadth-first by chunks.  The size of a chunk looks like it can be controlled by the command line option -XX:ParGCArrayScanChunk=, but I don't know how much experimentation went into choosing the default value (50, in the code I'm looking at).
>
> That code might only be used for marking, not for copying, which is what the original post asked about.  The sliding compactors don't *copy* depth-first or breadth-first: they figure out where the objects are going, then they move the objects, conceptually in address order.  Except the parallel compactor does the sliding compaction in parallel, so it's not even in address order, e.g., as the memory system sees the requests.
>
> What are you really asking about?  What kind of an answer do you want?
>
> 			... peter
>
> On 05/ 7/15 11:51 AM, Jon Masamitsu wrote:
>>
>>
>> On 05/06/2015 07:56 PM, Tangwei (Euler Architecture & Design Dept) wrote:
>>>
>>> Would you help to list the object copying policy for different GC?  Or pointing out where to find such information?
>>>
>>
>> For the most part UseParallelGC and UseG1GC has depth-first copying.
>> UseConcMarkSweepGC and UseSerialGC use breadth-first.  I qualify that 
>> because I've heard people argue about whether that's 100% true.
>>
>> Jon
>>
>>> Regards!
>>>
>>> wei
>>>
>>> *From:*hotspot-gc-dev
>>> [mailto:hotspot-gc-dev-bounces at openjdk.java.net] *On Behalf Of * Jon 
>>> Masamitsu
>>> *Sent:* Thursday, May 07, 2015 8:23 AM
>>> *To:* hotspot-gc-dev at openjdk.java.net
>>> *Subject:* Re: Depth first object copying for all GC?
>>>
>>> On 5/6/2015 4:34 AM, Tangwei (Euler Architecture & Design Dept) wrote:
>>>
>>>      Hi All,
>>>
>>>        As a newbie in GC, I found some discussion on object copying order in following slides: breadth vs. depth.
>>>
>>>      It mentioned that /"Any static policy will hurt some 
>>> applications and help others". /After searching, there is a BZ shows
>>>
>>>      the object copying order has been switched from breadth to depth for ParallelGC in OpenJDK, please correct if I am wrong.
>>>
>>>      Anyone can help to confirm if all GC in OpenJDK use depth first copying now?
>>>
>>>
>>> No, not all the GC's use depth first copying.
>>>
>>>
>>> Is there any performance consideration to choose depth first instead of controlling by option?
>>>
>>>
>>> Yes, there is a performance cost to optionally using depth-first or breadth-first.
>>> ParallelGC used to have such an option.  It made the code harder to 
>>> maintain and, as far as I can recall, there was very little use of 
>>> the option.  We removed the it.  I recall maybe 1 complaint about it.
>>>
>>> Jon
>>>
>>>
>>> http://www.oracle.com/technetwork/server-storage/ts-6434-159339.pdf
>>>
>>> https://bugs.openjdk.java.net/browse/JDK-6450584: Improve object 
>>> copying order in parallel scavenge
>>>
>>> Regards!
>>>
>>> wei
>>>
>>
>
>