puppetlabs/puppet — pull request #209 by nicklewis (2011-11-11 22:31:08+00:00)
Title: Ticket/2.7rc/9671 Transaction performance improvements 

This branch contains several improvements to the transaction performance, primarily focused around eval_generate, and finding resources to evaluate.

When eval_generating and creating dependencies between generated resources and their dependencies, we now ask each generated resource for its potential ancestors, and check a hash to see if we generated any of them. Previously we would do a linear search (including a string slice per element) for each resource.

We now track the number of blockers for every resource, rather than recalculate them each time a dependency completes. This lets us quickly determine which resources ought to be added to the ready list.

The ready list is now represented as a sorted set (implemented as a red-black tree), rather than sorting the entire list each time we need a resource.