Reduce redundant walks when resolving module depends_on
#35157
Conversation
A walk can start from multiple roots, so making the Ancestors and Descendents methods variadic is the easiest way to add access to that via the API with no changes in existing callers. We can use this from terraform to avoid repeatedly walking overlapping sets of nodes.
The existing implementation of parentModuleDependsOn would walk each reference separately, but if there were many dependencies which were all interconnected, that would end up walking over the same nodes multiple times, and storing many duplicate results. Since a graph walk can start at multiple nodes, we use the extended version of Ancestors to start at all dependencies simultaneously, reducing the time spend traversing the graph as well as automatically removing duplicates.
jbardin
added
the
1.8-backport
|
Reminder for the merging maintainer: if this is a user-visible change, please update the changelog on the appropriate release branch. |
|
Amazing! now Terraform faster than ever on large graph!. Thanks |
|
I had this issue without understand really why If I did a plan or an apply locally, the plan|apply took ~1m30 on a large graph (>2'000 resources) And then I removed by coincidence the more So I was suspecting an issue on Azure Devops runner because everything came back to normal. Anyway, good news because now my plan run in ~20 sec for ~2'500 resources... |
The use of
depends_onin modules can cause large numbers of nodes to become connected to all of the same dependencies. When usingAncestorsto walk the graph and find all of these dependencies, there can be a lot of redundant ancestors shared between each of the original nodes, causing an exponential increase in processing time and memory use.Instead of traversing the graph from each dependency individually, which can frequently end up duplicating results, we can start a walk from all nodes at once, reducing the redundant graph traversals and automatically removing duplicates.
Fixes #35154
Target Release
v1.8.4