RFR: 8319115: GrowableArray: Do not initialize up to capacity

[Kim Barrett]

On Fri, 1 Dec 2023 07:56:04 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

> Before this patch, we always initialized the GrowableArray up to its `capacity`, and not just up to `length`. This is problematic for a few reasons:
> 
> - It is not expected. `std::vector` also only initializes the elements up to its size, and not to capacity.
> - It requires a default-constructor for the element type. And the default-constructor is then used to fill in the elements between length and capacity. If the elements do any allocation themselves, then this is a waste of resources.
> - The implementation also required the copy-assignment-operator for the element type. This is a lesser restriction. But the copy-assignment-operator was used in cases like `append` (where placement copy-construct would be expected), and not just in true assignment kinds of cases like `at_put`.
> 
> For this reason, I reworked a lot of the methods to ensure that only the "slots" up to `length` are ever initialized, and the space between `length` and `capacity` is always garbage.
> 
> -----
> 
> Also, before this patch, one can CHeap allocate both with `GrowableArray` and `GrowableArrayCHeap`. This is unnecessary. It required more complex verification in `GrowableArray` to deal with all cases. And `GrowableArrayCHeap` is already explicitly a smaller object, and should hence be preferred. Hence I changed all CHeap allocating cases of `GrowableArray` to `GrowableArrayCHeap`. This also allows for a clear separation:
> - `GrowableArray` only deals with arena / resource area allocation. These are arrays that are regularly abandoned at the end of their use, rather than deleted or even cleared.
> - `GrowableArrayCHeap` only deals with CHeap allocated memory. We expect that the destructor for it is called eventually, either when it goes out of scope or when `delete` is explicitly called. We expect that the elements could be allocating resources internally, and hence rely on the destructors for the elements being called, which may free up those internally allocated resources.
> 
> Therefore, we now only allow `GrowableArrayCHeap` to have element types with non-trivial destructors, but `GrowableArray` checks that element types do not have non-trivial destructors (since it is common practice to just abandon arena / resource area allocated arrays, rather than calling the destructor or clearing the array, which also destructs all elements). This more clearly separates the two worlds: clean-up your own mess (CHeap) vs abandon your mess (arena / resource area).
> 
> -----
> 
> I also completely refactored and improved ...

That's it for today.  I'll continue looking at this tomorrow.

src/hotspot/share/utilities/bitMap.hpp line 191:

> 189:     verify_size(size_in_bits);
> 190:   }
> 191:   ~BitMap() {}

This change is incorrect.  This destructor is intentionally declared protected, to prevent slicing
through it.  It would be reasonable to change it to have a `= default` definition though, rather
than the empty body definition it currently has.

Note that BitMap copying has the same shallow-copying problems as GrowableArray.

src/hotspot/share/utilities/growableArray.hpp line 87:

> 85:   }
> 86: 
> 87:   ~GrowableArrayBase() {}

Another incorrect removal of an intentionally protected destructor.

src/hotspot/share/utilities/growableArray.hpp line 124:

> 122:       GrowableArrayBase(capacity, initial_len), _data(data) {}
> 123: 
> 124:   ~GrowableArrayView() {}

Another incorrect removal of an intentionally protected destructor.

src/hotspot/share/utilities/growableArray.hpp line 294:

> 292:   void remove_range(int start, int end) {
> 293:     assert(0 <= start, "illegal start index %d", start);
> 294:     assert(start < end && end <= _len, "erase called with invalid range (%d, %d) for length %d", start, end, _len);

pre-existing: I think start == end should be permitted.  There's no reason to forbid an empty range,
and there are algorithms that are simpler if empty ranges are permitted.

src/hotspot/share/utilities/growableArray.hpp line 319:

> 317:     ::new ((void*)&this->_data[index]) E(_data[_len]);
> 318:     // Destruct last element
> 319:     this->_data[_len].~E();

Must not do the copy/destruct if index designated the last element.

src/hotspot/share/utilities/growableArray.hpp line 327:

> 325:   // sort by fixed-stride sub arrays:
> 326:   void sort(int f(E*, E*), int stride) {
> 327:     qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);

pre-existing: Use of qsort presumes E is trivially copyable/assignable.  Use QuickSort::sort instead.

src/hotspot/share/utilities/growableArray.hpp line 398:

> 396:   }
> 397: 
> 398:   ~GrowableArrayWithAllocator() {}

Another incorrect removal of an intentionally protected destructor.

src/hotspot/share/utilities/growableArray.hpp line 414:

> 412:     // Assignment would be wrong, as it assumes the destination
> 413:     // was already initialized.
> 414:     ::new ((void*)&this->_data[idx]) E(elem);

I don't think the cast to void* is needed, and just adds clutter.  There are many more of these.

-------------

Changes requested by kbarrett (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/16918#pullrequestreview-1787825840
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430721171
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430728218
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430728372
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430760537
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430759359
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430762966
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430734644
PR Review Comment: https://git.openjdk.org/jdk/pull/16918#discussion_r1430747894