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

[Dan Nicholson]

Hi Matthew,

Sorry for the super slow response. Between vacation and a busy release
at work, I didn't have time to get back to this. I had to go back and
refresh my understanding of the package filling and sorting code, but
this is definitely a win and seems to do the right thing. The tests
were a big help. I stripped some trailing whitespace from your commit
and added one to remove the unused package_list_strip_duplicates
function. This is on master now.

Thanks!
--
Dan Nicholson  |  +1.206.437.0833  |  Endless


On Wed, Jul 27, 2016 at 5:20 AM, Matthew Hanna (BLOOMBERG/ 731 LEX)
<mhanna21 at bloomberg.net> wrote:
> I have added some tests to verify the proposed implementation. The duplicate
> removal appears to be unnecessary. Even if the initial list has duplicates,
> the visited check will prevent duplicates from appearing on the output
> dependency list.
>
> Thanks,
> 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
>
>
>
> _______________________________________________
> pkg-config mailing list
> pkg-config at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/pkg-config
>