Skip to content

Commit b9e1dde

Browse files
safesparrowsafesparrow
committed
WIP - start combining partial results in an efficient way
1 parent 221f650 commit b9e1dde

1 file changed

Lines changed: 135 additions & 49 deletions

File tree

‎tests/FSharp.Compiler.Service.Tests2/RunCompiler.fs‎

Lines changed: 135 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -2,73 +2,108 @@
22

33
open System
44
open System.Collections.Concurrent
5+
open System.Collections.Generic
56
open System.Threading
67
open System.Threading.Tasks
78
open FSharp.Compiler.Service.Tests2
9+
open FSharp.Compiler.Service.Tests2.DepResolving
810
open NUnit.Framework
911

12+
type FileIdx =
13+
FileIdx of int
14+
with
15+
member this.Idx = match this with FileIdx idx -> idx
16+
override this.ToString() = this.Idx.ToString()
17+
static member make (idx : int) = FileIdx idx
18+
1019
type Node =
1120
{
12-
Idx : int
13-
Deps : int[]
14-
Dependants : int[]
21+
Idx : FileIdx
22+
Deps : FileIdx[]
23+
TransitiveDeps : FileIdx[]
24+
Dependants : FileIdx[]
1525
mutable PartialResult : string option
26+
mutable ThisResult : int
1627
mutable UnprocessedDepsCount : int
1728
_lock : Object
1829
}
30+
with member this.GetHashCode() = this.Idx.Idx
1931

2032
[<Test>]
2133
let runCompiler () =
2234
let args =
2335
System.IO.File.ReadAllLines(@"C:\projekty\fsharp\heuristic\tests\FSharp.Compiler.Service.Tests2\args.txt") |> Array.skip 1
2436
FSharp.Compiler.CommandLineMain.main args |> ignore
2537

26-
[<Test>]
27-
let runGrapher () =
28-
// let args =
29-
// System.IO.File.ReadAllLines(@"C:\projekty\fsharp\heuristic\tests\FSharp.Compiler.Service.Tests2\args.txt") |> Array.skip 1
30-
// FSharp.Compiler.CommandLineMain.main args |> ignore
38+
39+
40+
/// <summary> DAG of files </summary>
41+
type FileGraph = IReadOnlyDictionary<FileIdx, FileIdx[]>
42+
43+
let memoize<'a, 'b when 'a : equality> f : ('a -> 'b) =
44+
let y = HashIdentity.Structural<'a>
45+
let d = new ConcurrentDictionary<'a, 'b>(y)
46+
fun x -> d.GetOrAdd(x, fun r -> f r)
47+
48+
module FileGraph =
3149

32-
let fileDeps =
33-
[|
34-
0, [||] // A
35-
1, [|0|] // B1 -> A
36-
2, [|1|] // B2 -> B1
37-
3, [|0|] // C1 -> A
38-
4, [|3|] // C2 -> C1
39-
5, [|2; 4|] // D -> B2, C2
40-
|]
41-
|> dict
42-
|> DepResolving.calcTransitiveGraph
43-
|> Seq.map (fun (KeyValue(k, v)) -> k, v)
44-
|> Seq.toArray
50+
let calcTransitiveGraph (graph : FileGraph) : FileGraph =
51+
let transitiveGraph = Dictionary<FileIdx, FileIdx[]>()
52+
53+
let rec calcTransitiveEdges =
54+
fun (idx : FileIdx) ->
55+
let edgeTargets = graph[idx]
56+
edgeTargets
57+
|> Array.collect calcTransitiveEdges
58+
|> Array.append edgeTargets
59+
|> Array.distinct
60+
|> memoize
61+
62+
graph.Keys
63+
|> Seq.iter (fun idx -> calcTransitiveEdges idx |> ignore)
64+
65+
transitiveGraph :> IReadOnlyDictionary<_,_>
66+
67+
let collectEdges (graph : FileGraph) =
68+
graph
4569

46-
let fileDependants =
47-
fileDeps
48-
// Collect all edges
49-
|> Array.collect (fun (idx, deps) -> deps |> Array.map (fun dep -> idx, dep))
50-
// Group dependants of the same dependencies together
51-
|> Array.groupBy (fun (idx, dep) -> dep)
52-
// Construct reversed graph
53-
|> Array.map (fun (dep, edges) -> dep, edges |> Array.map fst)
54-
|> dict
55-
// Add nodes that are missing due to having no dependants
56-
|> fun graph ->
57-
fileDeps
58-
|> Array.map (fun (idx, deps) ->
59-
match graph.TryGetValue idx with
60-
| true, dependants -> idx, dependants
61-
| false, _ -> idx, [||]
62-
)
63-
|> dict
70+
type State = string // TcState
71+
type SingleResult = int // partial result for a single file
6472

