Skip to content

Commit 5f04801

Browse files
safesparrowsafesparrow
authored
Merge pull request #17 from safesparrow/speed
2 parents 9857439 + 01c28a3 commit 5f04801

22 files changed

Lines changed: 272 additions & 603 deletions

‎.fantomasignore‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ artifacts/
1212

1313
# Explicitly formatted Tests/ subdirectories (with exceptions)
1414
!tests/ParallelTypeCheckingTests/
15-
*/.checkouts/
15+
*/.fcs_test/
1616

1717
# Explicitly unformatted implementation files
1818

‎FSharp.sln‎

Lines changed: 0 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -107,8 +107,6 @@ Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Solution Items", "Solution
107107
src\Compiler\FSComp.txt = src\Compiler\FSComp.txt
108108
EndProjectSection
109109
EndProject
110-
Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "DiamondTest", "tests\DiamondTest\DiamondTest.fsproj", "{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}"
111-
EndProject
112110
Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "ParallelTypeCheckingTests", "tests\ParallelTypeCheckingTests\ParallelTypeCheckingTests.fsproj", "{59C31D40-97E0-4A69-ABD9-D316BD798ED8}"
113111
EndProject
114112
Global
@@ -433,18 +431,6 @@ Global
433431
{9C7523BA-7AB2-4604-A5FD-653E82C2BAD1}.Release|Any CPU.Build.0 = Release|Any CPU
434432
{9C7523BA-7AB2-4604-A5FD-653E82C2BAD1}.Release|x86.ActiveCfg = Release|Any CPU
435433
{9C7523BA-7AB2-4604-A5FD-653E82C2BAD1}.Release|x86.Build.0 = Release|Any CPU
436-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
437-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Debug|Any CPU.Build.0 = Debug|Any CPU
438-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Debug|x86.ActiveCfg = Debug|Any CPU
439-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Debug|x86.Build.0 = Debug|Any CPU
440-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Proto|Any CPU.ActiveCfg = Debug|Any CPU
441-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Proto|Any CPU.Build.0 = Debug|Any CPU
442-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Proto|x86.ActiveCfg = Debug|Any CPU
443-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Proto|x86.Build.0 = Debug|Any CPU
444-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Release|Any CPU.ActiveCfg = Release|Any CPU
445-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Release|Any CPU.Build.0 = Release|Any CPU
446-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Release|x86.ActiveCfg = Release|Any CPU
447-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC}.Release|x86.Build.0 = Release|Any CPU
448434
{59C31D40-97E0-4A69-ABD9-D316BD798ED8}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
449435
{59C31D40-97E0-4A69-ABD9-D316BD798ED8}.Debug|Any CPU.Build.0 = Debug|Any CPU
450436
{59C31D40-97E0-4A69-ABD9-D316BD798ED8}.Debug|x86.ActiveCfg = Debug|Any CPU
@@ -489,7 +475,6 @@ Global
489475
{209C7D37-8C01-413C-8698-EC25F4C86976} = {B8DDA694-7939-42E3-95E5-265C2217C142}
490476
{BEC6E796-7E53-4888-AAFC-B8FD55C425DF} = {CE70D631-C5DC-417E-9CDA-B16097BEF1AC}
491477
{9C7523BA-7AB2-4604-A5FD-653E82C2BAD1} = {CE70D631-C5DC-417E-9CDA-B16097BEF1AC}
492-
{B7C957CB-9E64-44CF-BC73-152BFC6E5BCC} = {CFE3259A-2D30-4EB0-80D5-E8B5F3D01449}
493478
{59C31D40-97E0-4A69-ABD9-D316BD798ED8} = {CFE3259A-2D30-4EB0-80D5-E8B5F3D01449}
494479
EndGlobalSection
495480
GlobalSection(ExtensibilityGlobals) = postSolution

‎src/Compiler/Driver/CompilerConfig.fsi‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -205,8 +205,11 @@ type ParallelReferenceResolution =
205205

206206
[<RequireQualifiedAccess>]
207207
type TypeCheckingMode =
208+
/// Default mode where all source files are processed sequentially in compilation order.
208209
| Sequential
210+
/// Signature files and implementation files without backing files are processed sequentially, then backed implementation files are processed in parallel.
209211
| ParallelCheckingOfBackedImplFiles
212+
/// Parallel type-checking that uses automated file-to-file dependency detection to construct a highly-parallelisable file graph.
210213
| Graph
211214

212215
[<RequireQualifiedAccess>]

