On Wed, 14 Feb 2024 23:37:03 GMT, Stuart Marks <sma...@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. > > (Discussion mainly of historical interest.) > > @pavelrappo Correct, historically, `Collections.sort` would fail to sort > `CopyOnWriteArrayList`. You have to go back to JDK 7 to see this. The sorting > approach used by `Collections.sort` (still present in the default > implementation of `List.sort`) gets an array using `toArray()`, sorts it, and > then copies the sorted elements back using `ListIterator.set`. Since > `CopyOnWriteArrayList` doesn't support modifications using `ListIterator`, it > fails with `UnsupportedOperationException`. The overrides of `List.sort` have > fixed this problem. > > COWAL still has some problems with other things that use similar techniques, > such as `Collections.shuffle`. That uses get/set to swap elements, which > COWAL does support, but it copies the array on each set() operation. This > results in N copies of the array being made for an N-element list. @stuart-marks > 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. That's absolutely understood :-) I was just trying to add some color by describing the use case I stumbled upon. > 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. I confirmed that the code in [ListDefaults.java:403](https://github.com/openjdk/jdk/blob/master/test/jdk/java/util/List/ListDefaults.java#L403) exercises `ArrayList$SubList.sort()`. In the meantime, I also added a more exhaustive stochastic test, although it might be an overkill. I'm inclined to remove it. ------------- PR Comment: https://git.openjdk.org/jdk/pull/17818#issuecomment-1951481144