<html><head><title></title></head><body><div class="rte-style-maintainer" style="font-family: Arial; white-space: pre-wrap; font-size: small; color: rgb(0, 0, 0);"data-color="global-default" bbg-color="default" data-bb-font-size="medium" bbg-font-size="medium" bbg-font-family="normal">I have added some tests to verify the proposed implementation. The duplicate<div>removal appears to be unnecessary. Even if the initial list has duplicates,</div><div>the visited check will prevent duplicates from appearing on the output</div><div>dependency list.</div><div> </div><div>Thanks,</div><div>Matthew</div><div class="rte-style-maintainer" style="font-size: small; font-family: 'Courier New', Courier; color: rgb(0, 0, 0);"data-color="global-default" bbg-color="default" data-bb-font-size="medium" bbg-font-size="medium" bbg-font-family="fixed-width"> <div class="bbg-rte-fold-content" data-header="From: nicholson@endlessm.com At: 07/26/16 10:57:35" data-digest="From: nicholson@endlessm.com At: 07/26/16 10:57:35" style=""><div class="bbg-rte-fold-summary">From: nicholson@endlessm.com At: 07/26/16 10:57:35</div><div>To: <a spellcheck="false" bbg-destination="mailto:mhanna21@bloomberg.net" href="mailto:mhanna21@bloomberg.net">Matthew Hanna (BLOOMBERG/ 731 LEX)</a> Cc: <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org">pkg-config@lists.freedesktop.org</a> Subject: Re: Re: [PATCH 1/1] Improve performance of package list expansion. </div></div><blockquote>That looks a lot better, but there's one thing that I'm concerned about. The way this is setup here, once a pkg is in the hash table, it's no longer added to the recursive list. Previously, the in_requires_chain setting was reset as the chain was unwound. In most cases, I don't think this change is significant, but I recall this being important when I was doing the in_requires_chain work initially. What I think might be a problem is the final sorting of packages. See the comment following the call to recursive_fill_list in fill_list: /* Remove duplicate packages from the recursive list. This should provide a * serialized package list where all interdependencies are resolved * consistently. */ This would only work if we allow the duplicates in the first place. That won't happen any more with your change. Here's a concrete example. Suppose we have package test that requires a and b. a and b both depend on c. When resolving the package list for test, it should end up being "a b c". We want c at the end because both a and be depend on it. Currently, the package list would be built as "a c b c" and then duplicates would be stripped starting at the end so that you end with "a b c". With your change, the original list would be "a c b" and then there are no duplicates to strip. I don't know if there's a test covering this (there should be), but I think the packges should be removed from visited as the chain is unwound. Dan -- Dan Nicholson | +1.206.437.0833 | Endless On Mon, Jul 11, 2016 at 3:34 PM, Matthew Hanna (BLOOMBERG/ 731 LEX) <<a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:mhanna21@bloomberg.net" data-destination="mailto:rte:bind">mhanna21@bloomberg.net</a>> wrote: > Works for me. Attached is a revised patch that incorporates your > suggestions. > > Thanks, > Matthew > > From: <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:nicholson@endlessm.com" data-destination="mailto:rte:bind">nicholson@endlessm.com</a> At: 07/08/16 19:19:15 > To: MATTHEW HANNA (BLOOMBERG/ 731 LEX), <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> > > Subject: Re: [PATCH 1/1] Improve performance of package list expansion. > > That looks like a nice fix. I guess I only ever tested this with a small > set of packages. However, I think I'd like it reworked a bit. Since > there are only 2 callers, I'd prefer to have them create the hash table > and pass it to recursive_fill_list. Then you also don't need to create 2 > versions of the static helper function. I also don't see a great reason > to change the function name, but I guess I don't feel that strongly > about that. > > Thanks, > Dan > > On Sun, 2016-06-19 at 12:57 +0000, Matthew Hanna (BLOOMBERG/ 731 LEX) > wrote: >> Thanks for the quick reply. Yes, I forgot to attach it. Should be >> attached now. >> >> Matthew >> >> From: <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:nicholson@endlessm.com" data-destination="mailto:rte:bind">nicholson@endlessm.com</a> At: Jun 18 2016 10:19:35 >> To: MATTHEW HANNA (BLOOMBERG/ 731 LEX) >> Cc: <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> >> Subject: Re: [PATCH 1/1] Improve performance of package list >> expansion. >> Hi Matthew, >> I don't see the patch. Did you forget to attach it? >> Dan >> On Jun 18, 2016 6:31 AM, "Matthew Hanna (BLOOMBERG/ 731 LEX)" <mhanna2 >> <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:1@bloomberg.net"data-destination="mailto:rte:bind">1@bloomberg.net</a>> wrote: >> > 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'. >> > >> > _______________________________________________ >> > pkg-config mailing list >> > <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> >> > <a bbg-destination="rte:bind"spellcheck="false" href="https://lists.freedesktop.org/mailman/listinfo/pkg-config"data-destination="rte:bind">https://lists.freedesktop.org/mailman/listinfo/pkg-config</a> >> > >> _______________________________________________ >> pkg-config mailing list >> <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> >> <a bbg-destination="rte:bind"spellcheck="false" href="https://lists.freedesktop.org/mailman/listinfo/pkg-config"data-destination="rte:bind">https://lists.freedesktop.org/mailman/listinfo/pkg-config</a> >> _______________________________________________ >> pkg-config mailing list >> <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> >> <a bbg-destination="rte:bind"spellcheck="false" href="https://lists.freedesktop.org/mailman/listinfo/pkg-config"data-destination="rte:bind">https://lists.freedesktop.org/mailman/listinfo/pkg-config</a> > _______________________________________________ > pkg-config mailing list > <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> > <a bbg-destination="rte:bind"spellcheck="false" href="https://lists.freedesktop.org/mailman/listinfo/pkg-config"data-destination="rte:bind">https://lists.freedesktop.org/mailman/listinfo/pkg-config</a> > > > _______________________________________________ > pkg-config mailing list > <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> > <a bbg-destination="rte:bind"spellcheck="false" href="https://lists.freedesktop.org/mailman/listinfo/pkg-config"data-destination="rte:bind">https://lists.freedesktop.org/mailman/listinfo/pkg-config</a> > _______________________________________________ pkg-config mailing list <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org" data-destination="mailto:rte:bind">pkg-config@lists.freedesktop.org</a> <a bbg-destination="rte:bind"spellcheck="false" href="https://lists.freedesktop.org/mailman/listinfo/pkg-config"data-destination="rte:bind">https://lists.freedesktop.org/mailman/listinfo/pkg-config</a> </blockquote> </div></div></body></html>