IComparer issue

Question

I have a weird issue and I don't have a clue to track the reason. I will try to descript my issue clearly.

I have a RTree class, in this class, I want to compare two rectanlge (here I called envelope, it contains minX, minY, maxX, maxY), so we have a comparer class as following:

private class AnonymousXComparerImpl : IComparer
{
    public AnonymousXComparerImpl()
    { }

    public int Compare(object o1, object o2) 
    {
        IEnvelope ea = (IEnvelope)((IBoundable)o1).Bounds;
        IEnvelope eb = (IEnvelope)((IBoundable)o2).Bounds;
        double a = (ea.MinX + ea.MaxX) / 2d;
        double b = (eb.MinX + eb.MaxX) / 2d;
        return a > b ? 1 : a < b ? -1 : 0;
    }
}

With this comparer, we can maintain a ArrayList of envelope and sort it easily, the envelopes are randomly added. When we call the following code and we met the

Unable to sort because the IComparer.Compare() method returns inconsistent results. Either a value does not compare equal to itself, or one value repeatedly compared to another value yields different results.

sortedChildBoundables.Sort(new AnonymousXComparerImpl());

Here is the weird part. This error only occurs in .net 4.0 which doesn't install the VistualStudio. If the machine installed the VS or .net 4.5, this issue cannot reproceduce again.

In this case, I cannot figure out why it happens. It will be great if you have any experience on debuging this kind of issue, I appreciate.

Thanks, Howard

The only thing I can think of here is floating point issues meaning equality doesn't quite match for the same items, no idea why it'd be specific to v4. Have you tried enforcing a level of rounding? — Adam Houldsworth, May 08 '13 at 07:52
There's no other threads involved are there? Also, this thread may be of interest: http://stackoverflow.com/questions/6683059/are-floating-point-numbers-consistent-in-c-can-they-be — Matthew Watson, May 08 '13 at 07:56
Thank you guys, I will give a quick try and post the result soon. — Howard, May 08 '13 at 08:03
@Howard Beware that switching to `Decimal` will likely make the comparison hundreds of times slower - possibly not a problem for you, but you should be aware. — Matthew Watson, May 08 '13 at 08:09
Very interesting question. Could you post the code of your *RTree* class? Additionally, could you show us how you populate *sortedChildBoundables*? — Piotr Justyna, May 08 '13 at 08:11
Thank you, Matthew. I will be aware of that. Henrik, it can be NaN, but it still works in my testing. — Howard, May 08 '13 at 08:13
Have you tried just using `return a.CompareTo(b);` instead? Your problem might be that NaN != NaN. — Seph, May 08 '13 at 08:52
Not related to your question, but instead of having your class `AnonymousXComparerImpl` implement the interface `IComparer` directly, it is better to use `Comparer` as a base class (and not mention any interfaces explicitly). You only need one method again (this time an `override` of an `abstract` method from the base class). The advantage is that you will not have to cast, and that your type will be both an `IComparer` and an `IComparer` automatically. This is useful once you start using type-safe collections (such as `List` instead of `ArrayList`). — Jeppe Stig Nielsen, Jan 21 '16 at 09:16

Henrik · Accepted Answer · 2016-01-21T10:48:52.553

5

If e.g. ea.MinX is NaN, a will be NaN and both a > b and a < b will be false. This means, there are objects which compare equal to every other object.

You first have to decide, how you want objects containing NaN to be sorted.

An easy workaround might be to insert

if (double.IsNaN(a)) a = 0.0;
if (double.IsNaN(b)) b = 0.0;

As noted by @Seph and @Jeppe in comments, double.CompareTo does the right thing, so the last line can be replaced by return a.CompareTo(b);.

edited Jan 21 '16 at 10:48

answered May 08 '13 at 08:47

Henrik

23,186
6
42
92

+1 This sounds plausible - although I'm not sure why the results would differ between .Net versions. But if there *can* be NaNs in the data (and the OP says there can) then it will definitely cause the kind of issue that was observed. – Matthew Watson May 08 '13 at 09:19
That makes sense, please allow me to hold this thread for awhile and mark as answer later. Thank you so much. – Howard May 08 '13 at 09:38
2

@MatthewWatson - maybe the `Sort` function in the new version doesn't do unnecessary compares and therefore can't detect inconsistencies. – Henrik May 08 '13 at 11:24
1

It is simpler to only replace the last line in the original code (the question) with: `return a.CompareTo(b);`. The method `double.CompareTo(double)` handles `NaN` and infinities. It will not project to `0.0`, though.`NaN` will go before any negative number. _Addition:_ Just saw that Seph suggested this a long time ago in a comment to the question. – Jeppe Stig Nielsen Jan 21 '16 at 09:08

score 0 · Answer 2 · answered Jan 21 '16 at 08:27

One likely reason is that your information is actually changed during compare.

If you do the sorting in a background thread you will certainly get this error if the comparison get different values for the same item when asking for it twice.

If your main thread updates one of the values (maybe by databinding) while the comparison runs for example.

Make sure you cache the value compared so that you always return consistent results. Or accept that the error may happen from time to time and redo the sort if it does.

This will also explain your feeling of machine/os dependency. Multithreading issues occur differently depending of software and hardware differences.

IComparer issue

2 Answers2