tree a1b66147c7dfbde911a2ac72ae346dc10e54e6a7
parent 9aa43a01a3b7840d14f6185c18f21cbae8363d3c
author David 'Digit' Turner <digit+github@google.com> 1715067291 +0200
committer Jan Niklas Hasse <jhasse@bixense.com> 1715427715 +0200

ComputeCriticalPath: Use topological sort to speed up function.

Use a topological sort to get a sorted list of edges to perform
the critical path weigth propagation as fast as possible.

The previous version used a data flow algorithm that forced
the values to be recomputed several times for far too many
edges on complex build plans.

For example, for a Fuchsia build plan with 93339 edges,
this reduces the ComputeCriticalPath metric from 1.9s to 80ms!

The unit-tests still pass, and manual testing shows that the
order of commands does not change before and after this change
for the example build plan above.