Fsharp: F# compiler becomes abnormally slow

[quant1729]

F# compiler becomes abnormally slow when it compiles a code based on generic overloads. Libraries that are based on this feature of the language are victimized by this bug. e.g. FsControl, FSharpPlus.

Example code to reproduce the bug: https://gist.github.com/gmpl/5c2fae2d6e6a115d729e

In addition to that F# Intellisense stops working normally, VS consumes CPU and memory uncontrollably, VS hangs and stops responding when requested to quit.

Example code to reproduce the bug:
https://github.com/gmpl/FSharpPlus/blob/master/FSharpPlus/Samples/Learn%20You%20a%20Haskell.fsx

Used environment: VS 2013 Update 4, F# 3.1, .NET 4.5, Win 8.1 x64

[KevinRansom]

@arcturius
This may have been fixed for our Oob release 3.1.2: https://visualfsharp.codeplex.com/workitem/37

You can get the Oob release here: https://visualstudiogallery.msdn.microsoft.com/06b5edaf-9557-4987-b64e-f1722b015e86?SRC=Home

Let us know if this works for you.

[quant1729]

I installed Oob release now. Seems like the problem persists. F# Intellisense stops working normally, VS consumes CPU and memory uncontrollably. How can I check that I actually use this new version of F# this time, not some old version?

[latkin]

I can reproduce the compiler symptom in F# 4.0 - it indeed takes about ~10x longer to compile the KVP guys compared to the tuple guys.

[quant1729]

Hi guys, any ETA on the fix please?

[latkin]

Hi @arcturius, this will be fixed whenever someone gets around to it. It's not currently at the top of the priorities list.

If you need this addressed sooner, you are of course welcome to submit a PR with a fix yourself, which we would be happy to accept assuming proper implementation and testing.

[quant1729]

too bad. it is a serious issue in our project. Unfortunately neither of us are skilled to fix the compiler.

[dsyme]

The F# constraint solver is optimized for some things and not others. From the look of it, the FSharpPlus and FsControl libraries have driven the mechanisms available into the "other" areas pretty solidly.

We can hope to eventually fix the performance for this case, but it seems that, methodologically, the FSharpPlus library is still going to find another way of pushing beyond the limits. Given this, I recommend that the design of the FSharpPlus library be adjusted to be within scope of what gets solved efficiently.

So I think the way to make progress is to send a PR to FSharpPlus and FsControl to reduce the use of member constraints and simplify the overload resolution sets. Alternatively, structure your code to be less dependent on libraries like this.

[quant1729]

Hello Don, I strongly disagree with the points you made and the approach to the problem in general. I have sent you email with the details. Thanks.

[drvink]

