RFR 7065380 : Allow Collections.sort to sort Collections.singletonList() result
Hello all; Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted. This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted. WEBREV: http://cr.openjdk.java.net/~mduigou/7065380/0/webrev/ For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy". Thanks, Mike
Looks good to me. A superfluous comment in the test: 47 // 7065380 David On 2/03/2012 5:50 AM, Mike Duigou wrote:
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
WEBREV: http://cr.openjdk.java.net/~mduigou/7065380/0/webrev/
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
On 03/01/2012 08:50 PM, Mike Duigou wrote:
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
WEBREV: http://cr.openjdk.java.net/~mduigou/7065380/0/webrev/
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
Is it not better to check list.size() before calling toArray() ? Rémi
I thought so too initially but that's optimizing for empty or singleton collections which probably are an edge case? Adding a branch, polymorphic method call, and increasing bytecode size may not be worth it. Sent from my phone On Mar 1, 2012 3:25 PM, "Rémi Forax" <forax@univ-mlv.fr> wrote:
On 03/01/2012 08:50 PM, Mike Duigou wrote:
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
Is it not better to check list.size() before calling toArray() ?
Rémi
Also some collections may not have an O(1) size(). Sent from my phone On Mar 1, 2012 3:52 PM, "Vitaly Davidovich" <vitalyd@gmail.com> wrote:
I thought so too initially but that's optimizing for empty or singleton collections which probably are an edge case? Adding a branch, polymorphic method call, and increasing bytecode size may not be worth it.
Sent from my phone On Mar 1, 2012 3:25 PM, "Rémi Forax" <forax@univ-mlv.fr> wrote:
On 03/01/2012 08:50 PM, Mike Duigou wrote:
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
Is it not better to check list.size() before calling toArray() ?
Rémi
On 03/01/2012 09:52 PM, Vitaly Davidovich wrote:
I thought so too initially but that's optimizing for empty or singleton collections which probably are an edge case? Adding a branch, polymorphic method call, and increasing bytecode size may not be worth it.
toArray is also polymorphic, so the typecheck will be done once :) On 03/01/2012 09:56 PM, Vitaly Davidovich wrote:
Also some collections may not have an O(1) size().
Sent from my phone
Yes, you're right. I see now. Rémi
Sent from my phone
On Mar 1, 2012 3:25 PM, "Rémi Forax" <forax@univ-mlv.fr <mailto:forax@univ-mlv.fr>> wrote:
On 03/01/2012 08:50 PM, Mike Duigou wrote:
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
WEBREV: http://cr.openjdk.java.net/~mduigou/7065380/0/webrev/ <http://cr.openjdk.java.net/%7Emduigou/7065380/0/webrev/>
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
Is it not better to check list.size() before calling toArray() ?
Rémi
I thought about that but the usual issue of non-O(1) size() methods lead me to avoid having a size() in addition to the toArray(). Not perfect. :( Mike On Mar 1 2012, at 12:26 , Rémi Forax wrote:
On 03/01/2012 08:50 PM, Mike Duigou wrote:
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
WEBREV: http://cr.openjdk.java.net/~mduigou/7065380/0/webrev/
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
Is it not better to check list.size() before calling toArray() ?
Rémi
What about exception cases where the single element is not comparable? http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045147 Consider the following: ========= Object[] a = new Object[]{new Object()}; Arrays.sort(a); List l = Arrays.asList(a); //Evil raw type Collections.sort(l); ======== On JDK1.6u31, Arrays.sort passes but, Collections.sort fails with a class cast. Per the method contracts, both Arrays.sort and Collections.sort should fail in non-comparable single element case. So for this patch, the length check be performed to prevent the element swap that causes the unsupported operation exception but not prevent the call to Arrays.sort. That way both methods always have the same type checking behavior. Jason
From: mike.duigou@oracle.com Subject: RFR 7065380 : Allow Collections.sort to sort Collections.singletonList() result Date: Thu, 1 Mar 2012 11:50:49 -0800 To: core-libs-dev@openjdk.java.net
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
WEBREV: http://cr.openjdk.java.net/~mduigou/7065380/0/webrev/
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
On Mar 1 2012, at 13:35 , Jason Mehrens wrote:
What about exception cases where the single element is not comparable? http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045147
Consider the following:
========= Object[] a = new Object[]{new Object()}; Arrays.sort(a); List l = Arrays.asList(a); //Evil raw type Collections.sort(l); ========
On JDK1.6u31, Arrays.sort passes but, Collections.sort fails with a class cast.
Per the method contracts, both Arrays.sort and Collections.sort should fail in non-comparable single element case.
Correct. This would require extra checks. If we do add these checks would it be reasonable to add them as assertions to reduce "but you made it slower" calls? I'm not really confident about proposing "assertions as lint detection" rather than adding explicit checks. We wouldn't (and don't) use optional assertions for array bounds checking. This has clearly been the right choice. I'm still considering my feelings about whether to be hardline and suggest we add the checks to Arrays.sort Thoughts anyone?
So for this patch, the length check be performed to prevent the element swap that causes the unsupported operation exception but not prevent the call to Arrays.sort. That way both methods always have the same type checking behavior.
Yes, this patch would result in the above working for both the Arrays.sort and Collections.sort cases, but as you point out, in technical breach of the contract of both. Mike
Jason
From: mike.duigou@oracle.com Subject: RFR 7065380 : Allow Collections.sort to sort Collections.singletonList() result Date: Thu, 1 Mar 2012 11:50:49 -0800 To: core-libs-dev@openjdk.java.net
Hello all;
Currently Collections.sort() refuses to sort the lists which result from calling Collections.singletonList(). This makes some sense because the singleton lists are immutable but they are also alway sorted.
This patch allows Collections.sort() to be used with empty and singleton lists of all types. A short circuit return is provided for lists of length 0 and 1 as they are already sorted.
WEBREV: http://cr.openjdk.java.net/~mduigou/7065380/0/webrev/
For the unit test ignore the diffs and view the "New" file--webrev doesn't understand "hg copy".
Thanks,
Mike
I'm not really confident about proposing "assertions as lint detection" rather than adding explicit checks. We wouldn't (and don't) use optional assertions for array bounds checking. This has clearly been the right choice. I'm still considering my >>feelings about whether to be hardline and suggest we add the checks to Arrays.sort
Thoughts anyone?
Add wiggle room to the throws CCE javadocs to suggest detection doesn't occur for all cases. Reading over the bug report again, the justification example is flawed. The caller only knows it is safe to call sort when the documentation for 'generate' states that the returned list is mutable. If the returned list is mutable, it is not a Collections$SingletonList. If 'generate' returns an unmodifiable list the call has to make a mutable copy. If the caller has to create a copy, the caller could perform the size check first. Close as Not a bug?? Jason
On 13/03/2012 5:08 AM, Jason Mehrens wrote:
I'm not really confident about proposing "assertions as lint detection" rather than adding explicit checks. We wouldn't (and don't) use optional assertions for array bounds checking. This has clearly been the right choice. I'm still considering my>>feelings about whether to be hardline and suggest we add the checks to Arrays.sort
Thoughts anyone?
Add wiggle room to the throws CCE javadocs to suggest detection doesn't occur for all cases.
Reading over the bug report again, the justification example is flawed. The caller only knows it is safe to call sort when the documentation for 'generate' states that the returned list is mutable. If the returned list is mutable, it is not a Collections$SingletonList. If 'generate' returns an unmodifiable list the call has to make a mutable copy. If the caller has to create a copy, the caller could perform the size check first.
Close as Not a bug??
Well it's not a bug it is a RFE. :) But I agree that the example is a little flawed in that generate() would not reasonably be able to generate mutable lists in some cases and immutable lists in others. I find the restriction on empty/singleton lists unnecessary, but not sure it is worth jumping through the spec hoops to change this. David
Jason
Well it's not a bug it is a RFE. :) But I agree that the example is a little flawed in that generate() would not reasonably be able to generate mutable lists in some cases and immutable lists in others. I find the restriction on empty/singleton lists unnecessary, but not sure it is worth jumping through the spec hoops to change this.
Agreed. If the core of this RFE is to allow just Collections.singletonList to work then one possible fix would be to relax SingletonList.set to be a no-op if the given element is the contained element (see CopyOnWriteList.set). That way there is no performance impact for everyone else calling sort. The spec for SingletonList would have to change which might be a deal breaker. If not, then this RFE is really about allowing sort to return normally for pre-sorted unmodifiable lists and Collections.singletonList fits that category. For this case, sort could prevent swaps of identical elements. But, that's a sort spec change and a lot of performance testing. Jason
participants (5)
-
David Holmes
-
Jason Mehrens
-
Mike Duigou
-
Rémi Forax
-
Vitaly Davidovich