timsort

[Christopher Hegarty -Sun Microsystems Ireland]

Hi Martin,

Sorry for joining the party late...

I think adding the system property should take care of the compatibility 
issues, at least giving the user the ability to revert to the old 
behavior if they so choose.

I have a few minor comments ( if these issue have been discussed already 
I apologize ):

1) Should we update the Arrays class description and appropriate sort
    methods to now refer to timsort instead of saying: "The sorting
    algorithm is a modified mergesort...". I know this is not strictly
    necessary, but you must have considered it already, right?
2) With the addition of @throws IllegalArgumentException, this
    condition cannot be met with the old merge sort right, i.e. running
    with -Djava.util.Arrays.useLegacyMergeSort=true. So we're saying
    that all bets are off when running with this property set?
3) Have I missed something obvious! Can the test run, or even compile?
    Sorter.java, L29:
      ComparableTimSort.sort(array);

BTW, if you agree, I think we should stick with the process as is today 
for making spec changes. Once agreed, I can submit a CCC request for 
this change and help with the communication to get it approved.

-Chris.




Martin Buchholz wrote:
> No one actually said NO, but both Alan and Andrew strongly hinted that
> a backward compatibility mode would be good.
> So I kept the old implementation and allow it to be selectable
> via a system property.  There's nothing more compatible than
> the legacy implementation.
> 
>     /**
>      * Old merge sort implementation can be selected (for
>      * compatibility with broken comparators) using a system property.
>      * Cannot be a static boolean in the enclosing class due to
>      * circular dependencies.  To be removed in a future release.
>      */
>     static final class LegacyMergeSort {
>         private static final boolean userRequested =
>             java.security.AccessController.doPrivileged(
>                 new sun.security.action.GetBooleanAction(
>                     "java.util.Arrays.useLegacyMergeSort")).booleanValue();
>     }
> 
> The sort method bodies now look like:
> 
>         if (LegacyMergeSort.userRequested)
>             legacyMergeSort(a);
>         else
>             ComparableTimSort.sort(a);
> 
> New webrev at:
> http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/
> 
> If I don't hear from anyone soon (e.g. for CCC approval)
> I'll commit to the tl forest.
> 
> Martin
> 
> On Tue, Jun 30, 2009 at 11:28, Alan Bateman<Alan.Bateman at sun.com> wrote:
>> Martin Buchholz wrote:
>>> :
>>>
>>> As you suggested, I added the Classpath exception wording
>>> to TimSort.java and ComparableTimSort.java.
>>>
>>> I excised the old mergesort code from Arrays.java.
>>>
>>> webrev regenerated.
>> Thanks for doing this.
>>> Adding all-or-nothing wording would be good to add,
>>> perhaps to the class-level javadoc.  But it doesn't
>>> have to be part of this change.
>> I brought it up because it looks like (and you can correct me) that the IAE
>> may be thrown after some reordering of the array has taken place. This might
>> be unexpected.
>>
>>> The JDK project has unusually high compatibility concerns.
>>> I and Josh believe the introduction of a possible IAE if the
>>> comparator doesn't satisfy its contract is the right thing,
>>> but we'd also be willing to change the code to swallow the IAE
>>> or to do so conditionally based on the value of a system property.
>>> Keep in mind that a call to foreign code can throw any throwable at all,
>>> so a rogue comparator can cause arbitrary behavior even today.
>> I think most people would agree that that catching these otherwise-silent
>> failures is a good thing. The problem is the customer that upgrades the JDK
>> on a production system and gets burnt by some broken third party code that
>> "used" to work. Having some way to restore existing behavior would make this
>> an easier sell. The suggestion from Jason to change it to an assertion might
>> be worth thinking about too but I suspect that few developers test with
>> assertions enabled.
>>
>> -Alan.
>>