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

[Dan Nicholson]

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
>