timsort

[Andrew John Hughes]

2009/7/7 Christopher Hegarty -Sun Microsystems Ireland
<Christopher.Hegarty at sun.com>:
> 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.
>>>
>

Forgive the naivety, but what is a 'CCC request'?  Is this process of
requesting and approving specification changes public?  I'm sure I'm
not alone among those contributing to the JDK only since its inception
as OpenJDK and thus unaware of such procedures, so some explanation
would be helpful.

Thanks,
-- 
Andrew :-)

Free Java Software Engineer
Red Hat, Inc. (http://www.redhat.com)

Support Free Java!
Contribute to GNU Classpath and the OpenJDK
http://www.gnu.org/software/classpath
http://openjdk.java.net

PGP Key: 94EFD9D8 (http://subkeys.pgp.net)
Fingerprint: F8EF F1EA 401E 2E60 15FA  7927 142C 2591 94EF D9D8