Equality operator causes boxing on value types

[asik]

Comparing value types with the equality operator (=) causes unnecessary boxing to occur. Tested on Visual Studio 2015 RC. I described the issue in this StackOverflow question.

Example:

[<Struct>]
type MyVal =
    val X : int
    new(x) = { X = x }

for i in 0 .. 10000000 do
      (MyVal(i) = MyVal(i + 1)) |> ignore;;
Real: 00:00:00.077, CPU: 00:00:00.078, GC gen0: 38, gen1: 1, gen2: 0

My totally uninformed guess here is that the type is casted to IEquatable<_> before the strongly typed Equals is then called.

But it gets worse! If custom equality is defined:

[<Struct;CustomEquality;NoComparison>]
type MyVal =
    val X : int
    new(x) = { X = x }
    override this.Equals(yobj) =
        match yobj with
        | :? MyVal as y -> y.X = this.X
        | _ -> false
    interface System.IEquatable<MyVal> with
        member this.Equals(other) =
            other.X = this.X

for i in 0 .. 10000000 do
      (MyVal(i) = MyVal(i + 1)) |> ignore;;
Real: 00:00:00.497, CPU: 00:00:00.500, GC gen0: 77, gen1: 1, gen2: 0

Then the equality operator calls Equals(obj), boxing both operands in the process! Nevermind the casts then required. As you can see this results in roughly twice the amount of GC pressure.

Even for reference types, this is suboptimal because casts are required.

The only workaround this problem is systematically avoid use of this operator, which may not be feasible when using generic code in third-party F# libraries. I see no reason why the compiler shouldn't generate a direct call to IEquatable<T>.Equals without boxing or casts; a call that could then be properly inlined by the CLR in many cases.

[manofstick]

FYI I'm attacking some boxing issues in #513, but this case is still kind of an issue (your second example no longer causes boxing with that change applied). As I've been playing around in the equality space for a while, I don't think there is a particularly easy answer to this (i.e. one that doesn't change existing code functionality) although I do offer some possibilities at the end of this posting.

The reason is that their are three classes of equality; "PER", "ER" and "Other" (basically how to deal with floating point NaNs, as well as just any old equality to want to throw at it.)

IStructuralEquatable deals with any of these by the IEqualityComparer that is passed in.
IEquatable<'a> is hardcode using "ER"
obj.Equals defers to the IEquatable

The problem is that by default "=" does so with PER equality, and to change it would be a breaking change. So you can't just have any old struct deferring it's equality to the Equals method without checking all it's members.

Here is an example of the issue:

let nan1 = Double.NaN
let nan2 = Double.NaN

System.Console.WriteLine (if nan1 = nan2 then "nan1 = nan2" else "nan1 <> nan2")
System.Console.WriteLine (if nan1.Equals nan2 then "nan1 = nan2" else "nan1 <> nan2")

let nan1 = { Value = Double.NaN }
let nan2 = { Value = Double.NaN }

System.Console.WriteLine (if nan1 = nan2 then "nan1 = nan2" else "nan1 <> nan2")
System.Console.WriteLine (if nan1.Equals nan2 then "nan1 = nan2" else "nan1 <> nan2")

With the results

nan1 <> nan2
nan1 = nan2
nan1 <> nan2
nan1 = nan2

So anyway, I said that your second version now doesn't cause boxing, and this is because it doesn't implement IStructuralEquatable, so it doesn't have to worry about this ER/PER split, and it does have the IEquatable<'a> so that is used.

Anyway, a potential solution to solve this problem fully could be to recursively check a value type to ensure that it has not floating point numbers in it or subtypes; which is a bit dirty; or alternatively a better solution, although a bit bloaty, might be to create a new interface IEquatablePER<'a> and have the compiler generate those for value types (and records) and then defer to those. Now I'm not a Microsoft employee, or on any committee that makes such decisions, so I can't tell you if this is likely to be done.

[asik]

Or take the breaking change and fix the nan inconsistency... Having to box structs in simple equality comparisons is a high price to pay to maintain what is anyway a bug. You think you're saving on GC pressure and you're actually causing a ton more, this makes structs almost useless.

