[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

["carlos at redhat dot com" <sourceware-bugzilla at sourceware dot org>]

https://sourceware.org/bugzilla/show_bug.cgi?id=17645

Carlos O'Donell <carlos at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |carlos at redhat dot com

--- Comment #4 from Carlos O'Donell <carlos at redhat dot com> ---
(In reply to Paulo Andrade from comment #1)
> Created attachment 7972 [details]
> Proposed patch
> 
> This patch implements a simple stable topological sort that moves
> an entry at most once, by keeping track of, and resetting the weight
> of the entries after every move. It breaks loops by choosing the
> ones that appear first with the lowest weight, that is, less
> dependencies.
> If there is a loop, the "c" variable in the "sort" function will
> be larger than 0.

At the high-level your patch is almost ready.

You refactor the sorting code out into a static function that the compiler can
inline and you use the same pattern in all places where sorting happens. This
is good.

You are missing two important things:

* More code comments. You should comment each sort routine with a high-level
comment about what you're doing and why. This is particularly important for the
weight functions.

* Tests. The existing set of tests are insufficient to cover the changes you
are proposing. While it seems unfair, and I understand that, this kind of
change has not been undertaken because of the lack of testing. You need to add
more tests. The *best* testing is actually a test which deterministically
generates a sequence of permutations of linked objects and verifies they are
sorted correctly by the algorithms in question. This way we can show that the
sorting works for a large set of object dependency orderings. When we get a bug
report, and we will, we can enlarge the set of automated testing to include the
case the bug report claims and see what went wrong.

If you can cover those two things, then you're ready to post the patch to
libc-alpha for more formal review.

This looks really good though and you're making great progress in a difficult
part of the dynamic loader.

-- 
You are receiving this mail because:
You are on the CC list for the bug.