timsort

[Martin Buchholz]

[+jjb]  (Please keep Josh in this thread - he is the primary author)


On Tue, Jul 7, 2009 at 02:51, Christopher Hegarty -Sun Microsystems Ireland
<Christopher.Hegarty at sun.com> wrote:

> 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?


Josh?


>
> 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?


No.  Please re-read the @throws IllegalArgumentException.
It is carefully worded to make no promises at all.  All bets are off -
period.
No JCK tests can be written or are invalidated.


>
> 3) Have I missed something obvious! Can the test run, or even compile?
>   Sorter.java, L29:
>     ComparableTimSort.sort(array);
>

These are not tests.
Please see:
http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/test/java/util/TimSort/README

One could rework the benchmarks to work with the newly introduced
system property (using reflection to invoke appropriate methods)
but I have no plans to do that.


>
> 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.
>

OK.  Keep in mind that the spec changes are almost no-ops.

Martin


>
> -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/<http://cr.openjdk.java.net/%7Emartin/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.
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090707/61812be7/attachment.html>