RFR: 8247755: Leaner and more versatile GrowableArray classes

[Stefan Karlsson]

Hi Coleen,

On 2020-06-18 21:39, coleen.phillimore at oracle.com wrote:
>
> http://cr.openjdk.java.net/~stefank/8247755/webrev.01/src/hotspot/share/utilities/growableArray.cpp.html 
>
>
>   92 #endif
>
> nit, can you add // ASSERT here

Sure.

>
>
>
> http://cr.openjdk.java.net/~stefank/8247755/webrev.01/src/hotspot/share/utilities/growableArray.hpp.html 
>
>
> 302 template <typename E, typename S>
>  303 class GrowableArrayWithAllocator : public GrowableArrayView<E> {
>
>
> So all the functions in this class need to be able to call grow(), 
> with allocator 'S' right?

Yes.

>   Can template parameter 'S' be "ALLOC" so it's easy to find?

I chose the name S to match that the class that S represents *must* be a 
subclass. I can rename it to ALLOC, but then the name would loose that 
connection. I'd like to here more opinions before changing this.

>
> The early tiers run the SA tests so I think if it's not broken your SA 
> changes are sufficient.

OK. I'll make sure that they pass.

>
>
> Second webrev.
>
> http://cr.openjdk.java.net/~stefank/8247759/webrev.01/src/hotspot/share/gc/z/zArray.hpp.udiff.html 
>
>
> I looked at the diffs and they seemed fine (don't know the code). This 
> is a nice result of this rewrite.

Yes. At least I think so. This was the code that made me start 
investigating this:
https://cr.openjdk.java.net/~stefank/8247759/webrev.01/src/hotspot/share/gc/z/zPhysicalMemory.cpp.udiff.html

Thanks for looking at the code,
StefanK
>
> Coleen
>
> On 6/17/20 10:16 AM, Stefan Karlsson wrote:
>> Hi all,
>>
>> Please review and/or comment on this patch to create leaner and more 
>> versatile GrowableArray classes.
>>
>> https://cr.openjdk.java.net/~stefank/8247755/webrev.01
>> https://bugs.openjdk.java.net/browse/JDK-8247755
>>
>> This is a proposal to rewrite the GrowableArray classes, with two 
>> main goals:
>>
>> 1) Allow a GrowableArray instance to be allocated on the stack or 
>> embedded in other objects. This removes one of the two indirections 
>> when operating on the array elements.
>>
>> 2) Make the GrowableArray instances smaller, so that there's no extra 
>> overhead when they are embedded in other objects.
>>
>> This will enable us to use GrowableArray effectively in ZGC, without 
>> having to rely on our own implementations. See follow-up patch:
>> https://cr.openjdk.java.net/~stefank/8247759/webrev.01
>>
>> Some background about the GrowableArray:
>>
>> GrowableArray is split into two memory parts. One for the instance of 
>> the GrowableArray, and a second, separate memory part for the 
>> elements. This memory can come from these places:
>>
>> a) Resource area in the thread
>> b) CHeap (malloc)
>> c) Arena (malloced arena)
>> d) Stack
>> e) Embedded in other object
>>
>> From the C++ compiler's point-of-view, (a)-(e) can be used to 
>> allocate the GrowableArray, and (a)-(c) can be used to allocate the 
>> elements. However, there are runtime asserts that restricts the 
>> combinations.
>>
>> One of the restrictions is that if either of the GrowableArray 
>> instance memory, or the elements memory, comes from the CHeap, then 
>> the other must also come from the CHeap.
>>
>> I've found two reasons why we want to be restrictive with our CHeap 
>> allocated elements:
>>
>> - if the GrowableArray instance is allocated in (a) or (c), then the 
>> destructor will never run and we get a memory leak because the 
>> elements are not deallocated.
>>
>> However, for stack allocated instances the destructor will be run, 
>> and the memory will be handed back. For embedded instances it all 
>> depends on how the parent instance was allocated.
>>
>> - There's no proper support for copying/moving of the elements, just 
>> a simple pointer copy. So, if a copy would be done, the source 
>> GrowableArray would still have a pointer to the elements, and if the 
>> source were destructed (maybe because it was stack allocated and went 
>> out-of-scope) then the memory of the destination GrowableArray will 
>> be deallocated. This isn't a problem with instances in (a) or (c), 
>> since their destructors won't be run.
>>
>> Proposal for Goal 1:
>>
>> - Allow stack allocated and embedded GrowableArrays to have CHeap 
>> allocated elements.
>> - Add an assert in a copy constructor and assignment operator that 
>> checks that the GrowableArray elements are not CHeap allocated.
>>
>> The rest of the patch mainly deals with Goal 2:
>>
>> The current fields of GrowableArrays, in product builds, are:
>>    int _len;
>>    int _max;
>>    Arena* _arena;
>>    MEMFLAGS _memflags;
>>    E* _data;
>>
>> and the resulting is 32 bytes: 4 + 4 + 8 + 8 + 8. The _memflags size 
>> is due to alignment requirements for the _data field.
>>
>> - By combining _arena and _memflags, this is reduced to 24 bytes.
>> - By having a specialized CHeap version with the MEMFLAGS encoded as 
>> a template parameter, we can get rid of both _memflags and _arena 
>> fields, and reduce this to 16 bytes.
>>
>> Things to note about the patch:
>>
>> - GrowableArrayMetadata: I've fused _arena and _memflags into one 
>> uintptr_t field, and encapsulated all bookkeeping about where and how 
>> the memory is allocated for the GrowableArray. The hope is to 
>> simplify the code a bit, and also to move some of the checking out 
>> into a non-template class, so that the code can be put in the .cpp file.
>>
>> - GrowableArrayNestingCheck: Simplify and encapsulate resource area 
>> nesting checks.
>>
>> - I'm using CRTP because I don't want a vtable in the class. This 
>> means that the super class can cast to derived type, responsible for 
>> allocation and deallocation:
>>
>> template <typename E> class GrowableArray : public 
>> GrowableArrayWithAllocator<E, GrowableArray<E> >
>>
>> and then:
>>
>> void GrowableArrayWithAllocator<E, S>::grow(int j) {
>> ...
>>   E* newData = static_cast<S*>(this)->allocate();
>>
>> - Since I'm chainging so much of the structure of the code, I've also 
>> made some stylistic changes to make the code more consistent.
>>
>> - Moved the CompareClosure to iterator.hpp, where many of our other 
>> closures are located.
>>
>> - Moved _sort_Fn, since it was already used by non-GrowableArray code
>>
>> - I've added a GrowableArrayCHeap class to be able to mostly 
>> side-step the complication of the GrowableArray elements allocation, 
>> and to minimize the instance size.
>>
>> - The metaspaceShared.cpp was used to show how GrowableArrayCHeap can 
>> be used. It's not strictly necessary, and could be reverted.
>>
>> -  The arguments.cpp change shows a usage of GrowableArrayView as a 
>> way to only expose an interface that don't allow the array to be grown.
>>
>> - The arguments.cpp change also shows stack allocated 
>> GrowableArrayCHeap, that automatically gets deallocated when the 
>> function returns, and the cleanups we can do because of this.
>>
>> - The hashtable.* changes show an embedded GrowableArrayCHeap.
>>
>> - The SA agent. I didn't bother renaming the GenericGrowableArray 
>> file. I can do that upon request.
>>
>> - I added gtest for GrowableArray. There was not a single unit test 
>> of GrowableArray before. The creates all possible memory allocation 
>> combinations and run limited set of sanity checks. It also checks 
>> that the different memory allocation combinations return the correct 
>> allocation types when queried. I've added negative tests to show that 
>> GrowableArrays with CHeap allocated elements assert when being copied.
>>
>> Testing: will run at least tier1-3, but most likely more tiers on 
>> Linux x64. Suggestions on what to test welcome.
>>
>> Thanks,
>> StefanK
>