Re: Re: Re: [PATCH 1/1] Improve performance of package list expansion.

Tue Jul 26 15:55:33 UTC 2016

The loop in 'recursive_fill_list' is reversed.  So if I have an initial list of
'a b', both of which depend on 'c', then the dependencies of 'b' will be
evaluated first.  So 'c' will be added to the output list and then 'b' will be
prepended, resulting in a temporary value of 'b c'.  Then 'a' will be processed
and nothing will be done regarding 'c' since it has already been visited, so
'a' will be prepended, resulting in a final output of 'a b c'.  I will add some
tests to determine whether my proposed patch is equivalent to the existing
behavior.

If this patch is correct, then the duplicate removal is not strictly needed.  I
wasn't sure what to do about the duplicate removal, but I left it in since I
think the initial list of packages itself might have duplicates and I decided
to preserve existing behavior.  For this patch, the comment should be changed
to reflect the code.

Matthew

From: nicholson at endlessm.com At: 07/26/16 10:57:35
To: Matthew Hanna (BLOOMBERG/ 731 LEX)
Cc: pkg-config at lists.freedesktop.org
Subject: Re: Re: [PATCH 1/1] Improve performance of package list expansion.

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)
<mhanna21 at bloomberg.net> wrote:
> Works for me. Attached is a revised patch that incorporates your
> suggestions.
>
> Thanks,
> Matthew
>
> From: nicholson at endlessm.com At: 07/08/16 19:19:15
> To: MATTHEW HANNA (BLOOMBERG/ 731 LEX), pkg-config at lists.freedesktop.org
>
> 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: nicholson at endlessm.com At: Jun 18 2016 10:19:35
>> To: MATTHEW HANNA (BLOOMBERG/ 731 LEX)
>> Cc: pkg-config at lists.freedesktop.org
>> 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
>> 1 at bloomberg.net> 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
>> > pkg-config at lists.freedesktop.org
>> > https://lists.freedesktop.org/mailman/listinfo/pkg-config
>> >
>> _______________________________________________
>> pkg-config mailing list
>> pkg-config at lists.freedesktop.org
>> https://lists.freedesktop.org/mailman/listinfo/pkg-config
>> _______________________________________________
>> pkg-config mailing list
>> pkg-config at lists.freedesktop.org
>> https://lists.freedesktop.org/mailman/listinfo/pkg-config
> _______________________________________________
> pkg-config mailing list
> pkg-config at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/pkg-config
>
>
> _______________________________________________
> pkg-config mailing list
> pkg-config at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/pkg-config
>
_______________________________________________
pkg-config mailing list
pkg-config at lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pkg-config

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/pkg-config/attachments/20160726/1d13e139/attachment-0001.html>