Another "Comparison method violates its general contract!"

Question

I'm being asked to investigate a bug as part of my internship. A piece of code is throwing

java.lang.IllegalArgumentException: Comparison method violates its general contract!

A custom Comparator is comparing two custom classes by looking at long member variables of said custom class:

return v1 > v2 ? -1 : v1 < v2 ? 1 : 0;

The equals method for this custom class looks at a String member variable of this custom class. We're having a hell of a time reproducing the behavior. My knee-jerk reaction was to replace the return statement in the custom Comparator with return v2.compareTo(v1);, but my team is skeptical that this will address the problem. Can anyone offer any insight?

Arrays.sort(anArray, new Comparator<ACustomClass>() {
  @Override
  public int compare(ACustomClass o1, ACustomClass o2) {
    long v1 = o1.getALong();
    long v2 = o2.getALong();
    return v1 > v2 ? -1 : v1 < v2 ? 1 : 0;
  }});

You say you're having trouble reproducing this problem, but you also say that you know which piece of code is throwing the exception. Which is it? — Greg Hewgill, Aug 07 '13 at 23:32
Can't post anything more than I already have...think it would probably violate my NDA. I know the code that is throwing the Exception, but I don't the data/execution path that is causing the code to throw the Exception...hence, I'm having trouble reproducing it. — Dan Forbes, Aug 07 '13 at 23:34
Can you isolate the suspected part into SSCCE [http://sscce.org/] ? — PM 77-1, Aug 07 '13 at 23:37
The [Comparator documentation](http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html) has some notes about consistency with "equals". I'd say that if it's possible that the Comparator returns 0 when equals() returns false, or if the Comparator returns non-zero when equals() returns true, you could be getting yourself into trouble. — ajb, Aug 07 '13 at 23:37
Why don't you just use [`Long.compare()`](http://docs.oracle.com/javase/7/docs/api/java/lang/Long.html#compare(long,%20long)) here? — arshajii, Aug 07 '13 at 23:38
Follow-up to my previous comment: I took a quick look at the runtime sources, and the message is coming from either TimSort or ComparableTimSort. Those classes don't seem to call equals() directly, but they could be calling something else that does use equals(). But it would take a lot of work for me to delve into this further. — ajb, Aug 07 '13 at 23:44
Yes, you're right @ajb. We've done a ton of debugging, but haven't been able to hit that code either. — Dan Forbes, Aug 07 '13 at 23:50
@arshajii, that was the change that I suggested/implemented. As I said, though, my team is skeptical that will address the problem. — Dan Forbes, Aug 07 '13 at 23:54
I would like to see a stacktrace. `Arrays.sort()` doesn't throw that exception as far as I can see. — user207421, Aug 08 '13 at 01:13
`Arrays.sort(...)` calls `TimSort(...)`, which throws this Exception. — Dan Forbes, Aug 08 '13 at 01:29
We spent quite a bit of time on this w/ the debugger...lots of different test cases. Couldn't get the behavior to be reproduced. The stuff that's going on in TimSort isn't exactly straightforward... — Dan Forbes, Aug 08 '13 at 01:36
@DanForbes Not in the source code I have to hand: JDK 6 and OpenJDK 6. What's yours? — user207421, Aug 08 '13 at 01:46
The "Comparison method violates its general contract!" error has been introduced in Java 7, specifically its `Arrays.sort(Object[])` method (the one which uses TimSort). But it should only arise when the *natural order* is involved (not a custom `Comparator`). — Marko Topolnik, Aug 08 '13 at 10:53
Here's a workaround: set the `java.util.Arrays.useLegacyMergeSort` system property. Reference: [Java 7 Compatibility](http://www.oracle.com/technetwork/java/javase/compatibility-417013.html); search for "RFE: 6804124". — Marko Topolnik, Aug 08 '13 at 11:00
EJP, right - this is a JDK 7 issue. @MarkoTopolnik, I think both versions of TimSort can throw his Exception. We saw that workaround, but we're trying to figure out *why* it's happening. — Dan Forbes, Aug 08 '13 at 14:04
In that case, your Comparator *is* inconsistent with equals, isn't it? Each is checking a different field. — Marko Topolnik, Aug 08 '13 at 15:52
FYI, I took a closer look at the TimSort source, looking for any method call that might call some method in a different class that could possibly call equals() (which would be a subtle mistake if it did). But I didn't spot anything. So that really makes that line of thinking a lot less likely. If it's a concurrency issue, the idea I suggested before of adding an "insideSort" member to ACustomClass, but this time displaying a message in any methods that change the ALong member if insideSort is true, might help. Make insideSort `volatile`. — ajb, Aug 08 '13 at 15:56
possible duplicate of [When does TimSort complain about broken comparator?](http://stackoverflow.com/questions/24951257/when-does-timsort-complain-about-broken-comparator) — Raedwald, Jul 25 '14 at 09:34

Stephen C · Accepted Answer · 2013-08-08T01:41:11.297

6

I cannot see anything obviously wrong with the comparator as presented. (And I am sceptical about the proposed fixes: they "smell" of voodoo programming to me.)

But if the ACustomClass class's aLong attribute was mutable ... and it changed while you were sorting ... then this could cause the sort code to think that the comparator was violating the contract.

So ... check to see if this could be a concurrency issue, where one thread is mutating the objects in an array that another thread is trying to sort.

We spent quite a bit of time on this w/ the debugger...lots of different test cases. Couldn't get the behavior to be reproduced.

I would treat that as evidence that points to a concurrency issue ...

edited Aug 08 '13 at 01:41

answered Aug 08 '13 at 00:42

Stephen C

698,415
94
811
1,216

The exact "IllegalArgumentException: Comparison method violates its general contract!" arises only in Java 7 TimSort, when sorting according to the *natural order*. That specific message should never arise when using a `Comparator`. – Marko Topolnik Aug 08 '13 at 10:56
I don't think that's true, @MarkoTopolnik. – Dan Forbes Aug 08 '13 at 14:05
@StephenC - thank you for the insight. We ran some tests to see if this was, in fact, the case, and it looks like you are correct. – Dan Forbes Aug 13 '13 at 21:55
@MarkoTopolnik it will rear its ugly head everywhere; it shouldn't. The sort function should not assume that objects are immutable. The fact that this error throws in sort( T[], Comparator ) is a design flaw in the JDK. – bond Mar 20 '16 at 02:33
1

@bond - *"The sort function should not assume that objects are immutable."* - It has to! It is mathematically impossible to sort a collection of objects whose "ordering" relationships are changing while they are being sorted. It is NOT a design flaw in the JDK. It is a design flaw in the application that is trying to do this ... impossible thing. – Stephen C Mar 20 '16 at 02:43
@StephenC depends on what you are sorting and how it is used for. For an accurate sort you need immutable objects; for an "good enough" sort mutable objects can be used. Checking the contract should be the job of the Comparator and not the sort alg. If I want to write a sort using mutable objects the built-in sort alg should not penalize me. Its basically back to the "optimistic" concurrency vs locking concurrency debate. – bond Mar 20 '16 at 03:07
1

Well the Java API contract for the `sort` methods is not for "good enough" sorting. It is for precise sorting, and it always has been. If you want / need "good enough" sorting you need to implement your own sort methods. – Stephen C Mar 20 '16 at 03:23

user207421 · Answer 2 · 2013-08-08T01:44:37.577

0

I think you're barking up the wrong tree here. That piece of code does not throw that exception. I would want to see a stack trace, and I would also be looking at the ACustomClass.equals() method. Unless it tests the getAlong() results for equality, and nothing else, it doesn't agree with this Comparator, and one of them is therefore wrong, if used in a context where consistency with equals is required, such as a sorted collection, which is more probably where the exception is arising from.

You can address the scepticism experimentally. Unless they can come up with an actual formal reason why it can't work, you are certainly entitled to try it.

edited Aug 08 '13 at 01:44

answered Aug 08 '13 at 00:01

user207421

305,947
44
307
483

`equals` doesn't have to be consistent with the comparator. `Arrays.sort` doesn't use `equals`. – arshajii Aug 08 '13 at 00:06
@arshajii It doesn't say that in the Javadoc, but it does say "Caution should be exercised when using a comparator capable of imposing an ordering inconsistent with equals to order a sorted set (or sorted map)". If we're peeking at the source code, it doesn't throw that exception either. – user207421 Aug 08 '13 at 01:24

Another "Comparison method violates its general contract!"

2 Answers2