Skip to content

Commit d4e8bbd

Browse files
safesparrowsafesparrow
committed
* Small cleanup
* Bring back the state combination optimization where we reuse the results of the child with most transitive dependencies - 10x speedup of 'combineResults' method
1 parent 881f572 commit d4e8bbd

3 files changed

Lines changed: 5 additions & 69 deletions

File tree

‎tests/ParallelTypeCheckingTests/Code/GraphProcessing.fs‎

Lines changed: 4 additions & 65 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ type Node<'Item, 'State, 'Result> =
4545
/// <param name="deps">Direct dependencies of a node</param>
4646
/// <param name="transitiveDeps">Transitive dependencies of a node</param>
4747
/// <param name="folder">A way to fold a single result into existing state</param>
48-
let combineResultsOld
48+
let combineResults
4949
(emptyState: 'State)
5050
(deps: Node<'Item, 'State, 'Result>[])
5151
(transitiveDeps: Node<'Item, 'State, 'Result>[])
@@ -54,17 +54,11 @@ let combineResultsOld
5454
match deps with
5555
| [||] -> emptyState
5656
| _ ->
57-
5857
let biggestDep =
5958
let sizeMetric node =
60-
// Could also use eg. total file size/AST size
61-
node.Info.Item
62-
// node.Info.TransitiveDeps.Length
59+
node.Info.TransitiveDeps.Length
6360
deps
64-
// TODO To workaround a problem with merging state in the wrong order,
65-
// we temporarily effectively pick the child with the lowest index.
66-
// This means children are folded fully in sequence
67-
|> Array.minBy sizeMetric
61+
|> Array.maxBy sizeMetric
6862

6963
let orFail value =
7064
value |> Option.defaultWith (fun () -> failwith "Unexpected lack of result")
@@ -90,61 +84,12 @@ let combineResultsOld
9084
let state = Array.fold folder firstState resultsToAdd
9185
state
9286

93-
// TODO Do we need to suppress some error logging if we
94-
// TODO apply the same partial results multiple times?
95-
// TODO Maybe we can enable logging only for the final fold
96-
/// <summary>
97-
/// Combine results of dependencies needed to type-check a 'higher' node in the graph
98-
/// </summary>
99-
/// <param name="deps">Direct dependencies of a node</param>
100-
/// <param name="transitiveDeps">Transitive dependencies of a node</param>
101-
/// <param name="folder">A way to fold a single result into existing state</param>
102-
let combineResults
103-
(emptyState: 'State)
104-
(deps: Node<'Item, 'State, 'Result>[])
105-
(transitiveDeps: Node<'Item, 'State, 'Result>[])
106-
(folder: 'State -> 'Result -> 'State)
107-
(_foldingOrderer: 'Item -> int)
108-
: 'State =
109-
match deps with
110-
| [||] -> emptyState
111-
| _ ->
112-
let orFail value =
113-
value |> Option.defaultWith (fun () -> failwith "Unexpected lack of result")
114-
115-
let firstState = emptyState
116-
// TODO Potential perf optimisation: Keep transDeps in a HashSet from the start,
117-
// avoiding reconstructing the HashSet here
118-
119-
// Add single-file results of remaining transitive deps one-by-one using folder
120-
// Note: Good to preserve order here so that folding happens in file order
121-
let included =
122-
let set = HashSet()
123-
//set.Add biggestDep.Info.Item |> ignore
124-
set
125-
126-
let resultsToAdd =
127-
transitiveDeps
128-
// Sort it by effectively file index.
129-
// For some reason this is needed, otherwise gives 'missing namespace' and other errors when using the resulting state.
130-
// Does this make sense? Should the results be foldable in any order?
131-
// TODO Use _foldingOrderer
132-
|> Array.sortBy (fun node -> node.Info.Item)
133-
|> Array.filter (fun dep -> included.Contains dep.Info.Item = false)
134-
|> Array.distinctBy (fun dep -> dep.Info.Item)
135-
|> Array.map (fun dep -> dep.Result |> orFail |> snd)
136-
137-
let state = Array.fold folder firstState resultsToAdd
138-
state
139-
14087
// TODO Could be replaced with a simpler recursive approach with memoised per-item results
14188
let processGraph<'Item, 'State, 'Result, 'FinalFileResult when 'Item: equality and 'Item: comparison>
14289
(graph: Graph<'Item>)
14390
(doWork: 'Item -> 'State -> 'Result)
14491
(folder: bool -> 'State -> 'Result -> 'FinalFileResult * 'State)
145-
(foldingOrderer: 'Item -> int)
14692
(emptyState: 'State)
147-
(includeInFinalState: 'Item -> bool)
14893
(parallelism: int)
14994
: 'FinalFileResult[] * 'State =
15095
let transitiveDeps = graph |> Graph.transitiveOpt
@@ -203,15 +148,14 @@ let processGraph<'Item, 'State, 'Result, 'FinalFileResult when 'Item: equality a
203148
finalFileResult, state
204149

205150
printfn $"Node count: {nodes.Count}"
206-
// let mutable cnt = 1
207151

208152
let work
209153
(node: Node<'Item, StateWrapper<'Item, 'State>, ResultWrapper<'Item, 'Result>>)
210154
: Node<'Item, StateWrapper<'Item, 'State>, ResultWrapper<'Item, 'Result>>[] =
211155
let folder x y = folder false x y |> snd
212156
let deps = lookupMany node.Info.Deps
213157
let transitiveDeps = lookupMany node.Info.TransitiveDeps
214-
let inputState = combineResults emptyState deps transitiveDeps folder foldingOrderer
158+
let inputState = combineResults emptyState deps transitiveDeps folder
215159
node.InputState <- Some inputState
216160
let singleRes = doWork node.Info.Item inputState.State
217161

@@ -222,7 +166,6 @@ let processGraph<'Item, 'State, 'Result, 'FinalFileResult when 'Item: equality a
222166
}
223167

224168
let state = folder inputState singleRes
225-
//let state, = folder inputState singleRes
226169
node.Result <- Some(state, singleRes)
227170
// Need to double-check that only one dependency schedules this dependant
228171
let unblocked =
@@ -262,11 +205,7 @@ let processGraph<'Item, 'State, 'Result, 'FinalFileResult when 'Item: equality a
262205

263206
let finals, { State = state }: 'FinalFileResult[] * StateWrapper<'Item, 'State> =
264207
nodesArray
265-
|> Array.filter (fun node -> includeInFinalState node.Info.Item)
266208
|> Array.sortBy (fun node -> node.Info.Item)
267-
|> fun nodes ->
268-
// printfn $"%+A{nodes |> Array.map (fun n -> n.Info.Item.ToString())}"
269-
nodes
270209
|> Array.fold
271210
(fun (fileResults, state) node ->
272211
let fileResult, state = folder true state (node.Result.Value |> snd)

‎tests/ParallelTypeCheckingTests/Code/ParallelTypeChecking.fs‎

Lines changed: 0 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -136,7 +136,6 @@ let CheckMultipleInputsInParallel
136136
let parsedInput, logger = inputsWithLoggers.[fileIdx]
137137
processFile (parsedInput, logger) state
138138

139-
let folder: bool -> State -> SingleResult -> FinalFileResult * State = folder
140139
let _qnof = QualifiedNameOfFile.QualifiedNameOfFile(Ident("", Range.Zero))
141140
let state: State = tcState, priorErrors
142141

@@ -145,10 +144,7 @@ let CheckMultipleInputsInParallel
145144
graph
146145
processFile
147146
folder
148-
// When combining results, order them by index
149-
id
150147
state
151-
(fun _ -> true)
152148
10
153149

154150
partialResults |> Array.toList, tcState)

‎tests/ParallelTypeCheckingTests/Tests/TestCompilationFromCmdlineArgs.fs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,7 @@ let internal codebaseToConfig code method =
8888
WorkingDir = Some code.WorkDir
8989
}
9090

91+
/// Before running this test, you must prepare the codebase by running the script 'FCS.prepare.ps1'
9192
[<TestCaseSource(nameof (codebases))>]
9293
[<Explicit("Slow, only useful as a sanity check that the test codebase is sound and type-checks using the old method")>]
9394
let ``1. Test sequential type-checking`` (code: Codebase) =

0 commit comments

Comments
 (0)