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.

[OnurGumus]

I have encountered this issue while making some research on F# equality. To me, this is surprisingly frightening. Any love for this?

[asik]

I'm getting the same performance numbers on the current Visual F# 2017 nightly.
This has also become more relevant with the addition of struct tuples, struct records and struct DUs. You would not expect using struct tuples, for instance, to greatly increase GC and execution time:

let foo() =
    let mutable b = false
    for i in 0 .. 10000000 do
        b <- ((i, i) = (i + 1, i + 1)) && b
    b        
foo() |> printfn "%A";;
false
Real: 00:00:00.009, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

let foo() =
    let mutable b = false
    for i in 0 .. 10000000 do
        b <- (struct(i, i) = struct(i + 1, i + 1)) && b
    b        
foo() |> printfn "%A";;
false
Real: 00:00:01.287, CPU: 00:00:01.281, GC gen0: 107, gen1: 1, gen2: 0

[manofstick]

@OnurGumus

The Phoenix of #513 will rise again at some stage, but i have been on a bit of a round about adventure which sees me currently in #2587

Although I do see that @dsyme had given this the "urgency soon" and "bug" labels; so maybe they have some alternative thoughts on this?

[OnurGumus]

I think the correct solution here is to define a new equals operator dedicated to structs. And compiler should give a warning for the old usage. This way nothing breaks and people can gradually fix their code

And yes, the code for FSharp.Core also has to change for the things like List.contains which also would do boxing by default for user defined value types.

[OnurGumus]

Here's a script file demonstrating the problem for List.contains :

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

let s = [for i in 0 .. 1000000 do
            yield MyVal(i)]

System.GC.Collect()
#time

for i in 0 .. 10000000 do
    List.contains (MyVal(4)) s |> ignore

and the output is:

--> Timing now on

Real: 00:00:01.259, CPU: 00:00:01.250, GC gen0: 572, gen1: 0, gen2: 0
val it : unit = ()

And none of the above fixes will prevent this problem!

[manofstick]

@OnurGumus

It's not quite that simple. Internally in library functions such as groupBy or the list element comparisons or tuples etc. what you have suggested just doesn't work. This was the reason why #513 existed.

[OnurGumus]

@manofstick Sorry but I fail to see how #513 is relevant to this issue at all. Correct me if I am wrong but #513 is about an optimization regarding value types with generic type parameters. Here we don't have that.

Finally I don't get why it is not simple to fix the below code for List.contains in F# Core:

 [<CompiledName("Contains")>]

        let inline contains e list1 =

            let rec contains e xs1 =

                match xs1 with

                | [] -> false

                | h1::t1 -> e = h1 || contains e t1

            contains e list1

There is a single e = h1 expression leading to boxing. We just need to get rid of it with a proper equality checking.

[vzarytovskii]

Main issue with that is still a backwards compatibility and we don't exactly have a plan on how to solve it as well as don't have approval from @dsyme for an opt-out approach.

I'm also not entirely sure how can we make all library functions work with that opt-out approach, since can't really do any shadowing in dlls

[dsyme]

I'm not sure how widespread knowledge is of open NonStructuralComparison. This switches all the core operators to use op_Equality static member overloads etc. and is a great way of finding many places in your code you are relying on structural equality. You can then make uses of structural equality explicit using === or some other self-defined operators

This approach doesn't solve the issue generally:

• requires the definition of the C#-style operator methods manually,
• doesn't allow structural comparison on lists, tuples etc. that recursively do operator-constrained comparison on leaf types.
• doesn't redefine FSharp.Core primitives that implicitly do structural comparison (List.contains etc.) , though in theory it could.

Despite that it can certainly help root out problems and I think deserves to be much better known

https://fsharp.github.io/fsharp-core-docs/reference/fsharp-core-operators-nonstructuralcomparison.html

[dsyme]

@brianrourkeboll It looks to me the huge difference you notice is really due to something else: the reduction of the integer sequence to a fast for-loop is not occurring in the first example. This has the flow on effect of boxing in equality - but solving the second problem wouldn't solve the first problem for this particular example.

