timsort

[Andrew John Hughes]

2009/6/30 Martin Buchholz <martinrb at google.com>:
> 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.
>

Given that this is a new release (JDK7), I'd strongly agree that
introducing such a change is both timely and appropriate.  Users
should expect some minor changes/incompatibilities with a completely
new major release, especially when we are talking about something that
has been enforced verbally (in the Javadocs) beforehand.  The only
change here is that this is enforced at a technical level and may
actually catch some errors ahead of time that would otherwise result
in strange behaviour.  I'm sure all of us want to limit the number of
hacks to preserve legacy code wherever possible.

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

OpenJDK is (or at least should now be) a community-driven open source
project.  And so, the community as a whole should be making such
decisions, not just those who happen to be employed by Sun.

> Martin
>
> On Tue, Jun 30, 2009 at 03:04, Alan Bateman <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/>
>>>
>>> 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. When you say "also content leaving
>> out", do you mean just the spec update, or do you mean that the exception
>> won't be thrown if detected? I wonder if this will need a compatibility
>> switch so as not to change the failure mode of existing (broken)
>> applications.  Also, I assume failure atomicity is not possible here
>> (right?); just wondering if this needs to be stated in the javadoc for this
>> exception.
>>
>> I haven't studied the code but from a brief glance, I think the
>> "Classpath" exception might be missing from the new files in
>> src/share/classes/java/util. Also, should the mergeSort implementation be
>> removed or moved out of Arrays?
>>
>> -Alan.
>>
>
>



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