‎src/Compiler/Driver/CompilerOptions.fs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1392,6 +1392,11 @@ let testFlag tcConfigB =
13921392
{ tcConfigB.typeCheckingConfig with
13931393
Mode = TypeCheckingMode.ParallelCheckingOfBackedImplFiles
13941394
}
1395+
| "GraphBasedChecking" ->
1396+
tcConfigB.typeCheckingConfig <-
1397+
{ tcConfigB.typeCheckingConfig with
1398+
Mode = TypeCheckingMode.Graph
1399+
}
13951400
#if DEBUG
13961401
| "ShowParserStackOnParseError" -> showParserStackOnParseError <- true
13971402
#endif

‎src/Compiler/Driver/ParseAndCheckInputs.fs‎

Lines changed: 17 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -759,17 +759,31 @@ let ParseInputFilesInParallel (tcConfig: TcConfig, lexResourceManager, sourceFil
759759
for fileName in sourceFiles do
760760
checkInputFile tcConfig fileName
761761

762+
763+
// Order files to be parsed by size (descending). The idea is to process big files first,
764+
// so that near the end when only some nodes are still processing items, it's the smallest items,
765+
// which should reduce the period of time where only some nodes are busy.
766+
// This requires some empirical evidence.
767+
let sourceFiles =
768+
sourceFiles
769+
|> List.mapi (fun i f -> i, f)
770+
|> List.sortBy (fun (_i, f) -> -FileInfo(f).Length)
771+
762772
let sourceFiles = List.zip sourceFiles isLastCompiland
763773

764774
UseMultipleDiagnosticLoggers (sourceFiles, delayLogger, None) (fun sourceFilesWithDelayLoggers ->
765775
sourceFilesWithDelayLoggers
766-
|> ListParallel.map (fun ((fileName, isLastCompiland), delayLogger) ->
776+
|> ListParallel.map (fun (((idx, fileName), isLastCompiland), delayLogger) ->
767777
let directoryName = Path.GetDirectoryName fileName
768778

769779
let input =
770780
parseInputFileAux (tcConfig, lexResourceManager, fileName, (isLastCompiland, isExe), delayLogger, retryLocked)
771781

772-
(input, directoryName)))
782+
idx, (input, directoryName))
783+
// Bring back index-based order
784+
|> List.sortBy fst
785+
|> List.map snd
786+
)
773787

774788
let ParseInputFilesSequential (tcConfig: TcConfig, lexResourceManager, sourceFiles, diagnosticsLogger: DiagnosticsLogger, retryLocked) =
775789
let isLastCompiland, isExe = sourceFiles |> tcConfig.ComputeCanContainEntryPoint
@@ -1729,7 +1743,7 @@ let mutable typeCheckingMode: TypeCheckingMode = TypeCheckingMode.Sequential
17291743
let CheckClosedInputSet (ctok, checkForErrors, tcConfig: TcConfig, tcImports, tcGlobals, prefixPathOpt, tcState, eagerFormat, inputs) =
17301744
// tcEnvAtEndOfLastFile is the environment required by fsi.exe when incrementally adding definitions
17311745
let results, tcState =
1732-
match typeCheckingMode with
1746+
match tcConfig.typeCheckingConfig.Mode with
17331747
| TypeCheckingMode.Sequential ->
17341748
CheckMultipleInputsSequential(ctok, checkForErrors, tcConfig, tcImports, tcGlobals, prefixPathOpt, tcState, inputs)
17351749
| TypeCheckingMode.ParallelCheckingOfBackedImplFiles ->

‎tests/ParallelTypeCheckingTests/Code/ASTVisit.fs‎