65-
let graph =
66-
fileDeps
67-
|> Seq.map (fun (idx, deps) -> idx, {Idx = idx; Deps = deps; Dependants = fileDependants[idx]; PartialResult = None; UnprocessedDepsCount = deps.Length; _lock = Object()})
68-
|> dict
73+
/// <summary>
74+
/// Combine results of all transitive dependencies for a single target node.
75+
/// </summary>
76+
/// <param name="graph"></param>
77+
/// <param name="deps">Transitive deps</param>
78+
let combineResults (graph : IReadOnlyDictionary<FileIdx, Node>) (node : Node) (folder : State -> SingleResult -> State) : State =
79+
80+
// Find the child with most transitive deps
81+
let biggestChild =
82+
node.TransitiveDeps
83+
|> Array.map (fun d -> graph[d])
84+
|> Array.maxBy (fun n -> n.TransitiveDeps.Length)
85+
86+
// Start with that child's state
87+
let state = biggestChild.PartialResult |> Option.defaultWith (fun () -> failwith "Unexpected lack of result")
88+
89+
let alreadyIncluded = HashSet<FileIdx>(biggestChild.TransitiveDeps, HashIdentity.Structural)
90+
91+
// Find individual results from all transitive deps that were not in biggestChild
92+
let toBeAdded =
93+
node.TransitiveDeps
94+
|> Array.filter alreadyIncluded.Add
95+
96+
let state =
97+
toBeAdded
98+
|> Array.map (fun d -> graph[d].ThisResult)
99+
|> Array.fold folder state
100+
101+
state
102+
103+
let processGraph (graph : IDictionary<FileIdx, Node>) =
69104

70105
printfn "start"
71-
use q = new BlockingCollection<int>()
106+
use q = new BlockingCollection<FileIdx>()
72107

73108
// Add leaves to the queue
74109
let filesWithoutDeps =
@@ -87,17 +122,20 @@ let runGrapher () =
87122
printfn $"UnprocessedCount = {unprocessedCount}"
88123
)
89124

90-
let actualWork (idx : int) =
125+
let fold (state : string) (singleResult : int) =
126+
state + singleResult.ToString()
127+
128+
let actualWork (idx : FileIdx) =
91129
let node = graph[idx]
92130
let depsResult =
93131
node.Deps
94132
|> Array.map (fun dep -> match graph[dep].PartialResult with Some result -> result | None -> failwith $"Unexpected lack of result for a dependency {idx} -> {dep}")
95-
|> Array.fold (fun state item -> state + item) ""
96-
let thisResult = idx.ToString()
97-
$"{thisResult}"
133+
|> Array.fold fold ""
134+
let thisResult = idx.Idx
135+
thisResult
98136

99137
// Processing of a single node/file - gives a result
100-
let go (idx : int) =
138+
let go (idx : FileIdx) =
101139
let node = graph[idx]
102140
printfn $"Start {idx} -> %+A{node.Deps}"
103141
Thread.Sleep(500)
@@ -151,3 +189,51 @@ let runGrapher () =
151189
|> Seq.fold (fun state item -> state + item) ""
152190

153191
printfn $"End result: {fullResult}"
192+
193+
194+
[<Test>]
195+
let runGrapher () =
196+
// let args =
197+
// System.IO.File.ReadAllLines(@"C:\projekty\fsharp\heuristic\tests\FSharp.Compiler.Service.Tests2\args.txt") |> Array.skip 1
198+
// FSharp.Compiler.CommandLineMain.main args |> ignore
199+
200+
let graph =
201+
[|
202+
0, [||] // A
203+
1, [|0|] // B1 -> A
204+
2, [|1|] // B2 -> B1
205+
3, [|0|] // C1 -> A
206+
4, [|3|] // C2 -> C1
207+
5, [|2; 4|] // D -> B2, C2
208+
|]
209+
|> dict
210+
211+
let fileDeps =
212+
graph
213+
|> DepResolving.calcTransitiveGraph
214+
215+
let fileDependants =
216+
fileDeps
217+
// Collect all edges
218+
|> Seq.collect (fun (idx, deps) -> deps |> Array.map (fun dep -> FileIdx.make idx, FileIdx.make dep))
219+
// Group dependants of the same dependencies together
220+
|> Array.groupBy (fun (idx, dep) -> dep)
221+
// Construct reversed graph
222+
|> Array.map (fun (dep, edges) -> dep, edges |> Array.map fst)
223+
|> dict
224+
// Add nodes that are missing due to having no dependants
225+
|> fun graph ->
226+
fileDeps
227+
|> Array.map (fun (idx, deps) ->
228+
match graph.TryGetValue idx with
229+
| true, dependants -> idx, dependants
230+
| false, _ -> idx, [||]
231+
)
232+
|> dict
233+
234+
let graph =
235+
fileDeps
236+
|> Seq.map (fun (idx, deps) -> idx, {Idx = idx; Deps = deps; Dependants = fileDependants[idx]; PartialResult = None; UnprocessedDepsCount = deps.Length; _lock = Object()})
237+
|> dict
238+
239+
processGraph graph

0 commit comments

Comments
 (0)