dotnet
Equality operator causes boxing on value types
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.
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.
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#.
@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#.
@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.
Yes, simply opening NonStructuralComparison is a bit blunt. See this convo, and an approach for encapsulating NonStructuralComparison in dedicated operators here.
@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...)
@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...
@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.
@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.
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.
OK, reopening. As mentioned above much of the impact is reduced by the combination of #513 and the dilegent use of NonStructuralComparison.
I have encountered this issue while making some research on F# equality. To me, this is surprisingly frightening. Any love for this?
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
@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?
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.
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!
@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.
@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.
@onurgumus
Short answer: you'll just have to believe me!
Longer answer: there are more complex rules around how f# handles equality than straight IEquatable and they have to be honoured.
Similarly the comparison only considers IComparable and not IComparable<'T> causes boxing as in below code:
[<Struct; CustomComparison; CustomEquality>]
type MyVal =
val X : int
new(x) = { X = x }
override this.Equals other =
match other with
| :? MyVal as y -> this.Equals y
| _ -> false
override this.GetHashCode() = this.X
member this.CompareTo (other:MyVal) = this.X.CompareTo(other.X)
member this.Equals (other:MyVal) = other.X = this.X
with
interface System.IComparable with
member this.CompareTo other =
match other with
| :? MyVal as y -> this.CompareTo y
| _ -> failwith "not comparable"
interface System.IComparable<MyVal> with
member this.CompareTo other = failwith "never comes to here"
interface System.IEquatable<MyVal> with
member this.Equals other = failwith "never comes to here"
let s =[for i in 0 .. 1000 do
yield MyVal(i)]
System.GC.Collect()
#time
for i in 0 .. 1000 do
List.filter (fun item -> item > (MyVal(4))) s |> ignore
with the output:
--> Timing now on
Real: 00:00:00.133, CPU: 00:00:00.140, GC gen0: 19, gen1: 2, gen2: 1
So much for the struct performance in F#!
@OnurGumus
Yes, #513 looked after IComparables as well.
OK, the problem is that f# views equality/comparison as structural, which means that things
let a = [ for i = 0 to 9 do yield i + 1 ]
let b = [ for i = 2 to 11 do yield i - 1 ]
if not (obj.ReferenceEquals (a, b)) then printfn "nothing up my sleeve!"
if a = b then printfn "equality for all!"
work. Or on generic record types that you create:
type X<'a> = {
A : 'a
}
let a = { A = 1 }
let b = { A = 1 }
if not (obj.ReferenceEquals (a, b)) then printfn "nothing up my sleeve!"
if a = b then printfn "equality for all!"
But the point is that in library code you are not aware of what types are going to be passed. i.e. you mightn't have a type which supports equality stored within an array. Or it's rules are different from normal equality - such as the way that arrays are handled.
Anyway. As I have said about half a dozen times, that is what #513 was for. It needs to be fixed - and needs confirmation from @dsyme that it will be accepted; it does dynamically create types which is not compatible with .net native, which may be a showstopper. But, I'm currently busy. I hope to get back to it at some stage in the not too distant future. If you want to help, then help me finish #2587 so that I can get back to this. Thanks.
We just experienced this issue using a Dictionary with Guid keys. 630 MB of Guids were allocated in our scenario. We are now reviewing our code for uses of '=' on structs in general. A compiler warning to find such usages would be greatly appreciated.
@christian-clausen
It is a shame. It's not just = though, it's usage through containers, to members in records - especially then you have to consider generics. It's quite nasty. So making a warning would be difficult (impossible?) to cover all usages; so would it really be a good warning? (Maybe some code analyser could at least offer some hints, albeit in a limited form)
I've tried, and tried to get something suitable to fix this but I just didn't get into the fsharp early enough in it's lifecycle, and now any change is going to be a breaking one - it appears that it's unacceptable to prefer IEquatable<>.Equals(...) over object.Equals(...) and technically this is a breaking change. But sad.
Anyway, it has lost me as an fsharp developer, which is a shame as I really love writing code in fsharp, but with advancements in csharp over the years, it's, for the type of code I write, a lesser worse option. (I mean most people probably just don't care about performance at this level, so it's mostly a non-issue, which is why it's never found enough traction to solve, and I understand that. But does make me sad.)
...as a caveat, adding Guids is probably reasonable and sensible (been a long time since I delved into the code, but I thought they already did, but obviously not from your discovery), as they can guarantee Equality not being a breaking change there. But I extensively use NodaTime (as anyone who write multi-timezone code should!), which mainly has value types, and they can't obviously extend out handling to arbitrary libraries.
By the way, what is the state of FSharpAnalyzers? It was quite a theme like year or two ago. All those usages could be found with an analyzer and converted to custom "==" meaning IEquatable equality or some other.
In compiler there are many examples of this too. Not only structs but array/list equality and this makes compiler code slower for no good reason honestly @dsyme @vzarytovskii @KevinRansom
Having analyzers for a trap like this would be great. One mitigation we are trying is to annotate all (many) structs with [<NoEquality; NoComparison>] as well as a custom IEquatable<_> implementation (and ignore the warning - and hope that mechanism doesn't get forbidden) and then use the == operator as defined above to ensure IEquatable<_>.Equals is used to avoid boxing. Structs from external libraries is a different situation. IL-rewriting?
Well, my benchmarking tests show that you don't really have to put [<NoEquality; NoComparison>] on a struct as compiler generated equality is good enough. I mean in a case where you just have to check all fields in an expected manner. Well, you obviously have to do this if you have your own special rules for equality. But in many cases default one is great.
So overriding "==" is usually enough.
I don't know what to do with external libraries tho (non F# especially). Also, comparing arrays and lists and so on using default "=" operator costs greatly too.
@En3Tho The only reason for adding [<NoEquality; NoComparison>] was to get compiler errors so as to know what code to fix to use '==', as there is no compiler, analyzer or analyzer tooling for VS proper to find these cases otherwise. Using these attributes unfortunately but understandably removes the default IEquatable<_> implementation though, and so you have to reimplement manually - and for all types wrapping these types as well. A more sensible approach is perhaps to put all [<NoEquality; NoComparison>] declarations inside a conditional compilation directives which can be switched on for checking purposes.