Lines changed: 25 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1254,18 +1254,20 @@ module TopModulesExtraction =
12541254
synAccessOption,
12551255
range,
12561256
synModuleOrNamespaceTrivia) ->
1257-
if mightHaveAutoOpen synAttributeLists then
1258-
// Contents of a module that's potentially AutoOpen are available from its parent without a prefix.
1259-
// Stay safe and as soon as the parent module is reachable, consider this module reachable as well
1260-
[| LongIdent.Empty |]
1261-
else
1262-
// 'module A.B' is equivalent to 'namespace A; module B', meaning that 'A' is opened implicitly
12631257
if
1264-
synModuleOrNamespaceKind.IsModule && longId.Length > 1
1258+
mightHaveAutoOpen synAttributeLists && synModuleOrNamespaceKind.IsModule
12651259
then
1260+
// Contents of a module that's potentially AutoOpen are available from its parent without a prefix.
1261+
// Stay safe and as soon as the parent module is reachable, consider this module reachable as well
12661262
[| longId.GetSlice(None, Some <| longId.Length - 2); longId |]
12671263
else
1268-
[| longId |]
1264+
// 'module A.B' is equivalent to 'namespace A; module B', meaning that 'A' is opened implicitly
1265+
if
1266+
synModuleOrNamespaceKind.IsModule && longId.Length > 1
1267+
then
1268+
[| longId.GetSlice(None, Some <| longId.Length - 2); longId |]
1269+
else
1270+
[| longId |]
12691271
// TODO Temporarily disabled digging into the file's structure to avoid edge cases where another file depends on this file's namespace existing (but nothing else)
12701272
// synModuleDecls
12711273
// |> moduleDecls
@@ -1307,6 +1309,8 @@ module TopModulesExtraction =
13071309
synAccessOption,
13081310
range) ->
13091311
let idents =
1312+
// TODO Fix this by making it similar to what happens in other places where we detect AutoOpen modules
1313+
// Currently it doesn't matter, since we don't look within modules.
13101314
if mightHaveAutoOpen synAttributeLists then
13111315
// Contents of a module that's potentially AutoOpen are available everywhere, so treat it as if it had no name ('root' module).
13121316
[| LongIdent.Empty |]
@@ -1326,11 +1330,20 @@ module TopModulesExtraction =
13261330
synAccessOption,
13271331
range,
13281332
synModuleOrNamespaceTrivia) ->
1329-
if mightHaveAutoOpen synAttributeLists then
1330-
// Contents of a module that's potentially AutoOpen are available everywhere, so treat it as if it had no name ('root' module).
1331-
[| LongIdent.Empty |]
1333+
if
1334+
mightHaveAutoOpen synAttributeLists && synModuleOrNamespaceKind.IsModule
1335+
then
1336+
// Contents of a module that's potentially AutoOpen are available from its parent without a prefix.
1337+
// Stay safe and as soon as the parent module is reachable, consider this module reachable as well
1338+
[| longId.GetSlice(None, Some <| longId.Length - 2); longId |]
13321339
else
1333-
synModuleDecls |> moduleSigDecls |> combine longId
1340+
// 'module A.B' is equivalent to 'namespace A; module B', meaning that 'A' is opened implicitly
1341+
if
1342+
synModuleOrNamespaceKind.IsModule && longId.Length > 1
1343+
then
1344+
[| longId.GetSlice(None, Some <| longId.Length - 2); longId |]
1345+
else
1346+
[| longId |]
13341347

13351348
and moduleSigDecls (x: SynModuleSigDecl list) : Eit =
13361349
let emptyState = Eit.Nested [||]

‎tests/ParallelTypeCheckingTests/Code/DependencyResolution.fs‎

Lines changed: 10 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -260,31 +260,31 @@ module internal DependencyResolution =
260260
}
261261

262262
/// <summary>
263-
/// Calculate and print some stats about the expected parallelism factor of a dependency graph
263+
/// Calculate and print some statistics about the expected parallelism factor of a dependency graph
264264
/// </summary>
265265
let analyseEfficiency (result: DepsResult) : unit =
266266
let graph = result.Graph
267-
let totalSize1 = graph |> Seq.sumBy (fun (KeyValue (_k, v)) -> v.Length)
268-
let t = graph |> Graph.transitive
269-
let totalSize2 = t |> Seq.sumBy (fun (KeyValue (_k, v)) -> v.Length)
267+
let edgeCount = graph |> Seq.sumBy (fun (KeyValue (_k, v)) -> v.Length)
268+
let t = graph |> Graph.transitiveOpt
269+
let edgeCountTransitive = t |> Seq.sumBy (fun (KeyValue (_k, v)) -> v.Length)
270270

271-
printfn $"Non-transitive size: {totalSize1}, transitive size: {totalSize2}"
271+
log $"Non-transitive edge count: {edgeCount}, transitive edge count: {edgeCountTransitive}"
272272

273-
let totalFileSize = result.Files |> Array.sumBy (fun file -> int64 (file.CodeSize))
273+
let fileCount = result.Files.Length
274274

275-
// Use depth-first search to calculate 'depth' of each file
275+
// Use depth-first search to calculate 'depth' of a file
276276
let rec depthDfs =
277277
Utils.memoize (fun (file: File) ->
278278
let deepestChild =
279279
match result.Graph[file] with
280-
| [||] -> 0L
280+
| [||] -> 0
281281
| d -> d |> Array.map depthDfs |> Array.max
282282

283-
let depth = int64 (file.CodeSize) + deepestChild
283+
let depth = 1 + deepestChild
284284
depth)
285285

