This document describes the idea and implementation details for parallel type-checking of independent files in the F# compiler.

Performance of F# compilation and code analysis is one of the concerns for big codebases.

Despite several recent improvements in this area, there is still appetite and potential for change.

It is going to be the main topic of this page.

But before we dive into the details of the proposal, let's first discuss how the things work at the moment.

One of the main phases of compilation is type-checking. Depending on the project in question, it can take as much as 50% of the total compilation time.

The same is true about code analysis (used by the IDEs), but to an even higher degree - since code analysis skips some of the expensive compilation phases, type-checking represents a bigger fraction of the total wall-clock time, hence any improvements in this area can lead to more drastic total time reduction.

There is a lot of information associated with type-checking individual files and groups of them.

Currently, due to the (mostly) sequential nature of the processing, it is sufficient to maintain a single instance of such information for the whole project.

This instance is incrementally built on as more and more files have been processed.

A recent [change](https://github.com/dotnet/fsharp/pull/13737) introduced in the compiler introduced a level of parallelism in type-checking.

It allows for parallel type-checking of all `.fs` files backed by `.fsi` files. Such `.fs` files by definition cannot be depended upon by any other files w.r.t. type-checking, since all the necessary information is exposed by the corresponding `.fsi` files.

Files in an F# project are ordered and processed from the top (first) and the bottom (last) file.

The compiler ensures that no information, including type information, flows upwards.

Consider the following list of files in a project:

By default, they are type-checked in the order of appearance: `[A.fs, B.fs, C.fs, D.fs]`

Let's define `allowed dependency` as follows:

The graph of dependencies between the files that the compiler _allows_ looks as follows:

Type-checking files in the appearance order guarantees that when processing a given file, any files it _might_ depend on w.r.t. type-checking have already been type-checked and their type information is available.

Let's define a `necessary dependency` too:

And finally a `dependency graph` as follows:

A few slightly imprecise/vague statements about all the graphs:

1. The _Necessary dependencies_ graph is a subgraph of the _allowed dependencies_ graph.

2. If there is no path between 'B.fs' and 'C.fs' in the _necessary dependencies_ graph, they can be type-checked in parallel, as long as there is a way to maintain and merge more than one instance of type-checking information.

3. Type-checking _must_ process files in an order that is compatible with the topological order in the _necessary dependencies_ graph.

4. If using a dependency graph as an ordering mechanism for (parallel) type-checking, the closer it is to the _necessary dependencies_ graph, the higher parallelism is possible.

5. Type-checking files in appearance order is equivalent to using the `allowed dependencies` graph for ordering.

6. Removing an edge from a _dependency_ graph _can_ increase (but not decrease) the level of parallelism possible and improve wall-clock time.

Let's look at point `5.` in detail.