[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 #15 from Don Hatch <dhatch at ilm dot com> 2013-04-02 09:54:17 UTC ---
Progress on unit/stress test...
I got something working, in such a way that it can go cleanly into the build
(assuming the init sort has been separated out into a function,
as in my "Proposed initial patch" attachment).
I'll submit the test as soon as I get it polished (and I get legally cleared).

It tests _dl_sort_init on all 17854749 graphs of up to 4 nodes in 1min8sec,
and _dl_sort_fini on all 16777846 pairs of graphs
(static dep graph and dynamic dep graph) of up to 3 nodes in 48sec
(on an Intel Xeon L5630 @ 2.13GHz which is a pretty fast machine I guess).
That's probably a bit long for a confidence test run during "make check",
so for that, I'd probably do something less,
augmented by some randomized testing (with deterministic seed of course).

As Carlos pointed out in the referenced email thread,
this test would have prevented the last several generations
of bugs in these sorting routines, and it should help ensure that
the impending overhaul properly fixes the bugs it intends to fix, without
introducing new ones, and that no similar bugs appear in the future.

In addition to lots of expected failures of _dl_sort_fini due to bug 15311,
the testing of _dl_sort_init on graphs up to 4 nodes
revealed that the existing algorithm doesn't keep SCCs contiguous,
which was a surprise to me.  I just opened bug 15329 on that.
(Not sure whether that's technically a bug... but it's certainly
not a nice behavior, and we can do better.)

Is it okay to add a test that currently fails
due to bugs that we intend to fix very soon?

-- 
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.