Depth first object copying for all GC?

[Tangwei (Euler)]

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? 

>> 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
>>
>