RFR: 8360023: Add an insertion sort implementation to Hotspot [v3]

[Evgeny Astigeevich]

On Thu, 19 Jun 2025 15:47:51 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

> > These many years of the project, there have not been any needs for a stable sort.
> 
> Just do a `grep -rn ./src/hotspot -e "stable sort"` you can find:
> 
> https://github.com/openjdk/jdk/blob/c4fb00a7be51c7a05a29d3d57d787feb5c698ddf/src/hotspot/share/classfile/fieldLayoutBuilder.hpp#L106
> 

Ok. Do we need to rewrite this code to use a stable sort?

> > If you want the insertion sort, I'd recommend to have it in `GrowableArrayView`: `GrowableArrayView<>::insertion_sort()`.
> 
> We are programming in C++, I think it would be better to follow the C++ convention. The practical reason is that it prevents users not wanting to sort from having to include the sort functionality.

Yes, we use C++ but we use subset of it: https://github.com/openjdk/jdk/blob/master/doc/hotspot-style.md
IMO 10 LoC is always better than 50+ LoC.
We don't write library code which uses most of C++ features. If we can solve a problem with less code which looks like C code, let's use such a solution. We don't have a goal to use as many C++ features as possible, especially approaches used in STL. 

> 
> > In this case you will not have the issue with iterators names which is a big issue from my point of view.
> 
> Now we have `GrowableArrayIterator` and `GrowableArrayNonConstIterator`, what is the issue with them?

One issue is the pollution of the global namespace by the name which rarely be used. Another is that this is opposite to what C++ programmers are familiar with: iterator and const_iterator. It's already confusing: users of `GrowableArrayIterator` might expect it to be non-constant.
So instead of fixing this confusion by getting close to C++ standards, we are diverging more from them.

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

PR Comment: https://git.openjdk.org/jdk/pull/25895#issuecomment-2988632237