Ranges allocate 670 MB in 94 seconds of normal IDE usage in service.fs only

[cartermp]

Ranges are a struct, so it's strange that it would show up so high in the GC stats:

Taking a look, this is mostly due to equality comparisons:

Range is compared all over the place with = and <>. This actually leads towards GenericEqualityIntrinsic, which causes boxing:

https://github.com/Microsoft/visualfsharp/blob/32251218913b82390b6b11e374ea5ac84c2c56ad/src/fsharp/FSharp.Core/prim-types.fs#L1539-L1540

And this leads to lots of heap allocations.

[cartermp]

More general issue here: #526

But this is a rather pressing issue with data.

[abelbraaksma]

Wow, this may well be at the root of many of the heap alloc issues we have, I can imagine this also happens with many more types. Can the generic comparer be written in a way to avoid boxing?

[cartermp]

I'm not sure the function is inherently bad.

The fact that F# structs are boxed if they are defined with NoEquality is the issue, and because this is the case with the range type in the compiler, it's definitely showing up in IDE tooling perf. These ranges are compared a lot and in pretty much every IDE scenario.

What's ironic is that these structs are boxed, only to end up calling an overridden Equals that merely compares the values of in64 values:

https://github.com/Microsoft/visualfsharp/blob/0302e63de164bce738317486c672f45ec9128b5b/src/fsharp/range.fs#L192

[TIHan]

After an intense night with Optimizer.fs, I managed to output the IEquatable<'T>.Equals for types. However, this kind of change involves some slight semantic differences and later I will describe what is going on. The upside is that it is an order of magnitude better perf for structs when using =.

Related topics:
#556
#526
#513
#966
#5307

@manofstick I'm now walking down your path and I see the demons you had to come across.

[TIHan]

Quoting from @dsyme #513 (comment) :

It's possible that we would ultimately be willing to take a change along the lines of "As of F# V.v and FSharp.Core X.X.X.X, the generic comparison logic will compare types defined in freshly compiled code which implement IComparable or IStructuralComparable via the generic interface rather then the non-generic interface IComparable".

If we backed that up by performance figures showing the reduction in boxing then it could well seem very acceptable. However that should definitely be a separate PR to the core work you're doing to improve performance without changing the preference order for comparison.

[manofstick]

@TIHan

hahah. Yeah in all production code where I use value types, I give them CustomEquality just so I can override the boxing Equals operator and throw an exception in it to find all uses!!

Anyway, #5307 is a good PR (if I do say so myself!) It should be 100% compatible with existing code - and although not quite as as optimal as outputting IEquatable's Equals, it's non-boxing, and pretty good. There is a slight initial runtime cost (to use reflection) but then gone.

And the benefit has over compiler injection is that it works for generic code - think collection classes at a bare minimum.

and eventually you could modify the compiler to follow the same rules (i.e. scour the type definitions to determine what sort of equality is required)...

[TIHan]

@manofstick I need to look at your PR a bit more. I am curious how you avoid boxing when the first call to equality is IStructuralEquality.Equals(object, IEqualityComparer).

[manofstick]

@TIHan

magic

[manofstick]

@TIHan

I modified the compiler in some places, but there were others where I didn't, so possibly it doesn't it the cases you actually care about. I can't remember what it does actually. Been too long :-)

[manofstick]

@TIHan

Slowing memories are creeping - I think the reason the compiler put in the IStructuralEquality.Equals(object, IEqualityComparer) was because it had already run a round of "optimizations" (i.e. inlining), as the initial equality operation put in was the function that I hijacked... It was more efficient for me to stop the compiler from doing that optimization - maybe I stopped the inlining? But I really can't remember if I did end up doing that...

[TIHan]

So, the fundamental problem is that we don't have IStructuralEquality<'T> existing today, and IStructuralEquality.Equals(object, IEqualityComparer) takes precedence over IEquatable<'T>.Equals('T) and override __.Equals(object). F# defined records, unions, and struct types implement all of them by default and IStructuralEquality.Equals gets called first; we technically could make one optimization that could avoid boxing for the receiver of that call on override __.Equals and IStructuralEquality.Equals, but the first argument on both those calls will still be boxed.

However, F# defined records, unions, and struct types (without [<CustomEquality>]), IStructuralEquality.Equals and IEquatable<'T>.Equals and Equals will give you the same result, unless you call StructuralEquality.Equals with your own custom comparer rather than the F# default one defined in prim-types.fs. Because = will ultimately call IStructuralEquality.Equals with the F# default comparer, we can guarantee that IEquatable<'T> for a F# type that does not have [<CustomEquality>] (not explicit) in theory should be safe to call directly and not break equality semantics. At least, this is what I think is true.

As soon as you do [<CustomEquality>] or have a type that implements IStructuralEquality.Equals, we can't call IEquatable<'T>.Equals directly as you may be providing different types of equality; meaning, IEquatable<'T> could be doing reference equality and IStructuralEquality doing full structural equality. The same goes for C# types that implement IStructuralEquality. Luckily, only a few types in .NET Framework/Core implement IStructuralEquality, namely, Array, Tuple and ValueTuple. And these are handled specially in F#, except for ValueTuple because we probably forgot about doing that. System.Numerics vector types do not implement IStructuralEquality.

For this issue in particular with ranges, the solution without potentially harming equality in F# is to just make a function call to check range equality instead of using =.

[TIHan]

Closing as we merged the PR to resolve this issue. A long term solution would be to devirtualize =, so we get perf improvements for all F# structs.