(#9617) Keep track of blockers for resources when traversing
Upon application of a resource previously, we would iterate its
dependents and check if each of their dependencies were done, to
determine which dependent resources were now ready to run.
This is extremely slow in certain cases, such as when some resource X
depends on a recursive file resource with thousands of generated
children. In that case, each time any of the thousands of children was
applied, we would check the thousands of dependencies of X.
Now, we take advantage of the fact that the dependency graph only
changes when resources are eval_generated. Thus, we can compute and
store the number of unfinished dependencies for each resource. Then,
when a resource completes, we need only visit each dependent and
decrement its blocker count. When that count is 0, the resource is ready
to run.
While it would theoretically be possible to also track changes to
dependencies by eval_generate, doing so would add significantly more
complexity to an already complex method. For now, we are opting to
simply clear the blocker counts and recalculate them when needed, if
eval_generate adds resources. If this proves to be a significant
performance benefit in future, we can revisit it.
Paired-With: Josh Cooper <josh@puppetlabs.com>