{"id":48610,"date":"2023-11-02T10:05:00","date_gmt":"2023-11-02T17:05:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/dotnet\/?p=48610"},"modified":"2024-07-22T09:42:42","modified_gmt":"2024-07-22T16:42:42","slug":"a-new-fsharp-compiler-feature-graphbased-typechecking","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/a-new-fsharp-compiler-feature-graphbased-typechecking\/","title":{"rendered":"A new F# compiler feature: graph-based type-checking"},"content":{"rendered":"

This is a guest blog post by Florian Verdonck<\/strong>. Florian is a freelance software craftsman. He does consultancy, training and open-source development. Currently, he is very active in the F# community, working on the compiler and tooling, improving the overall state of the F# ecosystem according to the needs of his customers. Florian is a member of the open-source division at G-Research<\/a> and a maintainer of the open-source F# formatter project Fantomas<\/a>.<\/p><\/blockquote>\n

Currently, when you build a project using dotnet build<\/code> (and, by extension, when you invoke the compiler dotnet fsc.dll <arguments><\/code> via MSBuild), the compilation of your project will type-check each file sequentially. Type-checking is typically one of the most time consuming phases of the compilation. Introducing some parallelization could significantly speed things up. Accelerating large data processing jobs is something of great interest to the G-Research OSS team.<\/p>\n

Background<\/h2>\n

Last year, I revived an existing experiment<\/a> from Will Smith<\/a> to type-check implementation files (backed by a signature file) in parallel. This was a good learning experience on how type-check orchestration works, what types like TcState<\/code> and TcEnv<\/code> are, and other internal compiler details.<\/p>\n

At the time I was happy that the --test:ParallelCheckingWithSignatureFilesOn<\/code> landed (see dotnet\/fsharp#13737<\/a>), but I understood that this was only beneficial under a set of limited circumstances. The biggest drawback was that it only would work when you had signature files<\/a>. Files without a matching signature file would still be processed sequentially.<\/p>\n

I actually like signature files, I know some people will forever reject them, but for me, well, they grew on me. And I believe they have a role to play in larger F# (enterprise) projects. Signature files allow you to hide the implementation details of a file and are in fact a summary of what the project needs to know about your implementation. On a practical level, you never have to use the private<\/code> keyword anymore in your implementation, as functions will be private by default if they don’t get listed in the signature file.<\/p>\n

I love having a well-documented signature file that covers everything I need to know about a 3,000 line implementation file. This is particularly beneficial in an enterprise where people come and go and the living code serves as documentation. Signature files force you to think more explicitly about the boundaries between your software. If you need to edit your signature file, it will raise immediate awareness that you might be changing your public API surface.<\/p>\n

The downside of signature files are that you need to do double bookkeeping. Adding or modifying any public details in an implementation file will require you to change code in two places. There is not much IDE tooling (regardless of what your current editor is) at the time of writing this, and that might be frustrating.<\/p>\n

Basic concept<\/h2>\n

The new feature flag --test:GraphBasedChecking<\/code> will try to type-check any file in parallel on multiple threads, regardless if it is backed by a signature file. In order to know which files can be processed in parallel, we first need to discover the relationship between each file in a project. The current relationship is determined by the file order in the project. Right now, each file has the type-checked information of all the files that came before it.<\/p>\n

In practice, however, this isn’t really always a strict requirement to type-check the current file. For example, inside a unit test project, your individual test files are likely independent. Or in other projects, you might have some features that just don’t depend on each other. So, based on what you do inside your project, there might be some room for parallelization.<\/p>\n

To discover the dependency graph between files, we can process the Untyped Abstract Syntax Tree<\/code> (AST) to detect links. Because the information inside the AST isn’t as rich as the typed tree, we know that our resolution will be a super-set of the actual dependency graph. Using the typed tree, we could construct the true dependency graph, but we would only have that information after everything is type-checked. Which is the very thing we are trying to improve.<\/p>\n

To construct our dependency graph, we will process each file twice. Once to create a trie<\/a> structure that maps all the found namespaces and modules in the project. And the second time to detect any potential links to other files in the trie. You can read more details on the algorithm in the documentation<\/a>.<\/p>\n

This might sound abstract and is slightly easier to grasp by looking at an example. Imagine the following project:<\/p>\n

A.fs:<\/p>\n

module Project.A\r\n\r\nopen System\r\n\r\nlet add x y = x + y<\/code><\/pre>\n
B.fs:<\/p>\n
module Project.B\r\n\r\nopen Project.A\r\n\r\nlet b = add 1 2<\/code><\/pre>\n
This will lead to the following trie:<\/p>\n
\"the<\/p>\n
Every trie will always have a root node. We used this node to capture files that will automatically be linked. Think of scenarios like global namespace<\/code> or a top-level module without any prefix [<AutoOpen>] module X<\/code>.<\/p>\n
The first child node is the Project<\/code> namespace node. Both files are using this namespace because the module is prefixed by it. However, we make a distinction between files that use a namespace and files that expose types into a namespace. More on that later.<\/p>\n
The child nodes A<\/code> and B<\/code> are self-explanatory. A module can only contain one file as a dependency because it can technically only be specified once.<\/p>\n
After constructing the trie, we will process files A and B again but this time we will look at the content. As A.fs<\/code> is the first file in a project, we will skip the second processing as it cannot have any dependencies being the first file.<\/p>\n
For the file B.fs<\/code> we will look at nodes of interest in the AST and use them to query the trie. If we find a matching node for our query, we will consider adding files in that node as dependency for the current file. In our example, we will process open Project.A<\/code> from the AST and query for [\"Project\".\"A\"]<\/code>. The resulting node will be the module node of ‘A’ which contains A.fs<\/code>. And we conclude the following graph:<\/p>\n
\"the<\/p>\n
We need to take a lot of details into account when processing the contents of a file. I won’t cover all of them in this blog post, but I’d like to give one more example:<\/p>\n
A.fs:<\/p>\n
namespace Foo\r\n\r\ntype A =\r\n    {\r\n        Age: int\r\n        Name: string\r\n    }<\/code><\/pre>\n
B.fs:<\/p>\n
module Foo.B\r\n\r\nlet x y z = y.Age - z.Age<\/code><\/pre>\n
Our trie would look like:<\/p>\n
\"the<\/p>\n
And when we process B.fs<\/code> (again, we don’t need to process A.fs<\/code>), we need to take module Foo.B<\/code> into account. We query the trie for the prefix [\"Foo\"]<\/code> and will get the Foo<\/code> namespace node back.<\/p>\n
Because of the namespace prefix of our module, any types defined in Foo<\/code> are accessible to B.fs<\/code>. So we need to take a dependency on A.fs<\/code> in order for the code to compile. That is why we treat namespaces differently than modules. We don’t automatically want to link files because they share a namespace and we do want to link files when there are types in a namespace involved. This of course is a trade-off scenario, we could in theory be adding links between files, where in practice they are not required. Better safe than sorry, right?<\/p>\n
Getting started<\/h2>\n
To get started with this in your own code base, you will need to download the .NET 7.0.400<\/code> SDK. Make sure your global.json<\/code> is configured correctly!<\/p>\n
First, we need to tell the F# compiler that we wish to use this feature. We can do this by adding it to the OtherFlags<\/code> property in MSBuild.<\/p>\n
In your .fsproj<\/code> (or Directory.Build.props<\/code>) you can extend this property by adding <OtherFlags>$(OtherFlags) --test:GraphBasedChecking<\/OtherFlags><\/code>. This will append our new test flag to any existing flags that were already set.<\/p>\n
From there on, we can trigger a build using dotnet build<\/code> and may already notice a performance difference. This really depends from project to project and does require some tweaking to get the most out of it.<\/p>\n
Seeing the graph<\/h2>\n
In order to verify the resolved dependency graph, we can add another flag to export the graph as a Mermaid diagram<\/a>. Add --test:DumpCheckingGraph<\/code> to the OtherFlags<\/code> and rebuild. This will generate a .graph.md<\/code> file next to the output location of the project (the -o<\/code> flag), which is typically in obj\\Debug\\netXYZ<\/code>. This file is a mermaid diagram which we can visually inspect in an IDE (using a plugin) or via the website.<\/p>\n
Seeing the duration<\/h2>\n
The resolved graph will be processed in parallel, to a certain degree. We can only start type-checking a file once all its dependencies are available and thus we could have some bottleneck situations. To get a sense of which file took long to type-check we can use the open telemetry<\/a> from the compiler. Adding the --times:report.csv<\/code> flag to the OtherFlags<\/code> will generate a report with the duration of each activity.<\/p>\n
When we open this CSV<\/a> file, we can filter on CheckDeclarations.CheckOneImplFile<\/code> and sort by Duration(s)<\/code>. This will show us which files took the most time to type-check.<\/p>\n
CheckDeclarations.CheckOneImplFile,13-17-29.4512,13-17-29.5127,000.0615,00-c8782254ceb3813ae947bd7647dc0acb-3e0d008dcf461b26-00,00-c8782254ceb3813ae947bd7647dc0acb-5baad57327070a15-00,c8782254ceb3813ae947bd7647dc0acb,C:\\Users\\nojaf\\Projects\\graph-sample\\A.fs,,A,,,,,,,,,,\r\n\r\nCheckDeclarations.CheckOneImplFile,13-17-29.5131,13-17-29.5471,000.0340,00-c8782254ceb3813ae947bd7647dc0acb-101d02a6006605f7-00,00-c8782254ceb3813ae947bd7647dc0acb-5baad57327070a15-00,c8782254ceb3813ae947bd7647dc0acb,C:\\Users\\nojaf\\Projects\\graph-sample\\B.fs,,Foo.B,,,,,,,,,,<\/code><\/pre>\n
Restructure code to improve performance<\/h2>\n
As you can visually inspect the graph and the times, you might realize that some files contain too many links and could be good candidates for a split. As this feature is rather new, we are still trying to find some good heuristics or convenient ways to detect what change in your code structure will get you the most benefits from graph-checking.<\/p>\n
Here are a few more pointers when a file will always be linked to the ones that came after it:<\/p>\n