[PATCH 1/1] Improve performance of package list expansion.
Matthew Hanna (BLOOMBERG/ 731 LEX)
mhanna21 at bloomberg.net
Sat Jun 18 13:23:00 UTC 2016
In practice, for library sets with a high degree of dependency, iteration over the tree with revisiting results in significant slow down at best and pkg-config failure due to memory exhaustion at worst. This patch replaces the 'in_requires_chain' flag that halted circular dependencies with a hash table that marks visited package nodes. The resulting algorithm is equivalent to a topological sort. Although a boolean flag on each node could be used to implement the algorithm, resetting the flag to false can only be done after the algorithm is complete, creating a bit of extra bookkeeping. Instead, I chose to use a new hash table to record the visits, reducing the bookkeeping to a call to 'g_hash_table_destroy'.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the pkg-config