Parallel type checking

[kerams]

The recent awesome work on parallel parsing and IL gen got me thinking whether it would be feasible to parallelize type checking as well.

Given F#'s significant file order, if the compiler can quickly establish that file B can't possibly reference anything in file A declared directly above it, can't A and B be typechecked (and optimized) simultaneously? This would require an initial traversal of the AST in every file in order to create a file dependency graph. Specifically, things like this need to be checked:

• If B opens a module or class defined in A, B depends on A
• If A contains an AutoOpen that has immediate effect in B (because of overlapping namespaces, regardless of actual contents), B depends on A
• If B references something from A using a qualified name, B depends on A

I think these can be gleaned from the untyped syntax tree alone, the question is whether it would be fast enough to offset the overhead and whether typechecking has a significant cost. Apologies in advance if there's a gaping flaw in here somewhere :).

[smoothdeveloper]

@kerams, would you mind paying a look at the recent comments I made in the broader/fuzzy discussion for incremental recompile (#8044)?

What I touch on my comments in #8044 is targeted at identifying if a file and a diff of signatures before it should engender a recompile of the file.

The same approach could be taken earlier, it could be on diff of AST that we could already identify opportunities to skip recompile of a file, or more likely, proceed in checking the next stage.

Why is it related to incremental recompilation?

Because incremental recompilation will require serialisation and heuristics on the serialized graphs, and making things like a graph and serialised, means they can conceptually be parallelised for read only usage 🙂 (I know I'm stretching everything a little bit).

Now, regarding your more precise issue, I have few things coming to mind:

Are you familiar with the NameResolution business? if there was a way to populate those after AST parsing, and do the checks that you are looking for, and serialise the outcome, it would benefit both some of the rough ideas I explore for incremental recompilation and as you say, gets us closer to the ability to type check in parallel, according to your more precise plot (the F# world domination, errr, compilation plan, I presume).

If NameResolution as we know (but me) is not good enough (because needs a first pass of type checking, or parsing of references), we could maybe have a lower one, that still targets few use cases for your parallel type checking graph splitter endeavours.

That would be the beginning of a NameResolution that enrich at each stages:

• AST
• assembly reference loading
• later type checking
• codegen (not sure if relevant, but maybe for relinking, in context of type provider SDK...)

It means invalidation of the serialised NameResolutions could be fine grained in terms of which context it impacts.

One big pitfall, at least, nest of edge cases, is shadowing and aliasing features of the language, and also stuff like AutoOpen and open static.

It sounds like "after assembly reference resolution" maybe the next stage if bare AST can't help much in sorting out what you are pointing at.

edit:

Apologies in advance if there's a gaping flaw in here somewhere :)

Don't worry, you are covered at least 10x by all mine :)

[TIHan]

We have a PR that could enable this: #11152

The restriction is that it will only parallelize type checking impl files that have a backing signature file. Our hope in the future is that we will add better tooling to create these signature files automatically through a gesture in an editor.

Trying to parallelize type checking for impl files without sig files is a much more difficult undertaking. Sure, you could add heuristics like you suggested, but we would have to have a dependency graph of types and functions; which may be more expensive in of itself.

[kerams]

Yes, I'm specifically talking about no sig scenarios.

a dependency graph of types and functions;

Yes, that would be expensive. I was thinking keeping track of namespaces and modules alone could theoretically suffice. For instance, if we collect those for file A and see a related open in B, we can't parallelize. It does not matter what exactly is used (or if the open is indeed redundant). This heuristic would only guarantee what definitely isn't used, and would because of this specificity hopefully run very fast.

@smoothdeveloper, I'm afraid I don't know enough about those topics, or whether your approach, if viable, would supersede mine (perhaps they could even complement each other). My evening thoughts were very narrowly concerned about full compilation performance.

[kerams]

Here's a really silly idea. If I extract all namespaces and top level modules (a very shallow AST traversal would be enough) from file A and do a full text search for them in file B, will I not be perfectly sure that the files are independent if there are no hits (other than perhaps a shared top level namespace)? :)))))

I'll answer myself. The aforementioned auto opens would cause a problem, but that can be easily checked separately. Partially qualified opens are worse though.

[smoothdeveloper]

It seems to me like a great bang for buck first pass at splitting out stuff just at the AST level, like having both a genius and captain obvious being one and single person bringing this :D

I'm curious what roadblocks would be hit by this heuristics to turn faulty in the wild.

@vasily-kirichenko, any opinion?

[cartermp]

Will move this to a discussion

[safesparrow]

To me this also seems to have a massive potential for speedup.

I raised a similar 'idea' recently: #13733 .

Trying to parallelize type checking for impl files without sig files is a much more difficult undertaking. Sure, you could add heuristics like you suggested, but we would have to have a dependency graph of types and functions; which may be more expensive in of itself.

I do think there are plenty of heuristics, either text-based or AST-based, that would be both quick and give a decent rate of true negatives.

A simple thing that the user can do to help with performance would be putting individual files in separate modules/namespaces (so that .
While this is not ideal and is not a nice trade-off for public APIs, in many internal code areas it's a much lower cost to pay than asking the user to maintain FSI files, and it can bring much more benefit (I think).

Another thing is that this wouldn't have to be limited to type-checking and could apply to next phases of code analysis/compilation. I don't have a good picture of how the compilation is structured, but in principle things like optimisation, constraint solving etc. could be parallelisable if two files in question don't depend on each other at all.

@smoothdeveloper @kerams I think we should discuss some ideas further.

[kerams]

So here's a rough outline of how establishing whether file B depends on file A could work:

• Use AST walker to gather all types and values declared in file A
• Use AST walker to gather all identifiers used in file B
• Check if there is any overlap (completely ignoring modules)

This is extremely simple and could yield a bunch of false positives, but, correct me if I am wrong, no false negatives.

Then we can proceed to fine tune the algorithm to whittle the false positives by introducing some more improvements and complex checks:

• If file B opens a module that exists in File A, considered them dependent and skip walking the AST of file B to get all identifiers (this will give false positives with unused opens - perhaps we could live with that?) (because of type inference we have to assume all opened modules are used)
• Take modules into account
  • Add visible auto-open modules from file A to our list of opened modules in file B
  • Filter out all identifiers in file B that refer to local types or values - not sure how complex this would be, it does not seem far from actual type checking
  • For every opened module and identifier combination in file B, see if there's is an overlap with qualified types and values in file A
• Transitivity
  • If there's a file C and we have decided that B depends on A, check if C depends on B first. If it does, there's no point in checking C with A.

[safesparrow]

Use AST walker to gather all identifiers used in file B

I don't think this works. B can use type inference to depend on types from A without mentioning their names.
That's been mentioned in #13733 (comment)

As I understand type inference requires a module to be open for it to infer types from that module.

So I think the best we can do is detect whether B opens any modules from A.

[kerams]

You still need to check identifiers since you can use fully qualified names without opening any modules.

[safesparrow]

You still need to check identifiers since you can use fully qualified names without opening any modules.

Yeah, sorry, forgot about that for a moment.

Anyway: others claim such a limitation would give a low true positive rate.
I don't think I agree. Plus as mentioned it can be 'artificially' helped by putting symbols in more fine-grained modules (not perfect, but maybe a decent trade-off).

I think we should:

1. verify how easy it would be to do the parallelisation once the heuristic is in place
2. verify whether the AST approach for the heuristic is feasible
3. verify how costly it is relative to the things that it can parallelise
4. use example codebases to assess how often the heuristic would kick in
5. assess how much could be gained in those codebases by putting all/most of unrelated code in separate modules

For 4. and 5. some analysis tooling would probably be needed.

[safesparrow]

@kerams What do you think about the above? Would you have some time yourself to try some of these steps?

[nojaf]

Hello,

I'd like to pitch a related idea here.
In the case of unit test projects, you typically have a couple of files here the file order matters and then a bunch of test files where in that group, the exact order of the files does not really matter.

Sample layout:

Helper1.fs
Helper2.fs
Helper3.fs
TestFile1.fs
TestFile2.fs
TestFile3.fs
TestFile4.fs
TestFile5.fs
TestFile6.fs
TestFile7.fs
TestFile8.fs
TestFile9.fs
TestFile10.fs
TestFile11.fs
TestFile12.fs
TestFile13.fs
TestFile14.fs
TestFile15.fs
TestFile16.fs
TestFile17.fs
TestFile18.fs
TestFile19.fs
TestFile20.fs

Every TestFile file needs to know about the Helpers but you could change the order of the test files and the result would be the same.

The compiler could type-check these files in parallel if you know this (because the user specified it).
I've made a raw proof of concept PR for this: #14104

It is very hard coded, and I don't really know yet how to expose this feature-wise.
But I did get positive results for this when testing compilation only for the Fantomas.Core.Tests project (which has about 110 test files):

Normal compiler:
3.250
3.162
2.965
3.246
3.104

Average: 3.1454

PR compiler:
1.580
1.704
1.725
1.628
1.776

Average: 1.6826

+= 45% faster

There is no clever heuristic here, but I believe the use case is common enough to explore this.

I believe the same magic number trick could be used for enablePartialTypeChecking.

Any initial thoughts on this @dsyme and @vzarytovskii?

//cc @safesparrow

[vzarytovskii]

I was wondering whether an equivalent of reference assemblies on file level (maintained automatically by the compiler) could be used to remove the need for signature files in parallel type checking.

One of the problems with it - is figuring out how to keep them up to date efficiently. To "prove" they're up to date you will need to typecheck the whole tree branch they depend on.

In case of FSI files, we just assume, that they are source of truth, and use them pretty much as typecheck results, if they don't match, we produce typecheck errors.

One thing you can do is assume the same, but in case of first typecheck error - recalculate the whole subtree and cache again.

[kerams]

Maybe just a file hash?

But yes, it would not be trivial.

Have the compiler compute hidden fsi files and check their validity based on file hashes and if they match, reuse the existing type checking parallelization, or go further and somehow serialize typed trees?

[vzarytovskii]

Maybe just a file hash?

But yes, it would not be trivial.

Yeah, worth tinkering with it. If we can leverage signature cache without user thinking about it, it would be great.

[baronfel]

A common real-world case for this kind of arrangement would be database migrations. In a typical scenario they might be arranged like:

migrations
\ Common.fs // common utilities used in migrations  
  0001_CreateDatabase.fs
  0002_AddNewTableType.fs
  0003_AddNewColumnToExistingTable.fs
  ... and so on

And inside a project file a user might do something like this for convenience, since they know that all migrations are logically independent and naturally ordered:

<Compile Include="migrations\Common.fs" />
<Compile Include="migrations\*.fs" Exclude="MIgrations\Common.fs" />

to provide this semantic. It would be nice to be able to push this information to the compiler somehow.

[safesparrow]

For a solution without user input, I think that heuristic-based approach could go a long way. If a given file is in an independent module and doesn't open any modules from another file, it can be compiled independently. Then the only thing the user can do to help the heuristic if not done already, is putting independent pieces of code in separate nested modules. My claim is that's much less intrusive than having to introduce and maintain fsi files.

Hopefully something like this could be utilised in both compilation and code analysis, but as I understand it's quite a bit easier to do in the compiler for now.

Regarding checking fs-fsi match, as I understand a change to any file that these files depend on can affect the (mis)match.

[safesparrow]

FYI @kerams I mentioned some work I'm doing on implementing a parallelisation mechanism like this, based on AST information, in #14104