This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
Re: [Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos
- From: OndÅej BÃlka <neleai at seznam dot cz>
- To: dhatch at ilm dot com <sourceware-bugzilla at sourceware dot org>
- Cc: glibc-bugs at sourceware dot org
- Date: Tue, 2 Apr 2013 13:30:46 +0200
- Subject: Re: [Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos
- References: <bug-15310-131 at http dot sourceware dot org/bugzilla/> <bug-15310-131-cb1jx9aFjN at http dot sourceware dot org/bugzilla/>
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.