[ninjago] Drag calculation for critical steps
Test: fx test --host -o ninjagraph_test
Change-Id: Ic586f9140f9104d9dc01f0b272f765ce5624c639
Reviewed-on: https://fuchsia-review.googlesource.com/c/fuchsia/+/442477
Commit-Queue: Jay Zhuang <jayzhuang@google.com>
Reviewed-by: Shai Barack <shayba@google.com>
Testability-Review: Shai Barack <shayba@google.com>
diff --git a/tools/build/ninjago/ninjagraph/ninjagraph.go b/tools/build/ninjago/ninjagraph/ninjagraph.go
index aa10614..ac765ff 100644
--- a/tools/build/ninjago/ninjagraph/ninjagraph.go
+++ b/tools/build/ninjago/ninjagraph/ninjagraph.go
@@ -732,3 +732,93 @@
sort.Slice(criticalPath, func(i, j int) bool { return criticalPath[i].Start < criticalPath[j].Start })
return criticalPath, nil
}
+
+// parallelizableEdges returns all edges that can be run in parallel with the
+// input edge.
+func (g *Graph) parallelizableEdges(edge *Edge) ([]*Edge, error) {
+ if edge.Step == nil {
+ return nil, fmt.Errorf("input edge has no step associated to it, this should not happen if edges are correctly populated")
+ }
+
+ latestFinish, err := g.latestFinish(edge)
+ if err != nil {
+ return nil, err
+ }
+
+ var ret []*Edge
+ for _, e := range g.Edges {
+ if e == edge || e.Rule == "phony" || e.Rule == ninjagoArtificialSinkRule {
+ continue
+ }
+ if e.Step == nil {
+ return nil, fmt.Errorf("step is missing on edge, step can be populated by calling `PopulateEdges`")
+ }
+
+ es, err := g.earliestStart(e)
+ if err != nil {
+ return nil, err
+ }
+ lf, err := g.latestFinish(e)
+ if err != nil {
+ return nil, err
+ }
+
+ // TODO(jayzhuang): validate whether the checks below are good enough to get
+ // all parallelizable edges.
+
+ // This check covers 2 possibilities:
+ //
+ // edge: |oooooooo|
+ // e: |-----------------|
+ //
+ // or
+ //
+ // edge: |ooooooooo|
+ // e: |------------|
+ if lf >= latestFinish && es < latestFinish {
+ ret = append(ret, e)
+ continue
+ }
+ }
+ return ret, nil
+}
+
+// drag returns drag of the input edge. Drag is the amount of time an action
+// on the critical path is adding the total build time.
+//
+// NOTE: drag calculation assumes unconstrained parallelism, such that actions
+// can always begin as soon as their inputs are satisfied and never wait to be
+// scheduled on an available machine resources (CPU, RAM, I/O).
+//
+// https://en.wikipedia.org/wiki/Critical_path_drag
+func (g *Graph) drag(edge *Edge) (time.Duration, error) {
+ if edge.Step == nil {
+ return 0, fmt.Errorf("step is missing on edge, step can be populated by calling `PopulateEdges`")
+ }
+
+ tf, err := g.totalFloat(edge)
+ if err != nil {
+ return 0, fmt.Errorf("calculating total float: %w", err)
+ }
+ if tf != 0 {
+ // This edge is not on the critical path, so drag = 0.
+ return 0, fmt.Errorf("drag called for non-critical edge")
+ }
+
+ edges, err := g.parallelizableEdges(edge)
+ if err != nil {
+ return 0, fmt.Errorf("getting parallelizable edges: %w", err)
+ }
+
+ drag := edge.Step.Duration()
+ for _, e := range edges {
+ tf, err := g.totalFloat(e)
+ if err != nil {
+ return 0, fmt.Errorf("calculating total float of parallel edges: %w", err)
+ }
+ if tf < drag {
+ drag = tf
+ }
+ }
+ return drag, nil
+}
diff --git a/tools/build/ninjago/ninjagraph/ninjagraph_test.go b/tools/build/ninjago/ninjagraph/ninjagraph_test.go
index 9dbcc25..8161fde 100644
--- a/tools/build/ninjago/ninjagraph/ninjagraph_test.go
+++ b/tools/build/ninjago/ninjagraph/ninjagraph_test.go
@@ -968,6 +968,25 @@
}
for _, want := range []struct {
+ input *Edge
+ parallelizables []*Edge
+ }{
+ {input: edge1},
+ {input: edge2, parallelizables: []*Edge{edge6, edge8}},
+ {input: edge3, parallelizables: []*Edge{edge6, edge8}},
+ {input: edge4, parallelizables: []*Edge{edge7, edge8}},
+ {input: edge5},
+ } {
+ got, err := g.parallelizableEdges(want.input)
+ if err != nil {
+ t.Errorf("parallelizableEdges(edge outputting %v) error: %v", want.input.Outputs, err)
+ }
+ if !cmp.Equal(got, want.parallelizables, cmpopts.IgnoreUnexported(Edge{})) {
+ t.Errorf("parallelizableEdges(edge outputting %v) = %s, want: %s", want.input.Outputs, edgesToStr(got), edgesToStr(want.parallelizables))
+ }
+ }
+
+ for _, want := range []struct {
input *Edge
earliestStart time.Duration
earliestFinish time.Duration
@@ -1056,6 +1075,29 @@
}
}
}
+
+ for _, want := range []struct {
+ input *Edge
+ err bool
+ drag time.Duration
+ }{
+ {input: edge1, drag: 10},
+ {input: edge2, drag: 15},
+ {input: edge3, drag: 5},
+ {input: edge4, drag: 5},
+ {input: edge5, drag: 20},
+ {input: edge6, err: true},
+ {input: edge7, err: true},
+ {input: edge8, err: true},
+ } {
+ got, err := g.drag(want.input)
+ if (err != nil) != want.err {
+ t.Errorf("drag(edge outputting %v) got error: %v, want error: %t", want.input.Outputs, err, want.err)
+ }
+ if got != want.drag {
+ t.Errorf("drag(edge outputting %v) = %s, want: %s", want.input.Outputs, got, want.drag)
+ }
+ }
}
func edgesToStr(edges []*Edge) string {
