9

When comparing floating point values for equality, there are two different approaches:

  • NaN not being equal to itself, which matches the IEEE 754 specification.
  • NaN being equal to itself, which provides the mathematical property of Reflexivity which is essential to the definition of an Equivalence relation

The built in IEEE floating point types in C# (float and double) follow IEEE semantics for == and != (and the relational operators like <) but ensure reflexivity for object.Equals, IEquatable<T>.Equals (and CompareTo).

Now consider a library that provides vector structs on top of float/double. Such a vector type would overload ==/!= and override object.Equals/IEquatable<T>.Equals.

What everybody agrees on is that ==/!= should follow IEEE semantics. The question is, should such a library implement the Equals method (which is separate from the equality operators) in a way that's reflexive or in a way that matches the IEEE semantics.

Arguments for using IEEE semantics for Equals:

  • It follows IEEE 754
  • It's (possibly much) faster because it can take advantage of SIMD instructions

    I've asked a separate question on stackoverflow about how you'd express reflexive equality using SIMD instructions and their performance impact: SIMD instructions for floating point equality comparison

    Update: It seems like it's possible to implement reflexive equality efficiently using three SIMD instructions.

  • The documentation for Equals doesn't require reflexivity when involving floating point:

    The following statements must be true for all implementations of the Equals(Object) method. In the list, x, y, and z represent object references that are not null.

    x.Equals(x) returns true, except in cases that involve floating-point types. See ISO/IEC/IEEE 60559:2011, Information technology -- Microprocessor Systems -- Floating-Point arithmetic.

  • If you're using floats as dictionary keys you're living in a state of sin and should not expect sane behaviour.

Arguments for being reflexive:

  • It's consistent with existing types, including Single, Double, Tuple and System.Numerics.Complex.

    I don't know any precedent in the BCL where Equals follows IEEE instead of being reflexive. Counter examples include Single, Double, Tuple and System.Numerics.Complex.

  • Equals is mostly used by containers and search algorithms which rely on reflexivity. For these algorithms a performance gain is irrelevant if prevents them from working. Don't sacrifice correctness for performance.
  • It breaks all hash based sets and dictionaries, Contains, Find, IndexOf on various collections/LINQ, set based LINQ operations (Union, Except, etc.) if the data contains NaN values.
  • Code that does actual computations where IEEE semantic is acceptable usually works on concrete types and uses == / != (or more likely epsilon comparisons).

    You currently can't write high performance computations using generics since you need arithmetic operations for that, but these aren't available through interfaces/virtual methods.

    So a slower Equals method wouldn't affect most high performance code.

  • It's possible to provide an IeeeEquals method or an IeeeEqualityComparer<T> for the cases where you either need the IEEE semantics or you need to performance advantage.

In my opinion these arguments strongly favour a reflexive implementation.

Microsoft's CoreFX team plans to introduce such a vector type in .NET. Unlike me they prefer the IEEE solution, mainly due to the performance advantages. Since such a decision certainly won't be changed after a final release, I want to get feedback from the community, on what I believe to be a big mistake.

  • 1
    Excellent and thought provoking question. For me (at least), it doesn't make sense that == and Equals would return different results. Many programmers assume they are, and do the same thing. Furthermore - in general, implementations of the equality-operators invoke the Equals method. You have argued that one could include a IeeeEquals, but one might also do it the other way around and include a ReflexiveEquals-method. The Vector<float>-type may be used in many performance-critical applications, and should be optimized accordingly. – die maus Jan 23 '16 at 1:31
  • @diemaus Some reasons why I don't find that convincing: 1) for float/double and several other types, == and Equals are already different. I think an inconsistency with existing types would be even more confusing than the inconsistency between == and Equals you'll still have to deal with for other types. 2) Pretty much all generic algorithms/collections use Equals and rely on its reflexivity to function (LINQ and dictionaries), whereas concrete floating-point algorithms typically use == where they get their IEEE semantics. – CodesInChaos Jan 23 '16 at 10:56
  • I would consider Vector<float> to a different "beast" than a simple float or double. By that measure, I can't see the reason for Equals or the == operator to abide to the standards of them. You said yourself: "If you're using floats as dictionary keys you're living in a state of sin and should not expect sane behavior". If one were to store NaN in a dictionary, then it is their own goddamned fault for using terrible practice. I hardly think that the CoreFX-team didn't think this through. I'd go with a ReflexiveEquals or similar, just for performance sake. – die maus Jan 23 '16 at 19:05
5

I would argue that the IEEE behavior is correct. NaNs are not equivalent to one another in any way; they correspond to ill-defined conditions where a numeric answer isn't appropriate.

Beyond the performance benefits that come from using IEEE arithmetic that most processors support natively, I think there's a semantic problem with saying that if isnan(x) && isnan(y), then x == y. For instance:

// C++
double inf = std::numeric_limits<double>::infinity();
double x = 0.0 / 0.0;
double y = inf - inf;

I would argue that there's no meaningful reason why one would consider x equal to y. You could hardly conclude that they are equivalent numbers; they aren't numbers at all, so it just seems like an invalid concept entirely.

Furthermore, from an API design perspective, if you're working on a general-purpose library that is intended to be used by many programmers, it just makes sense to use the most industry-typical floating-point semantics. The goal of a good library is to save time for those who use it, so building in nonstandard behavior is ripe for confusion.

  • 3
    That NaN == NaN should return false is undisputed. The question is what the .Equals method should do. For example if I use NaN as a dictionary key, the associated value becomes unretrievable if NaN.Equals(NaN) return false. – CodesInChaos Jan 22 '16 at 20:51
  • 1
    I think you have to optimize for the common case. The common case for a vector of numbers is high throughput numerical computation (often optimized with SIMD instructions). I would argue that using a vector as a dictionary key is an extremely rare use case, and one hardly worth designing your semantics around. The counterargument that seems most reasonable to me is consistence, since the existing Single, Double, etc. classes already have the reflexive behavior. IMHO, that was just the wrong decision to begin with. But I wouldn't let elegance get in the way of usefulness/speed. – Jason R Jan 24 '16 at 19:15
  • But numerical computations will typically use == which has always followed IEEE, so they'd get the fast code no matter how Equals is implemented. IMO the whole point of having a separate Equals method is using in in algorithms that don't care about the concrete type, such as LINQ's Distinct() function. – CodesInChaos Jan 24 '16 at 19:18
  • 1
    I get that. But I would argue against an API that has an == operator and an Equals() function that have different semantics. I think you're paying a cost of potential confusion from a developer perspective, with no real benefit (I don't assign any value to being able to use a vector of numbers as a dictionary key). It's just my opinion; I don't think there's an objective answer to the question at hand. – Jason R Jan 24 '16 at 19:20
0

There is a problem: IEEE754 defines relational operations and equality in a way that is well-suited to numerical applications. It is not well-suited to sorting and hashing. So if you want to sort an array based on numerical values, or if you want to add numerical values to a set or use them as keys in a dictionary, you either declare that NaN values are not allowed, or you don't use IEEE754 built-in operations. Your hash table would have to make sure that all NaNs are matched to the same value, and compare equal to each other.

If you define Vector then you have to make the design decision whether you want to use it for numerical purposes only or whether it should be compatible with sorting and hashing. I personally think that the numerical purpose should be much more important. If sorting / hashing is needed then you can write a class with Vector as a member and define hashing and equality in that class the way you like.

  • 1
    I agree that numerical purposes are more important. But we already have the == and != operators for them. In my experience the Equals method is pretty much only used by non numeric algorithms. – CodesInChaos Jan 23 '16 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.