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

Wed Jul 27 12:20:48 UTC 2016

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/pkg-config/attachments/20160727/e9913864/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Improve-performance-of-packa.patch
Type: application/octet-stream
Size: 13879 bytes
Desc: not available
URL: <https://lists.freedesktop.org/archives/pkg-config/attachments/20160727/e9913864/attachment-0001.obj>