[Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos

["dhatch at ilm dot com" <sourceware-bugzilla@sourceware.org>]

http://sourceware.org/bugzilla/show_bug.cgi?id=15310

--- Comment #3 from Don Hatch <dhatch at ilm dot com> 2013-03-27 20:33:23 UTC ---
(In reply to comment #2)
> Don,
> 
> I agree that the sorting could be made *far* faster.
> 
> Thanks for submitting this. We were well aware that the minimal fix for bug
> 13882 would cause some kind of performance regression, but it was a balance
> between a minimal fix and low risk of breakage. I reviewed the patch for 13882
> and even build a minimal framework for testing that dynamic loader function
> outside of the build.
> 
> Do you have the time to investigate this and propose a patch (requires
> copyright assignment)?

I do. I am working on a patch that resolves both this and bug 15311,
and I'll submit it here in a day or two.

I am very interested in what you came up with in the way of a unit
testing scheme for this function... I could certainly use it.
I've found it frustrating that the existing tests run by "make check"
(the ones I saw anyway)
involve just creating/compiling/running a handful of real programs...
to really stress test an implementation of _dl_sort_fini properly,
I'd want to (at least) enumerate all possible graphs
of up to 3 or 4 nodes, and call it on each of them,
which would be millions of examples...
and a few million randomly generated larger examples as well.
It's *really* easy to get this stuff wrong otherwise.

Also I'd like to start by moving the init sorting code into a function.
It looks to me like this code is duplicated in two places (dl-open.c
and dl-deps.c), and (after the fix for bug 15309)
it's identical in both places except that
one of them starts at i0=0 and the other starts at i0=1.
So this could be expressed cleanly as a new function _dl_sort_init that takes
i0
as a parameter.
Should I start by submitting a patch that does that,
with no functional change, and go from there?  Or should I let you
or someone else do this refactoring (possibly in conjunction
with making these sorting functions unit testable)?
Let me know how to proceed.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.