RFR: 8325679: Optimize ArrayList subList sort
Attila Szegedi
attila at openjdk.org
Thu Apr 11 07:54:44 UTC 2024
On Wed, 14 Feb 2024 23:37:03 GMT, Stuart Marks <smarks 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.
>
> (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.
Hey folks (@stuart-marks or @JimLaskey) it's been a while – can I get a review?
-------------
PR Comment: https://git.openjdk.org/jdk/pull/17818#issuecomment-2049131137
More information about the core-libs-dev
mailing list