summaryrefslogtreecommitdiffstats
path: root/doc
diff options
context:
space:
mode:
authorDavid 'Digit' Turner <digit+github@google.com>2024-05-07 07:34:51 (GMT)
committerJan Niklas Hasse <jhasse@bixense.com>2024-05-11 11:41:55 (GMT)
commitba68213f518c8d54842f2471fbbc1b65d6caf2f4 (patch)
treea1b66147c7dfbde911a2ac72ae346dc10e54e6a7 /doc
parent9aa43a01a3b7840d14f6185c18f21cbae8363d3c (diff)
downloadNinja-ba68213f518c8d54842f2471fbbc1b65d6caf2f4.zip
Ninja-ba68213f518c8d54842f2471fbbc1b65d6caf2f4.tar.gz
Ninja-ba68213f518c8d54842f2471fbbc1b65d6caf2f4.tar.bz2
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.
Diffstat (limited to 'doc')
0 files changed, 0 insertions, 0 deletions