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 the tests for `GrowableArray(CHeap)`: https://github.com/openjdk/jdk/blob/e5eb36010355b444a719da6bdcd8c5de3145b961/test/hotspot/gtest/utilities/test_growableArray.cpp#L29-L60 The main improvement is that now **all** `GrowableArray` methods are tested, and that we test it with many different element types (including such without default-constructor or copy-assign-constructor). And we also check that the number of live elements is correct, which we can compute as `live = constructred - destructed`. This is especially valuable because I refactored the use of constructors/destructors heavily, to do the change from initializing up to `length` instead of `capacity`. ---- **Note on move-semantics** Since move semantics is currently not allowed by the style guide, we have to "simulate" a move by placement new with copy-constructor, and then destruct the old element. See this example when we need to grow an array, and move the elements from the old data to the new data: https://github.com/openjdk/jdk/blob/e5eb36010355b444a719da6bdcd8c5de3145b961/src/hotspot/share/utilities/growableArray.hpp#L530-L563 Of course this is nothing new with my change here. I just want to record that we are doing it this way, and in fact have to do so without any move-semantics. The problem with this: If you use nested `GrowableArray<GrowableArray<E>>`, then the inner arrays get copy-constructed around when we re-allocate the outer array. We now have two choices for how `GrowableArray` could copy (currently it is a shallow-copy): - shallow-copy: works well for reallocating outer arrays, since the inner array is now just shallow-copied to the new data, and the destructor for the old inner arrays does nothing. Shallow-copy of course would not work for `GrowableArrayCHeap`, since it would deallocate the data of the old inner arrays, and the new inner array would still have a pointer to that deallocated data (bad!). But shallow-copy is generally dangerous, since the copy-constructor may be used in non-obvious cases: ResourceMark rm; GrowableArray<GrowableArray<int>> outer; outer.at_grow(100); // default argument calls default constructor, and (shallow) copy-constructs it so all elements outer.at(0).at_put_grow(0, 42); outer.at(1).at_put_grow(0, 666); // inner array at position 1 has reference to same data as inner array 0 ASSERT_EQ(outer.at(0).at(0), 42); // fails, we see 666 instead of 42 ASSERT_EQ(outer.at(1).at(0), 666); - deep-copy: This ensures correctness, we never have two arrays with the same underlying data. But that also means that when we re-allocate an outer array, we now (deep) copy-construct all new elements from the old elements. And that seems quite wasteful, both for the memory and the time needed to deep-copy everything over. Neither of these options is good. This is exactly why the move-semantics were introduced in `C++11`. We should therefore discuss the introduction of move-semantics, and weigh it against the additional complexity that it introduces. ----- Testing: tier1-3 and stress testing. Running. ------------- Commit messages: - whitespaces - fix issue with clang, need explicit copy constructor if assignment operator deleted - Merge branch 'master' into JDK-8319115 - fix small comment - fix some comments - test shallow assign / copy - 2 negative tests: nested ra, insert_before to itself - refactor and test swap - find_sorted and insert_sorted - test 2 versions of sort - ... and 44 more: https://git.openjdk.org/jdk/compare/b31454e3...1ed037fd Changes: https://git.openjdk.org/jdk/pull/16918/files Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=16918&range=00 Issue: https://bugs.openjdk.org/browse/JDK-8319115 Stats: 3439 lines in 127 files changed: 2150 ins; 493 del; 796 mod Patch: https://git.openjdk.org/jdk/pull/16918.diff Fetch: git fetch https://git.openjdk.org/jdk.git pull/16918/head:pull/16918 PR: https://git.openjdk.org/jdk/pull/16918
