RFR: 8247755: Leaner and more versatile GrowableArray classes

[coleen.phillimore at oracle.com]

http://cr.openjdk.java.net/~stefank/8247755/webrev.01/src/hotspot/share/utilities/growableArray.cpp.html

   92 #endif

nit, can you add // ASSERT here


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?  Can template parameter 'S' be "ALLOC" so it's easy 
to find?

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

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.

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