diff options
author | David 'Digit' Turner <digit+github@google.com> | 2024-05-07 07:34:51 (GMT) |
---|---|---|
committer | Jan Niklas Hasse <jhasse@bixense.com> | 2024-05-11 11:41:55 (GMT) |
commit | ba68213f518c8d54842f2471fbbc1b65d6caf2f4 (patch) | |
tree | a1b66147c7dfbde911a2ac72ae346dc10e54e6a7 /src/dyndep.h | |
parent | 9aa43a01a3b7840d14f6185c18f21cbae8363d3c (diff) | |
download | Ninja-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 'src/dyndep.h')
0 files changed, 0 insertions, 0 deletions