Parallel GC and array object layout: way off the base and laid out in reverse?

[Tony Printezis]

What Igor said.

A few extra notes:

When I did the depth-first implementation in PS I did change the 
scanning order for instances so that refs will be pushed backwards on 
the stack and, hence, they will be popped and copied in the 'correct 
order'. I had also tried that for arrays but I was seeing, at the time, 
some performance regressions and I decided to back out of the backwards 
iteration for arrays and only keep it for instances. You might want to 
re-evaluate that. It won't take too long to prototype the change in PS 
to do an experiment.

G1 should also have depth-first copying (Igor, didn't you implement it?) 
so it should behave similarly to PS.

Performance of forward array iteration might or might not be important. 
For hash tables, it's all about look-ups, so the order should not 
matter. It should only matter if you do a lot of whole array traversals. 
It might be important for something like ArrayLists.

Regarding "I don't like surprises" : Thomas' reply was spot on. The 
expectation that all GCs should always copy objects in the same way and 
lay out objects graphs in the same order is very misguided, IMHO. 
Different GCs will behave differently (due to different allocation 
strategies, parallelism, PLABs, work stealing, array chunking, etc.). It 
might be possible to make the GCs behave a bit more similarly then they 
do now, but that's about it. :-)

Tony

On 9/4/13 10:00 PM, Igor Veresov wrote:
> Yup, that's a depth-first array-scanning quirk. The work-stealing is done using stacks, so in order to have the first fields followed first the references need to be put of stack in reverse. That's done for regular objects but for arrays it's not.
>
> igor
>
> On Sep 4, 2013, at 12:51 PM, Aleksey Shipilev <aleksey.shipilev at oracle.com> wrote:
>
>> Hi Jon,
>>
>> On 09/04/2013 10:19 PM, Jon Masamitsu wrote:
>>> I haven't followed this thread carefully enough but the ParallelGC
>>> collector uses a depth-first traversal while the other collectors use
>>> a breadth-first. Would that explain the difference?
>> The referenced objects in the array are the leaves in reachability
>> graph. I thought there is no difference in depth- vs. breadth-first in
>> this case? It looks more like we record the traversed objects on some
>> LIFO structure, which polls the elements in the reverse order.
>>
>> -Aleksey.
>>
>>

-- 
Tony Printezis | Staff Software Engineer | Twitter

@TonyPrintezis
tprintezis at twitter.com