https://devblogs.microsoft.com/dotnet/a-new-fsharp-compiler-feature-graphbased-typechecking/ Skip to main content [RE1Mu3b] Microsoft .NET Blog .NET Blog .NET Blog * Home * DevBlogs * Developer + Visual Studio + Visual Studio Code + Visual Studio for Mac + DevOps + Windows Developer + Developer support + ISE Developer + Engineering@Microsoft + Azure SDK + IoT + Command Line + Perf and Diagnostics + Dr. International + Notification Hubs + Math in Office + React Native * Technology + DirectX + PIX + Semantic Kernel + SurfaceDuo + Startups + Sustainable Engineering + Windows AI Platform * Languages + C++ + C# + F# + Visual Basic + TypeScript + PowerShell Community + PowerShell Team + Python + Q# + JavaScript + Java + Java Blog in Chinese * .NET + All .NET posts + .NET MAUI + ASP.NET Core + Blazor + Entity Framework + ML.NET + NuGet + Servicing + Xamarin + .NET Blog in Chinese * Platform Development + #ifdef Windows + Azure Depth Platform + Azure Government + Azure VM Runtime Team + Bing Dev Center + Microsoft Edge Dev + Microsoft Azure + Microsoft 365 Developer + Microsoft Entra Identity Developer Blog + Old New Thing + Power Platform + Windows MIDI and Music dev + Windows Search Platform * Data Development + Azure Cosmos DB + Azure Data Studio + Azure SQL Database + OData + Revolutions R + SQL Server Data Tools * More [ ] Search Search * No results Cancel .NET Conf 2023 The biggest .NET virtual event is back, November 14-16! Save The Date Close A new F# compiler feature: graph-based type-checking [png] Florian Verdonck November 2nd, 20232 1 This is a guest blog post by Florian Verdonck. 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 and a maintainer of the open-source F# formatter project Fantomas. Currently, when you build a project using dotnet build (and, by extension, when you invoke the compiler dotnet fsc.dll 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. Background Last year, I revived an existing experiment from Will Smith 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 and TcEnv are, and other internal compiler details. At the time I was happy that the --test:ParallelCheckingWithSignatureFilesOn landed (see dotnet/fsharp #13737), 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. Files without a matching signature file would still be processed sequentially. 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 keyword anymore in your implementation, as functions will be private by default if they don't get listed in the signature file. 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. 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. Basic concept The new feature flag --test:GraphBasedChecking 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. 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. To discover the dependency graph between files, we can process the Untyped Abstract Syntax Tree (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. To construct our dependency graph, we will process each file twice. Once to create a trie 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. This might sound abstract and is slightly easier to grasp by looking at an example. Imagine the following project: A.fs: module Project.A open System let add x y = x + y B.fs: module Project.B open Project.A let b = add 1 2 This will lead to the following trie: the resulting trie 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 or a top-level module without any prefix [] module X. The first child node is the Project 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. The child nodes A and B are self-explanatory. A module can only contain one file as a dependency because it can technically only be specified once. After constructing the trie, we will process files A and B again but this time we will look at the content. As A.fs is the first file in a project, we will skip the second processing as it cannot have any dependencies being the first file. For the file B.fs 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 from the AST and query for ["Project"."A"]. The resulting node will be the module node of 'A' which contains A.fs. And we conclude the following graph: the resulting trie 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: A.fs: namespace Foo type A = { Age: int Name: string } B.fs: module Foo.B let x y z = y.Age - z.Age Our trie would look like: the resulting trie And when we process B.fs (again, we don't need to process A.fs), we need to take module Foo.B into account. We query the trie for the prefix ["Foo"] and will get the Foo namespace node back. Because of the namespace prefix of our module, any types defined in Foo are accessible to B.fs. So we need to take a dependency on A.fs 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? Getting started To get started with this in your own code base, you will need to download the .NET 7.0.400 SDK. Make sure your global.json is configured correctly! 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 property in MSBuild. In your .fsproj (or Directory.Build.props) you can extend this property by adding $(OtherFlags) --test:GraphBasedChecking. This will append our new test flag to any existing flags that were already set. From there on, we can trigger a build using dotnet build 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. Seeing the graph In order to verify the resolved dependency graph, we can add another flag to export the graph as a Mermaid diagram. Add --test:DumpCheckingGraph to the OtherFlags and rebuild. This will generate a .graph.md file next to the output location of the project (the -o flag), which is typically in obj\Debug\netXYZ. This file is a mermaid diagram which we can visually inspect in an IDE (using a plugin) or via the website. Seeing the duration 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 from the compiler. Adding the --times:report.csv flag to the OtherFlags will generate a report with the duration of each activity. When we open this CSV file, we can filter on CheckDeclarations.CheckOneImplFile and sort by Duration(s). This will show us which files took the most time to type-check. 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,,,,,,,,,, CheckDeclarations.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,,,,,,,,,, Restructure code to improve performance 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. Here are a few more pointers when a file will always be linked to the ones that came after it: * Having a type in a namespace will link the file to each file that comes after and uses that same namespace. A.fs: namespace Foo type X = int Every file that contains Foo in the namespace or module will get a link to A.fs because of potential type inference. This isn't a bad thing, just keep in mind that using A.fs would require a large nested module and it could be a bottleneck while the graph is being processed. namespace Foo type X = int module Bar = // Imagine a super long module... begin end * Using a global namespace in your file also links it to everything that came after. If you have this, perhaps you want to move this file further down the project to avoid some links. * A non-prefixed [] module will also link to everything that came after it [] module Foo // ... Accelerating graph processing with signature files Signature files can be very useful to speed up the processing of the graph. When an implementation file is backed by a signature file, all links will point to the signature. The signature contains the same information and will always be a lot smaller to type-check. Thus, it can unblock the processing of dependent files a lot faster. Let's look at the example. A.fsi: module A val fn: int -> int A.fs: module A let fn (a:int) : int = // imagine a really long and complicated function to type check 0 B.fs: module B let process x y = A.fn x y Because of the signature, our graph will look like: the resulting trie And A.fs and B.fs can be type-checked in parallel. Generating signature files Using the F# compiler If you don't have any signature files in your current project, you can create them initially using the --allsigs compiler flag. Once you add it to your OtherFlags, it will create a matching signature file for each file in the project. Then you can add them accordingly to your project. Be aware though that --allsigs is something you typically want to enable once and remove afterwards. It would otherwise run during each build and always override any changes you may have made to your signature files. Using Telplin Alternatively, you could also create your signature files using the telplin .NET tool. Telplin has a different approach to generate the signature files and tries to be more faithful to the original source of the implementation file. IDE tooling Currently, no IDE has perfect tooling for working with signature files. So, I can sympathize if this makes you somewhat reluctant to start using signature files. Both --allsigs and Telplin only provide you with a starting point and are no solution for incremental changes. However, a lot of F# tooling is open source and your contributions are very welcome! Amplifying F Graph-based type-checking was one of the recent topics during Amplifying F#. Chet Husk guided us through the setup of the new compiler flag for FSAutocomplete and it was a very fun session. You can find the recording over the session page here. Acknowledgements G-Research took the lead on this feature and one can only imagine what F# could be if more companies were involved. I would particularly like to thank Janusz Wrobel (from G-Research) for exploring a first prototype of the idea and for teaming up with me to work on the implementation. Janusz and I spent hours discussing and working on this and it would have never landed without his drive to explore this idea. Next, I would like to thank the F# team at Microsoft for taking in our contribution into the code base. Just because you have an idea and PR for an open-source project doesn't mean that the maintainers necessarily get on board with it. So, I'm happy the team accepted our implementation and took the time to discuss its functionality in depth. This most likely was one of the hardest challenges we faced in the compiler code base, and I dearly appreciated all the help we got. Lastly, I would like to thank everyone who tested this feature on their code base ahead of the official .NET SDK release. I am so grateful for the early feedback that gave us a sense of whether this is working for all F# code. I very much implore you to test out this feature today! One day I hope we can turn on this feature by default, so please test this out on your code. Assert that the feature flag produces exactly the same binary! If this is not the case, open an issue on the F# repository with a sample to reproduce what isn't working for you. Thanks again for all those involved! [png] Florian Verdonck Open source developer Follow Posted in .NET F#Tagged compilers F# performance Read next Trying out MongoDB with EF Core using Testcontainers An introduction to the MongoDB database provider for EF Core, including use of Testcontainers [png]Arthur Vickers November 2, 2023 0 comment What's new with identity in .NET 8 An introduction to identity in .NET 8 with code examples to secure APIs, generate a Blazor-based UI and integrate authentication into Blazor WebAssembly apps. [png]Jeremy Likness November 3, 2023 4 comments 2 comments Leave a commentCancel reply Log in to join the discussion. * [png] Vladimir Shchur November 2, 2023 11:43 am 0 collapse this comment copy link to this comment Is it available in any 8.x sdk? Log in to Vote or Reply * [png] David N November 2, 2023 5:14 pm 0 collapse this comment copy link to this comment Fantastic work! I'll have to give this a try very soon. Log in to Vote or Reply .NET Feature Blogs * .NET MAUI * ASP.NET Core * Blazor * Entity Framework * ML.NET * NuGet * Xamarin Languages * C# * F# * Visual Basic Popular Topics * .NET Internals * .NET Servicing * Containers * Developer Stories * Performance Archive * November 2023 * October 2023 * September 2023 * August 2023 * July 2023 * June 2023 * May 2023 * April 2023 * March 2023 * February 2023 * January 2023 * December 2022 * November 2022 * October 2022 * September 2022 * August 2022 * July 2022 * June 2022 * May 2022 * April 2022 * March 2022 * February 2022 * January 2022 * December 2021 * November 2021 * October 2021 * September 2021 * August 2021 * July 2021 * June 2021 * May 2021 * April 2021 * March 2021 * February 2021 * January 2021 * December 2020 * November 2020 * October 2020 * September 2020 * August 2020 * July 2020 * June 2020 * May 2020 * April 2020 * March 2020 * February 2020 * January 2020 * December 2019 * November 2019 * October 2019 * September 2019 * August 2019 * July 2019 * June 2019 * May 2019 * April 2019 * March 2019 * February 2019 * January 2019 * December 2018 * November 2018 * October 2018 * September 2018 * August 2018 * July 2018 * June 2018 * May 2018 * April 2018 * March 2018 * February 2018 * January 2018 * December 2017 * November 2017 * October 2017 * September 2017 * August 2017 * July 2017 * June 2017 * May 2017 * April 2017 * March 2017 * February 2017 * January 2017 * December 2016 * November 2016 * October 2016 * September 2016 * August 2016 * July 2016 * June 2016 * May 2016 * April 2016 * March 2016 * February 2016 * January 2016 * December 2015 * November 2015 * October 2015 * September 2015 * August 2015 * July 2015 * June 2015 * May 2015 * April 2015 * March 2015 * February 2015 * January 2015 * December 2014 * November 2014 * October 2014 * September 2014 * August 2014 * July 2014 * June 2014 * May 2014 * April 2014 * March 2014 * February 2014 * January 2014 * December 2013 * November 2013 * October 2013 * September 2013 * August 2013 * July 2013 * June 2013 * May 2013 * April 2013 * March 2013 * February 2013 * January 2013 * December 2012 * November 2012 * October 2012 * September 2012 * August 2012 * July 2012 * June 2012 * May 2012 * April 2012 * March 2012 * February 2012 * January 2012 * October 2011 * September 2011 * August 2011 * June 2011 * April 2011 * March 2011 * February 2011 * January 2011 * December 2010 * November 2010 * October 2010 * September 2010 * August 2010 * July 2010 * June 2010 * May 2010 * April 2010 * March 2010 * February 2010 * December 2009 * November 2009 * October 2009 * September 2009 * August 2009 * July 2009 * June 2009 * May 2009 * April 2009 * March 2009 * February 2009 * January 2009 * December 2008 * November 2008 * October 2008 * September 2008 * August 2008 * July 2008 * June 2008 * May 2008 * April 2008 * March 2008 * February 2008 * January 2008 * December 2007 * November 2007 * October 2007 * September 2007 * August 2007 * July 2007 * June 2007 * May 2007 * April 2007 * March 2007 * February 2007 * January 2007 * December 2006 * November 2006 * October 2006 * September 2006 * August 2006 * July 2006 * June 2006 * May 2006 * April 2006 * March 2006 * February 2006 * January 2006 * October 2005 * July 2005 * May 2005 * December 2004 * November 2004 * September 2004 * June 2004 More .NET * Download .NET * .NET Community * .NET Documentation * .NET API Browser Learn * .NET Learning Hub * Architecture Guidance * Beginner Videos * Customer Showcase Follow * Twitter * Mastodon * YouTube * Facebook * LinkedIn * GitHub Stay informed [ ] [Subscribe] By subscribing you agree to our Terms of Use and Privacy Policy Share on Social media * * * Login Theme * light-theme-iconLight * dark-theme-iconDark Insert/edit link Close Enter the destination URL URL [ ] Link Text [ ] [ ] Open link in a new tab Or link to existing content Search [ ] No search term specified. Showing recent items. Search or use up and down arrow keys to select an item. Cancel [Add Link] Code Block x Paste your code snippet [ ] Cancel Ok Feedback usabilla icon What's new * Surface Laptop Studio 2 * Surface Laptop Go 3 * Surface Pro 9 * Surface Laptop 5 * Surface Studio 2+ * Copilot in Windows * Microsoft 365 * Windows 11 apps Microsoft Store * Account profile * Download Center * Microsoft Store support * Returns * Order tracking * Certified Refurbished * Microsoft Store Promise * Flexible Payments Education * Microsoft in education * Devices for education * Microsoft Teams for Education * Microsoft 365 Education * How to buy for your school * Educator training and development * Deals for students and parents * Azure for students Business * Microsoft Cloud * Microsoft Security * Dynamics 365 * Microsoft 365 * Microsoft Power Platform * Microsoft Teams * Microsoft Industry * Small Business Developer & IT * Azure * Developer Center * Documentation * Microsoft Learn * Microsoft Tech Community * Azure Marketplace * AppSource * Visual Studio Company * Careers * About Microsoft * Company news * Privacy at Microsoft * Investors * Diversity and inclusion * Accessibility * Sustainability Your Privacy Choices Your Privacy Choices * Sitemap * Contact Microsoft * Privacy * Manage cookies * Terms of use * Trademarks * Safety & eco * Recycling * About our ads * (c) Microsoft 2023