<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">The loop in 'recursive_fill_list' is reversed. So if I have an initial list of<div>'a b', both of which depend on 'c', then the dependencies of 'b' will be</div><div>evaluated first. So 'c' will be added to the output list and then 'b' will be</div><div>prepended, resulting in a temporary value of 'b c'. Then 'a' will be processed</div><div>and nothing will be done regarding 'c' since it has already been visited, so</div><div>'a' will be prepended, resulting in a final output of 'a b c'. I will add some</div><div>tests to determine whether my proposed patch is equivalent to the existing</div><div>behavior.</div><div><br></div><div>If this patch is correct, then the duplicate removal is not strictly needed. I</div><div>wasn't sure what to do about the duplicate removal, but I left it in since I</div><div>think the initial list of packages itself might have duplicates and I decided</div><div>to preserve existing behavior. For this patch, the comment should be changed</div><div>to reflect the code.</div><div><br></div><div>Matthew</div><div><br><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><br>Cc: <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:pkg-config@lists.freedesktop.org">pkg-config@lists.freedesktop.org</a><br>Subject: Re: Re: [PATCH 1/1] Improve performance of package list expansion.<br></div></div><blockquote>That looks a lot better, but there's one thing that I'm concerned<br>about. The way this is setup here, once a pkg is in the hash table,<br>it's no longer added to the recursive list. Previously, the<br>in_requires_chain setting was reset as the chain was unwound. In most<br>cases, I don't think this change is significant, but I recall this<br>being important when I was doing the in_requires_chain work initially.<br><br>What I think might be a problem is the final sorting of packages. See<br>the comment following the call to recursive_fill_list in fill_list:<br><br> /* Remove duplicate packages from the recursive list. This should provide a<br> * serialized package list where all interdependencies are resolved<br> * consistently. */<br><br>This would only work if we allow the duplicates in the first place.<br>That won't happen any more with your change. Here's a concrete<br>example. Suppose we have package test that requires a and b. a and b<br>both depend on c. When resolving the package list for test, it should<br>end up being "a b c". We want c at the end because both a and be<br>depend on it. Currently, the package list would be built as "a c b c"<br>and then duplicates would be stripped starting at the end so that you<br>end with "a b c". With your change, the original list would be "a c b"<br>and then there are no duplicates to strip.<br><br>I don't know if there's a test covering this (there should be), but I<br>think the packges should be removed from visited as the chain is<br>unwound.<br><br><br>Dan<br>--<br>Dan Nicholson | +1.206.437.0833 | Endless<br><br><br>On Mon, Jul 11, 2016 at 3:34 PM, Matthew Hanna (BLOOMBERG/ 731 LEX)<br><<a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:mhanna21@bloomberg.net" data-destination="mailto:rte:bind">mhanna21@bloomberg.net</a>> wrote:<br>> Works for me. Attached is a revised patch that incorporates your<br>> suggestions.<br>><br>> Thanks,<br>> Matthew<br>><br>> 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<br>> 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><br>><br>> Subject: Re: [PATCH 1/1] Improve performance of package list expansion.<br>><br>> That looks like a nice fix. I guess I only ever tested this with a small<br>> set of packages. However, I think I'd like it reworked a bit. Since<br>> there are only 2 callers, I'd prefer to have them create the hash table<br>> and pass it to recursive_fill_list. Then you also don't need to create 2<br>> versions of the static helper function. I also don't see a great reason<br>> to change the function name, but I guess I don't feel that strongly<br>> about that.<br>><br>> Thanks,<br>> Dan<br>><br>> On Sun, 2016-06-19 at 12:57 +0000, Matthew Hanna (BLOOMBERG/ 731 LEX)<br>> wrote:<br>>> Thanks for the quick reply. Yes, I forgot to attach it. Should be<br>>> attached now.<br>>><br>>> Matthew<br>>><br>>> 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<br>>> To: MATTHEW HANNA (BLOOMBERG/ 731 LEX)<br>>> 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><br>>> Subject: Re: [PATCH 1/1] Improve performance of package list<br>>> expansion.<br>>> Hi Matthew,<br>>> I don't see the patch. Did you forget to attach it?<br>>> Dan<br>>> On Jun 18, 2016 6:31 AM, "Matthew Hanna (BLOOMBERG/ 731 LEX)" <mhanna2<br>>> <a spellcheck="false"bbg-destination="mailto:rte:bind" href="mailto:1@bloomberg.net"data-destination="mailto:rte:bind">1@bloomberg.net</a>> wrote:<br>>> > In practice, for library sets with a high degree of dependency,<br>>> > iteration over the tree with revisiting results in significant slow<br>>> > down at best and pkg-config failure due to memory exhaustion at<br>>> > worst. This patch replaces the 'in_requires_chain' flag that halted<br>>> > circular dependencies with a hash table that marks visited package<br>>> > nodes. The resulting algorithm is equivalent to a topological<br>>> > sort. Although a boolean flag on each node could be used to<br>>> > implement the algorithm, resetting the flag to false can only be<br>>> > done after the algorithm is complete, creating a bit of extra<br>>> > bookkeeping. Instead, I chose to use a new hash table to record the<br>>> > visits, reducing the bookkeeping to a call to<br>>> > 'g_hash_table_destroy'.<br>>> ><br>>> > _______________________________________________<br>>> > pkg-config mailing list<br>>> > <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><br>>> > <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><br>>> ><br>>> _______________________________________________<br>>> pkg-config mailing list<br>>> <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><br>>> <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><br>>> _______________________________________________<br>>> pkg-config mailing list<br>>> <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><br>>> <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><br>> _______________________________________________<br>> pkg-config mailing list<br>> <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><br>> <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><br>><br>><br>> _______________________________________________<br>> pkg-config mailing list<br>> <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><br>> <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><br>><br>_______________________________________________<br>pkg-config mailing list<br><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><br><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><br></blockquote><br></div></div></div></body></html>