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

["Ondřej Bílka" <neleai@seznam.cz>]

On Tue, Apr 02, 2013 at 09:54:17AM +0000, dhatch at ilm dot com wrote:
> 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

How did you get these numbers? Directed graph on 4 nodes has 12 arcs. So
there only 2^{12} = 4096 directed graphs on 4 nodes. What extra data do you
need to generate?

> (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).
>
First optimization would be eliminate isomorphic graphs. I could assist
if I got code.