I think (not sure, it's been a while) this is because this particular "optimization" is done during type checking, and full type information is not known to allow it to proceed. I believe (not sure) that this can be "fixed" by also doing the reduction doing optimization if necessary (it still has to be done in type checking as well because the optimization is visible in quotations, when it applies).

[brianrourkeboll]

@dsyme

@brianrourkeboll It looks to me the huge difference you notice is really due to something else: the reduction of the integer sequence to a fast for-loop is not occurring in the first example.

Hmm, I'm not sure I follow. The for i = 0 to data.Length - 1 do seems to be translated to a (fast) while loop for both. To remove the (slow) array initialization from the comparison:

#time "on"

let fast (xs : int array) =
    let genericFSharpEquality (value : 'T) (data : 'T[]) =
        let mutable found = 0

        for i = 0 to data.Length - 1 do
            if data.[i] = value then
                found <- found + 1

        found

    let _ = genericFSharpEquality 1 xs
    ()

let slow (xs : int array) =
    let genericFSharpEquality (value : 'T) (data : 'T[]) =
        let mutable found = 0

        for i = 0 to data.Length - 1 do
            if data.[i] = value then
                found <- found + 1

        found

    ignore (genericFSharpEquality 1 xs)

let xs = [|1..1_000_000|]

then:

fast xs // Real: 00:00:00.002, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

slow xs // Real: 00:00:00.024, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0

[dsyme]

@brianrourkeboll You're correct, my bad.

[dsyme]

I see. The difference is that genericFSharpEquality has been inlined (and thus type-specialized) in one and not the other. I believe the inlining has happened because it the first has an "immediate" use of genericFSharpEquality. That said there's no real reason why the second couldn't also do the inlining given it's the only use of the local generic function.

Anyway, when it occurs this kind of inline+type-specialization is indeed a huge performance gain and can transform expensive generic equality calls to very inexpensive integer comparisons.

No matter how generic equality is implemented you tend to get this kind of thing. That said, it may be possible to make dramatic improvements to the generic equality non-inlined implementation, e.g.

• type-specializing it for integer types.
• type-specializing it for floating-point types.
• type-specializing it for tuple, list and array types.

By type specializing I mean something like if typeof<T>.Equals(typeof<int>) then .... IIRC some variation on this is now statically reduced in .NET code as the JIT specializes generic code - at least my understanding is .NET Core now has many techniques now for declaring type specializations within implementations and it may be worth looking at using these within LanguagePrimitives.HashCompare.GenericEqualityIntrinsic

Again this doesn't fully address the boxing problem by any means.

[asik]

Could the optimizer be made smart enough to look at struct types recursively and inline the comparison if it doesn't contain any members that require structural comparison? That would at least solve the problem in many common cases, with e.g. Matrix and Vector types in game engines.

[ScottArbeit]

Issue mentioned in F# developer stories: how we’ve finally fixed a 9-year-old performance issue.

[gdar91]

Boxing still happens in some cases. Take this code snippet for example, when a record is generic and it takes type of another struct record/union:

open System.Runtime.CompilerServices

type [<IsReadOnly; Struct>] MyRecord<'a> =
    { MyString: string;
      MyInt: int
      A: 'a }

type [<IsReadOnly; Struct>] MyNestedRecord =
    { MyNestedValue: int }

let test () =
    let record1 = { MyString = "MyString 1"; MyInt = 10; A = { MyNestedValue = 10 } }
    let record2 = { MyString = "MyString 2"; MyInt = 10; A = { MyNestedValue = 10 } }
    let mutable i = 0
    let mutable result = 0
    while i < 1000000000 do
        let record = { MyString = "MyString 1"; MyInt = 10; A = { MyNestedValue = 10 } }
        let result1 = if record = record1 then 1 else 0
        let result2 = if record = record2 then 1 else 0
        result <- result + result1 + result2
        i <- i + 1
    result

let result = test ()

printfn $"Result: %d{result}"

When comparing, it will still box the nested MyNestedRecord structs (but not the top-level one).