Repository navigation
Ranges allocate 670 MB in 94 seconds of normal IDE usage in service.fs only #6047
Description
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:
And this leads to lots of heap allocations.
Activity
cartermp commentedon Dec 21, 2018
More general issue here: #526
But this is a rather pressing issue with data.
[-]Ranges allocate 670 MB in normal IDE usage[/-][+]Ranges allocate 670 MB in 94 seconds of normal IDE usage in service.fs only[/+]abelbraaksma commentedon Dec 21, 2018
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 commentedon Dec 21, 2018
I'm not sure the function is inherently bad.
The fact that F# structs are boxed if they are defined with
NoEqualityis 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
Equalsthat merely compares the values ofin64values:https://github.com/Microsoft/visualfsharp/blob/0302e63de164bce738317486c672f45ec9128b5b/src/fsharp/range.fs#L192
TIHan commentedon Dec 21, 2018
After an intense night with Optimizer.fs, I managed to output the
IEquatable<'T>.Equalsfor 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 commentedon Dec 21, 2018
Quoting from @dsyme #513 (comment) :
manofstick commentedon Dec 21, 2018
@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 commentedon Dec 21, 2018
@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 commentedon Dec 21, 2018
@TIHan
magic
manofstick commentedon Dec 21, 2018
@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 commentedon Dec 21, 2018
@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 commentedon Dec 21, 2018
So, the fundamental problem is that we don't have
IStructuralEquality<'T>existing today, andIStructuralEquality.Equals(object, IEqualityComparer)takes precedence overIEquatable<'T>.Equals('T)andoverride __.Equals(object). F# defined records, unions, and struct types implement all of them by default andIStructuralEquality.Equalsgets called first; we technically could make one optimization that could avoid boxing for the receiver of that call onoverride __.EqualsandIStructuralEquality.Equals, but the first argument on both those calls will still be boxed.However, F# defined records, unions, and struct types (without
[<CustomEquality>]),IStructuralEquality.EqualsandIEquatable<'T>.EqualsandEqualswill give you the same result, unless you callStructuralEquality.Equalswith your own custom comparer rather than the F# default one defined inprim-types.fs. Because=will ultimately callIStructuralEquality.Equalswith the F# default comparer, we can guarantee thatIEquatable<'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 implementsIStructuralEquality.Equals, we can't callIEquatable<'T>.Equalsdirectly as you may be providing different types of equality; meaning,IEquatable<'T>could be doing reference equality andIStructuralEqualitydoing full structural equality. The same goes for C# types that implementIStructuralEquality. Luckily, only a few types in .NET Framework/Core implementIStructuralEquality, namely,Array,TupleandValueTuple. And these are handled specially in F#, except forValueTuplebecause we probably forgot about doing that.System.Numericsvector types do not implementIStructuralEquality.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 commentedon Dec 22, 2018
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.