timsort

[Christopher Hegarty -Sun Microsystems Ireland]

comments inline...

Martin Buchholz wrote:
> [+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 
> <mailto: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.
OK great. But just to clarify, what exactly does "if the natural order 
of the array elements is found to violate the Comparable contract" mean?

> 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
Yes, I only noticed that after sending the mail.

> 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.
Once I understand the impact of the spec change then I hope the 
fasttrack the CCC request.

-Chris.
> 
> 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
>         <mailto: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.
> 
>