BackgroundCompiler.ParseAndCheckProjectImpl takes a very long time on a big solution with a very connected project dependency graph

[oliviermatz]

I tried to use the "Find all references" feature of F# power tools on a big solution. In certain cases, the analysis would was very slow (I did not measure how slow, I killed devenv.exe after one hour). A quick profiling showed that the FSharp.Compiler.Service spent all its time running IncrementalBuilder.GetLogicalTimeStampForProject. I then tried to reproduce the degenerative behaviour on a simple example and came up with this.

• A simple solution with 4 projects A, B, C and D.
• B references A
• C references A and B
• D references A, B, and C

Using F# powertools, finding all references on a type defined in A results in :

• 53 calls of GetLogicalTimeStampForProject on the project A
• 21 calls of GetLogicalTimeStampForProject on the project B
• 7 calls of GetLogicalTimeStampForProject on the project C

I understand that the logical timestamp of a project is computed from the last modified timestamp on all of its files, and recursively from the logical timestamp of all the projects it references. So I believe we're faced with an algorithm that is doing IO with exponential complexity.

In my opinion, simply memoizing the logical timestamps of projects during the computation should solve the problem. I may get enough time in the next weeks to try to do it myself but I thought I would share my analysis in the mean time.

[vasily-kirichenko]

I think this is the same issue as in fsprojects-archive/zzarchive-VisualFSharpPowerTools#1280

[dsyme]

@vasily-kirichenko @matzoliv Can you verify if #550 has reduced the calls to GetLogicalTimeStampForProject? Thanks

@vasily-kirichenko I'm not sure this is the same as fsprojects-archive/zzarchive-VisualFSharpPowerTools#1280 but perhaps it is

[dsyme]

Fix is in 2.0.0.8

[vasily-kirichenko]

I does not seem to make any significant change. Moving the cursor from one symbol to another causes ~1200 file accesses (VFPT solution). SafeExists and GetLastWriteTimeShim are always at the top in profiler:

That said, the performance is adequate for editing small to middle size files and awful for "Find all references" on large solutions.

[dsyme]

@matzoliv @vasily-kirichenko The main thing I want to check is that the exponential behaviour is gone. It's possible there is still another path causing an exponential or quadratic number of checks. It's not necessarily going to solve any specific end-user performance problems on large solutions, but it's not going to hurt :)

@matzoliv If you could add a repro solution along the lines of the one you described above that would be great, with a download link and exact repro steps