ItemKeyStore construction performance concern

[TIHan]

I've been closely looking at the performance of the building of an ItemKeyStore that is used to dramatically lower the memory usage from storing symbol identity information for find all references. We build an ItemKeyStore every-time a background type-check happens. A background type-check occurs on a file when another file dependent on it is being type-checked, so it's not the editing document necessarily.

Some results on FSharp.Compiler.Private:

**FileName                     | TypeCheck Time       | ItemKeyStore Construction Time**
TypeChecker.fs                 | 2325ms               | 202ms
Optimizer.fs                   | 426ms                | 31ms
InnerLambdasToTopLevelFuncs.fs | 142ms                | 13ms
IlxGen.fs                      | 1014ms               | 82ms
SymbolPatterns.fs              | 29ms                 | 7ms

So, there is some clear performance cost. I don't know how noticeable this is, but I think it is. The trade-off is the memory reduction we gained, and the performance increase when doing a find all refs.

There is some GC cost and sometimes we do allocate on the LOH for semantic classification storage. This isn't a regression per-se, since we were allocating on the LOH for in-memory symbol storage before the ItemKeyStore changes.

We can address this in a number of ways:

• Lazy evaluation of background semantic classification and item key store.

  • This is most preferable but with the way incremental builder is designed, this makes it challenging. It is possible though.

• Make construction time faster and allocate less (remove LOH allocations)

  • We should do this anyway, but it could be possible to minimize the time enough to where we don't have to rely on lazy evaluation - but not sure if that's possible yet.
  • Make semantic classification be stored in a memory-mapped file like the item keys.

[abelbraaksma]

I don't know how noticeable this is, but I think it is.

Depending on the file I'm editing, waiting for the types of arguments or variables can easily take 20s in my project. Not sure it's related, but if it is, any improvement in performance in that area may have a big impact.

Most notably, type inference is slow if the file is large (4k lines or more) and primarily has let bindings in modules (i.e. static type resolution).

And something I noticed recently is that if SRTP is involved and has dual type resolution dependency on a method (as with binary operators), and there are a lot of candidates, then it can completely block the IDE for minutes if no candidate is found (exponential time complexity, it seems). I've yet to come up with a small repro of that, though. Again, not sure it's in any way related with this report, though.

[cartermp]

@abelbraaksma I doubt this would be related to the issue, unless this is a recent (VS 16.6 preview) occurrence. The change that @TIHan is talking about applies a small CPU time cost to typechecking, though this does remove significant other CPU time spent as a result of extremely high memory usage

[abelbraaksma]

@cartermp, the high memory usage is something I see several times a day, which I typically resolve by closing tabs and then restarting the ide (just closing tabs with large files isn't enough, that's probably the LOH @TIHan was talking about).

While not directly related, it may definitely have a positive impact in the scenarios I work with.

And no, I didn't mean anything recent or preview related. Most likely it's been like that forever, I just never before managed to pin completely unresponsive ide issues to a specific set of actions (compiling went from 30s to 3 min over a few keystrokes, and only then showed the error related to SRTP, I hope to create a small enough repro soon).

[cartermp]

@abelbraaksma Good to know! We expect some things to continue to improve when VS 16.6 releases, which will include the changes that make Find Refs and Rename significantly cheaper and more responsive. I've noticed that things have felt considerably snappier in the F# codebase with these changes in.

[TIHan]

Just realized that this PR: #10199 - should address this issue.
It implements what I said in the description:

Lazy evaluation of background semantic classification and item key store.
This is most preferable but with the way incremental builder is designed, this makes it challenging. It is possible though.