Hi @dsyme (I'll comment here since this is the canonical bug)--not trying to be difficult, but how minimal of a case are you looking for? Would a small example making use of only Map from FsControl be acceptable? (I'd have to double-check, but I don't think it relies on any other types, so it ought to work as an issue-inline example :))

[dsyme]

Hi @drvink

Any minimizing is useful, as well as information about the necessity of the library design and alternative possible. (I suppose the priority of this issue is based largely on whether the library be reasonably - and even beneficially - redesigned to make normal uses of the library efficient)

cheers
don

[drvink]

Thanks for the clarification; I'll try to make a minimized case later.

As for the necessity of the design of a library like this, it enables a great deal of flexibility without even needing language support for higher-kinded polymorphism. Any library that implements the right overloads can make use of the reusable combinator functions in FsControl (fmap, <*>, etc.). Otherwise, each library has to implement its own incompatible version of these functions, as e.g. FParsec does. (I guess an easier way to say it is: imagine if the signature of << didn't consist of purely type variables!)

While FsControl isn't my library, I'm open to suggestions of other ways of achieving the same idea, though using SRTP seems to be the most natural (and efficient) way of doing this.

[quant1729]

As I specified in my initial description, just open the FSharpPlus project, point editor to

https://github.com/gmpl/FSharpPlus/blob/master/FSharpPlus/Samples/Learn%20You%20a%20Haskell.fsx

in Visual Studio. F# Intellisense stops working normally, VS consumes CPU and memory uncontrollably, VS hangs and stops responding when requested to quit.

FsControl is not my library as well, but I totally agree with drvink's points. I think library's added value is huge.

[exercitusvir]

I also regularly run into this issue and I don't use FsControl. While I use custom code that does something similar to retroactively implement a function on existing types to get something similar to type classes (explicit member constraints on statically resolved type parameters that are fulfilled by a class with overloaded static members), I use this only sparingly when no other solution works, but that already makes tools like Visual F# Power Tools unusable.

I just like to point out that this is a serious issue that should be fixed. Another solution would be to make such approaches obsolete by giving us something like type classes or some other efficient construct that allows retroactive implementation of interfaces.

[gusty]

Hi all. I just found this discussion, may be I can add more information. Here's my experience developing and using FsControl.

When I started the project, compile times were fine, even with all 'crazy' abstractions like Arrows and Monad Transformers, a bit longer than usual but still acceptable.
It really started to slow down as I added more overloads for existing .NET types, specially (as latkin already noticed) when I added the KeyValuePair overloads. Here's a small reproduction of the issue as you can see the problem seems to be with overload resolution itself, my guess is that it slows down in presence of a type composed of 2 generic types as is the case of KeyValuePair<'a,'b> .
So right now it's pain to update FsControl with Visual Studio, I will add conditional compiler directives to take out those overloads when working on the project. Hopefully you can find a solution.
Why does FsControl uses overload? I can't find another compile time selection mechanism. It would be nice if static optimizations were available and not restricted to the FSharp Compiler itself.

Now using FsControl in another project is a different story. Once FsControl is compiled everything is OK, it will depend on how much you is used from the library, it will not slow down just because of the use of the generic map or the generic >>= operator and that's the way I'm using it at the moment in my applications.
For the time being, for those having problems using FsControl or F#+ in their applications I will be happy to help finding workarounds to reduce their compile time. May be we can create a minimal version of FsControl without all those overloads which are not very frequently used but slow down compilation a lot.

[smoothdeveloper]

@dsyme, I was playing with help of @drvink around using SRTP to have static compile time resolution without resorting to OO and overloads or plenty of names for function that does the same but different data types as input parameter.

I also encountered this example:

https://github.com/ctaggart/froto/blob/aeb4221d1b1bc9926b4a1181d174ebe135fb1e2b/Froto.Core.Test/ExampleProtoClass.fs#L44-49

Is that the type of thing that tend to currently make the type checker and all tooling to go slow? Is there a plan to address this specific usage of SRTP in a way which doesn't impact compile time and tooling? (which implementation in code can be elegant as @drvink showcased)

It seems to me like an important part for language evolution, with all static typing of CLR and type inference of F#, it is not ideal to have to state the type hydrateBool, hydrateString, etc. instead of just hydrate.

Is it what you perceive as an abuse or more like a current limitation which should eventually be addressed to push idiomatic F# code toward an even more elegant / maintainable state?

[smoothdeveloper]

Looking at ConstraintSolver.ResolveOverloading, despite I don't really understand the code, it seems that we keep doing calls to FilterEachThenUndo which does a linear search.

If we had a chance (requires someone who understands this code) to prepare a more efficient overload lookup structure to avoid linear search, this would shave significant amount of time.

Conceptually I'd imagine that if we had a hash based lookup on the types, this would become almost free while currently, the more possible "overloads" in the code, the compilation at each invocation will scan all the members in order (put most frequent first in the code :smile:).

[smoothdeveloper]

Debugging helps bring some insight,

let bestMethods =
    applicableMeths |> List.choose (fun candidate -> 
    if applicableMeths |> List.forall (fun other -> 
         candidate === other || // REVIEW: change this needless use of pointer equality to be an index comparison
         let res = better candidate other
         //eprintfn "\n-------\nCandidate: %s\nOther: %s\nResult: %d\n" (NicePrint.stringOfMethInfo amap m denv (fst candidate).Method) (NicePrint.stringOfMethInfo amap m denv (fst other).Method) res
         res > 0) then 
       Some(candidate)
    else 
       None)

I gather this becomes expensive, and we don't seem to cache the resolution.

Would it make sense for the compiler to keep a cache of "given those types of arguments and return type, for this SRTP function call, give me resolved overloading if already resolved"?

We would pay the full price when calling with an unseen type (but once) and / or eventually resolving to an error (which anyways ends the compilation).

The issue with this approach is that we don't really know when to purge the cache (it could grow infinitely during a compilation), but maybe having such cache per file is a suitable approach?

• Is there "prior art" for this kind of behaviour with the compiler?
• Is it something which we can consider?

[smoothdeveloper]

Also, it seems strange to have an n² iteration over applicableMeths despite forall might eagerly return false early when better returns 0 (which as far as can I understand happens a lot but still).

It would be great to have insight from someone familiar with this type of overload resolution and confirm if we can tackle the issue with another approach (but keeping the better scoring logic in place) and maybe rely on some caching to not perform same resolution over and over again during the course of the whole compilation.

[smoothdeveloper]

Should applicableMeths should first be pruned from all that have a 0 compare value resulting from better?

[gusty]

@smoothdeveloper It would be really nice to improve the overload resolution.
I wish I had more time to have a look at the constraint solver, I'm sure there is room for improvement.
At the moment I can contribute with code to tests the compile time. Please tell me if you need.

[quant1729]

Gauthier, very interesting investigation. Thank you.

Kevin, Don, can you please look into this? It is more than a year passed since I submitted this bug.

[smoothdeveloper]

@gmpl / @quant1729 I don't think I can fix the main issue myself, but eager to experiment with this bestMethods resolution.

I'm also eager to know, first hand from people who knows that area, if a caching strategy would make sense (tricky obviously), and if not, what could be used to avoid linear lookup (leaving aside the potential n² issue).

I just tried to compile with this added line before we pipe applicableMeths to List.choose:

let applicableMeths = applicableMeths |> List.filter (better firstCandidate >> ((<>) 0))

and on code sample, this reduces the number of lookup iterations (for the so many happening) from 14 to 11 in many cases.

I have no idea if this is correct but this would feel intuitive, although to do that filter, we call N times better already).

I'll try to look more into it coming weekend.

[gusty]

@smoothdeveloper where is firstCandidate defined? I can't see it anywhere in the code.

[smoothdeveloper]

@gmpl, I defined it taking the first element of applicableMeths.

let firstCandidate = applicableMeths |> List.head

[gusty]

Thanks.
I think you're looking at the wrong place here.
Your assumption that you have n² iteration over applicableMeths seems wrong to me. It does return eagerly. The other iterations you see come from other calls to ResolveOverloading and that's where we should focus on.
Why does the compiler makes so many calls to ResolveOverloading most of these times with the same list of methods?
I'm testing with code based on the reproduction example (first link in this discussion) and it calls 7 times ResolveOverloading for this tupled method resolution, but for this KeyValuePair version it calls 229 times !
I understand that tuples are baked into the compiler so it's normal to process them faster, but 229 times seems totally wrong, or am I missing something?
My impression is that the compiler is doing the same check many times.

[smoothdeveloper]

@gmpl yes you are right, that was mostly my first attempt at stepping / changing the code (printing counters) to see effect (which was minimal), looking at call sites and logic to ResolveOverloading might highlight more important issue.

[gusty]

Btw @dsyme while writing the code for FsControl I've found tons of compiler bugs (a few of them are partially documented and labeled as F# compiler bugs) mostly related to overload resolution in presence of static constraints. That area in general seems to be very buggy and have the impression that it was never tested. I guess it's because you don't consider it an important language feature but if you're interested I can report them, I will have to find a small repro for each one but wanted to check first if you will be interested.

[forki]

Please report all errors. How would we ever fix them if they are not
reported?
On Jun 25, 2016 8:21 AM, "Gusty" [email protected] wrote:

Btw @dsyme https://github.com/dsyme while writing the code for
FsControl I've found tons of compiler bugs (a few of them are partially
documented and labeled as F# compiler bugs
https://github.com/gmpl/FsControl/issues?utf8=%E2%9C%93&q=is%3Aissue%20label%3A%22F%23%20Compiler%20Bug%22%20)
mostly related to overload resolution in presence of static constraints.
That area in general seems to be very buggy and have the impression that
was never well tested. I guess it's because you don't consider it an
important language feature but if you're interested I can report them, I
will have to find a small repro for each one but wanted to check first if
you will be interested.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/Microsoft/visualfsharp/issues/343#issuecomment-228514906,
or mute the thread
https://github.com/notifications/unsubscribe/AADgNHflXwn3MwHs9mJG-CvaxJxcHO3mks5qPMjjgaJpZM4D5eOZ
.

[gusty]

As said, I wanted to check first if there is interest, because it will take me some time create small repros, accurate reports and as said before my impression over these years was that there was no general interest in exploring this area but this discussion makes me think that may be now there are some F# users interested. Perhaps I can even provide some fixes but the same applies if later those PR get never merged.
Thanks @forki for your feedback.

[forki]

Why would compiler fixes not be merged? That would make no sense.
On Jun 25, 2016 9:13 AM, "Gusty" [email protected] wrote:

As said, I wanted to check first if there is interest, because it will
take me some time create small repros, accurate reports and as said before
my impression over these years was that there was no general interest in
exploring this area but this discussion makes me think that may be now
there are some F# users interested. Perhaps I can even provide some fixes
but the same applies if later those PR get never merged.
Thanks @forki https://github.com/forki for your feedback.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/Microsoft/visualfsharp/issues/343#issuecomment-228518411,
or mute the thread
https://github.com/notifications/unsubscribe/AADgNPsWRdx7-RgnHKHV88bR71vgjmONks5qPNUugaJpZM4D5eOZ
.

[cartermp]

@gmpl There's definitely interest in fixing bugs. File as many as you can find! Sometimes PRs take a few days to make it in, sometimes they take a long time to make it in - that can just be the nature of things. But it's our intention to merge PRs and fix bugs, even if they take a long time to make it through.

[gusty]

Thanks @cartermp and @forki for your feedback I will review all the bugs I faced and report them, then if I can find a fix will submit a PR, otherwise I hope one day you will review the whole Constraint Solver, I have the feeling that it needs some redesign for the main backtracking process.

[dsyme]

@gmpl I will close this as I believe it is addressed by your PRs