This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos
- From: "neleai at seznam dot cz" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sourceware dot org
- Date: Tue, 02 Apr 2013 11:31:00 +0000
- Subject: [Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos
- Auto-submitted: auto-generated
- References: <bug-15310-131 at http dot sourceware dot org/bugzilla/>
http://sourceware.org/bugzilla/show_bug.cgi?id=15310
--- Comment #16 from Ondrej Bilka <neleai at seznam dot cz> 2013-04-02 11:31:00 UTC ---
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.
--
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.