Of course with your PR one will be able to work around the issue by defining custom equality, but it's an obscure fix and it feels like writing C#.

[latkin]

@asik -- scenarios like this are exactly why the NonStructuralComparison operators were added in F# 4.0.

[<Struct>]
type MyVal =
    val X : int
    new(x) = { X = x }
    static member op_Equality(this : MyVal, other : MyVal) =
        this.X = other.X

module Default =
    let test () =
        for i in 0 .. 10000000 do
              (MyVal(i) = MyVal(i + 1)) |> ignore

module NonStructural =
    open NonStructuralComparison
    let test () =
        for i in 0 .. 10000000 do
              (MyVal(i) = MyVal(i + 1)) |> ignore

// Real: 00:00:00.089, CPU: 00:00:00.093, GC gen0: 29, gen1: 1, gen2: 0
Default.test()

// Real: 00:00:00.003, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
NonStructural.test()

That's not to say we should ignore potential perf improvements to the default operators, certainly not. But at least there is a fairly straightforward workaround available with 4.0. You just need to define op_Equality, similar to how you need to implement == in C#.

[asik]

@latkin Good to know! I'll update my Stackoverflow answer with this information.
"open NonStructuralComparison" does have the unfortunate effect of disabling equality for DUs and Records across the module (the code ceases to compile). It's a workaround all right, but it doesn't seem to play nice with standard F# features.

[latkin]

Yes, simply opening NonStructuralComparison is a bit blunt. See this convo, and an approach for encapsulating NonStructuralComparison in dedicated operators here.

[manofstick]

@asik

An alternative to NonStructuralComparison could be

module EquatableModule =
    let inline eq<'a when 'a :> System.IEquatable<'a>> (x:'a) (y:'a) = x.Equals y
    let inline (==) x y = eq x y
    let inline (!=) x y = not (eq x y)

Which would mean you wouldn't need to implement op_Equality, rather just use the c#esq operators (not sure if that is a good choice or not! Name them what you will...)

[manofstick]

@asik

Oh, and you're still going to run into lots of trouble using value types anyway. Using them as keys to containers, embedding them in other objects, in the 64-bit JIT when they are greater than 64-bits and used as parameters in a function that uses the "tail" IL instruction (this is due to calling conversion rules), using things like List.find on a list of structs...

#513 resolves many of these issues, but they should still be used knowing that there are potential pitfalls all over the shop...

[asik]

@manofstick Looks like your (==) does the right thing for everything that's structurally equatable (records, DUs) as well as for structs. Everything is fast and correct. Might as well rename it (=), ignore the compiler warning, <AutoOpen> it as the first module in your project and use it everywhere? After that it's perhaps just a matter of avoiding library functions that use the default (=), like using List.exists rather than List.contains.

Only issue I can see is that this'll create compilation errors for types that don't implement IEquatable(T), but that's actually very nice, I'd like to be warned about that.

[manofstick]

@asik,

Will I wouldn't really recommend it, but each to their own; and whoever has to support the code in the future! As overriding = would mean that they couldn't use it for structural equality on containers, including arrays. Plus the subtle change of meaning for floating point numbers doesn't help.

And most of the time the performance just doesn't matter. I agree that when it does, it certainly does, but that can just be profiler guided.

Anyway, this is really a stackoverflow discussion, rather than an issue here. So I will end it here.

[asik]

I disagree that this should resolved as by design. This is surprising behavior and a performance trap. It affects all library code that uses this operator or structural equality, like Array.contains, Array.except, Array.distinct (and the same in Seq, List); causing N allocations for an input of size N is not a small performance problem, especially for larger value types (for ex. a 4x4 matrix of floats). There is no way to know which functions to avoid except through benchmarking. This reduces F#'s appeal in low-latency or high performance applications.

[dsyme]

OK, reopening. As mentioned above much of the impact is reduced by the combination of #513 and the dilegent use of NonStructuralComparison.