286286
// Run DFS for every file node, collect the maximum depth found
287287
let maxDepth = result.Files |> Array.map (fun f -> depthDfs f.File) |> Array.max
288288

289289
log
290-
$"Total file size: {totalFileSize}. Max depth: {maxDepth}. Max Depth/Size = %.1f{100.0 * double (maxDepth) / double (totalFileSize)}%%"
290+
$"File count: {fileCount}. Longest path: {maxDepth}. Longest path/File count (a weak proxy for level of parallelism) = %.1f{100.0 * double maxDepth / double fileCount}%%"

‎tests/ParallelTypeCheckingTests/Code/FileInfoGathering.fs‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,6 @@ let internal gatherBackingInfo (files: SourceFiles) : Files =
2323

2424
{
2525
Idx = FileIdx.make i
26-
Code = "no code here" // TODO
2726
AST = ASTOrFsix.AST f.AST
2827
FsiBacked = fsiBacked
2928
})

‎tests/ParallelTypeCheckingTests/Code/Graph.fs‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,23 @@ module Graph =
4242
graph.Values |> Seq.toArray |> Array.concat |> Array.except graph.Keys
4343

4444
addIfMissing missingNodes graph
45+
46+
/// Create a transitive closure of the graph
47+
let transitiveOpt<'Node when 'Node: equality> (graph: Graph<'Node>) : Graph<'Node> =
48+
let go (node: 'Node) =
49+
let visited = HashSet<'Node>()
50+
let rec dfs (node: 'Node) =
51+
graph[node]
52+
|> Array.filter visited.Add
53+
|> Array.iter dfs
54+
dfs node
55+
visited
56+
|> Seq.toArray
57+
58+
graph.Keys
59+
|> Seq.toArray
60+
|> Array.Parallel.map (fun node -> node, go node)
61+
|> readOnlyDict
4562

4663
/// Create a transitive closure of the graph
4764
let transitive<'Node when 'Node: equality> (graph: Graph<'Node>) : Graph<'Node> =

‎tests/ParallelTypeCheckingTests/Code/GraphProcessing.fs‎

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -104,6 +104,7 @@ let combineResults
104104
(deps: Node<'Item, 'State, 'Result>[])
105105
(transitiveDeps: Node<'Item, 'State, 'Result>[])
106106
(folder: 'State -> 'Result -> 'State)
107+
(_foldingOrderer: 'Item -> int)
107108
: 'State =
108109
match deps with
109110
| [||] -> emptyState
@@ -127,7 +128,8 @@ let combineResults
127128
// Sort it by effectively file index.
128129
// For some reason this is needed, otherwise gives 'missing namespace' and other errors when using the resulting state.
129130
// Does this make sense? Should the results be foldable in any order?
130-
|> Array.sortBy (fun d -> d.Info.Item)
131+
// TODO Use _foldingOrderer
132+
|> Array.sortBy (fun node -> node.Info.Item)
131133
|> Array.filter (fun dep -> included.Contains dep.Info.Item = false)
132134
|> Array.distinctBy (fun dep -> dep.Info.Item)
133135
|> Array.map (fun dep -> dep.Result |> orFail |> snd)
@@ -140,11 +142,12 @@ let processGraph<'Item, 'State, 'Result, 'FinalFileResult when 'Item: equality a
140142
(graph: Graph<'Item>)
141143
(doWork: 'Item -> 'State -> 'Result)
142144
(folder: 'State -> 'Result -> 'FinalFileResult * 'State)
145+
(foldingOrderer: 'Item -> int)
143146
(emptyState: 'State)
144147
(includeInFinalState: 'Item -> bool)
145148
(parallelism: int)
146149
: 'FinalFileResult[] * 'State =
147-
let transitiveDeps = graph |> Graph.transitive
150+
let transitiveDeps = graph |> Graph.transitiveOpt
148151
let dependants = graph |> Graph.reverse
149152

150153
let makeNode (item: 'Item) : Node<'Item, StateWrapper<'Item, 'State>, ResultWrapper<'Item, 'Result>> =
@@ -208,7 +211,7 @@ let processGraph<'Item, 'State, 'Result, 'FinalFileResult when 'Item: equality a
208211
let folder x y = folder x y |> snd
209212
let deps = lookupMany node.Info.Deps
210213
let transitiveDeps = lookupMany node.Info.TransitiveDeps
211-
let inputState = combineResults emptyState deps transitiveDeps folder
214+
let inputState = combineResults emptyState deps transitiveDeps folder foldingOrderer
212215
node.InputState <- Some inputState
213216
let singleRes = doWork node.Info.Item inputState.State
214217

0 commit comments

Comments
 (0)