andrewdavey/cassette — pull request #464 by alex-davidson (2014-12-18 16:23:19+00:00)
Title: Gather and sort dependencies more efficiently.

* It is not necessary to enumerate a bundle's dependencies if it is already present in the set, since they will have been added the first time around.
* We need to traverse the dependency hierarchy in order to construct the set of bundles. By performing a depth-first traversal and always inserting a dependency before the referencing bundle in the list of references, it is possible to collect and sort the bundles in a single pass.

For a single-page application referencing nearly 1000 script files in 40+ bundles, these changes reduce page render time from ~2 seconds to under 0.5 seconds. The algorithm should now be O(n) in the total number of bundles, rather than O(n2).

The BundleCollection_SortBundles tests are currently commented out because sorting is now performed as part of reference collection, therefore SortBundles no longer exists. I think most of the relevant logic is covered by the ReferenceBuilder tests in any case.

I have made the assumption that a given bundle instance is effectively immutable, ie. its References collection won't change between it being referenced by the page's code and the page's content being rendered.