RFR: 8325679: Optimize ArrayList subList sort

[Stuart Marks]

On Mon, 12 Feb 2024 23:37:59 GMT, Jim Laskey <jlaskey at openjdk.org> wrote:

>> Somewhat surprisingly, `ArrayList$Sublist.sort()` is not specialized and will thus fall back to slower default method of `List.sort()` instead of sorting a range of the array in-place in its backing root `ArrayList`. 
>> 
>> This doesn't change observable behavior, so haven't added tests, and `tier1` tests still all pass except for `test/jdk/java/util/Locale/LocaleProvidersFormat.java` which also currently fails on master too on the machine I tested on.
>
> Been there since day one?

Just to clarify, my comments about "sorting sublists is rare" is a response to "has this been there since day one?" from @JimLaskey, and it's not an argument against adding this. Maybe it's a bit surprising that it hasn't been done, but maybe not, as the case is somewhat rare. (There are a lot of cases in the collections where various collection views inherit slow implementations from default methods or from the Abstract implementations, because nobody has really cared enough to provide optimized implementations, and it would add bulk to the code.)

CopyOnWriteArrayList needs to override subList.sort since it potentially modifies the array, and COWAL needs to make a copy before making any modifications.

Regarding testing: the tests in `test/jdk/java/util/concurrent/tck` are supposed to be the conformance tests for the java.util.concurrent package, so it'd be somewhat odd to have functional tests for non-juc classes added there. (I did find it surprising that there are ArrayList tests there, but a lot of work in the core collections was done in the context of JSR166, so maybe I shouldn't be too surprised.)

There appears to be some coverage of the List.sort() default method in `test/jdk/java/util/List/ListDefault.java'. It does seem to cover sublists. I guess the question is whether this test is focused on the _default implementation_ of List.sort(), or whether it's intended to cover all implementations -- whether the default or overridden -- of the default methods that were added in JDK 8. I think this area is worth a closer look. If the new ArrayList.subList().sort() override is covered already, we might be able to get away without adding a new test. Or possibly some adjustment could be made to this test if necessary.

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

PR Comment: https://git.openjdk.org/jdk/pull/17818#issuecomment-1944635901