aph at redhat.com
Tue Jun 30 09:25:47 PDT 2009
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.)
> 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.
> 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.
--- 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)
- else if (d < 0)
+ else if (d > 0)
hi = mid - 1;
// This gets the insertion point right on the last loop
More information about the core-libs-dev