timsort

[Andrew John Hughes]

2009/6/30 Andrew Haley <aph at redhat.com>:
> Martin Buchholz wrote:
>> Thanks, Alan.  You're a good reviewer.
>>
>> 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.
>>
>> 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.
>>
>> 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.
>> It's up to Sun/CCC.
>>
>> (There is the deeper governance issue of who gets to make
>> such decisions.  I would like most of such decisions to be made
>> by the "group" of engineers who do the work.  For collections/concurrency,
>> such a group has worked informally for many years.)
>>
>> Martin
>>
>> On Tue, Jun 30, 2009 at 03:04, Alan Bateman <Alan.Bateman at sun.com
>> <mailto:Alan.Bateman at sun.com>> wrote:
>>
>>     Martin Buchholz wrote:
>>
>>         Hi sort team!
>>
>>         Google would like to contribute a new implementation for sorting
>>         of Object arrays,
>>         which has much better performance for input that is already
>>         partially sorted,
>>         based on Tim Peter's sort used in Python.
>>
>>         This sort is already being used in the java.util. that comes
>>         with Android.
>>
>>         Written by Josh Bloch.
>>
>>         http://cr.openjdk.java.net/~martin/timsort/
>>         <http://cr.openjdk.java.net/%7Emartin/timsort/>
>>         <http://cr.openjdk.java.net/%7Emartin/timsort/>
>>
>>
>>         Strictly speaking, no further review may be necessary,
>>         since it has already seen much review by Google engineers,
>>         (including some who are OpenJDK committers),
>>         and it has seen real-world usage.
>>
>>         Nevertheless, interested parties are invited to further review it.
>>
>>         The proposed webrev includes some very minor change to
>>         the javadoc for Arrays.sort, that we would like to include,
>>         but are also content leaving out, or to have a Sun engineer
>>         shepherd through CCC (perhaps Chris or Alan?).
>>
>>     The results look very good.
>>
>>     I assume the only contentious issue is going to be the IAE when a
>>     broken implementation of Comparable is detected.
>
> We had a similar problem with GNU Classpath.  Our binary search compared
> the elements in a different order from that in Sun's library, and this
> caused many problems.  My attitude was "well, you program is broken",
> but in the end we had to fix Classpath anyway.
>

Sigh...  I can remember all too many such cases.  At least with
OpenJDK we have more leverage now to set the playing field, rather
than always being the ones trying to catch up.

> Andrew.
>
>
> Index: Arrays.java
> ===================================================================
> --- Arrays.java (revision 121090)
> +++ Arrays.java (revision 121091)
> @@ -1,5 +1,5 @@
>  /* Arrays.java -- Utility class with methods to operate on arrays
> -   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
> +   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
>    Free Software Foundation, Inc.
>
>  This file is part of GNU Classpath.
> @@ -370,10 +370,13 @@
>     while (low <= hi)
>       {
>         mid = (low + hi) >>> 1;
> -        final int d = Collections.compare(key, a[mid], c);
> +       // NOTE: Please keep the order of a[mid] and key.  Although
> +       // not required by the specs, the RI has it in this order as
> +       // well, and real programs (erroneously) depend on it.
> +        final int d = Collections.compare(a[mid], key, c);
>         if (d == 0)
>           return mid;
> -        else if (d < 0)
> +        else if (d > 0)
>           hi = mid - 1;
>         else
>           // This gets the insertion point right on the last loop
>
> Andrew.
>



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