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: "dhatch at ilm dot com" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sourceware dot org
- Date: Tue, 02 Apr 2013 13:07: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 #17 from Don Hatch <dhatch at ilm dot com> 2013-04-02 13:07:00 UTC ---
(In reply to comment #16)
> >
> > 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?
I was considering the complete graph on 4 nodes to have 16 arcs, not 12,
so there are 2^16 = 65536 possible graphs
(though that might be a worthwhile corner to cut... once we convince ourselves
that an edge from a node to itself doesn't affect the algorithm,
then yes, we could just consider 4096 of them)...
and all permutations of edges lists have to be considered different,
so I was taking the sum, over all 65536 graphs,
of the product of the factorials of the node arities.
(plus similar sums for 0,1,2,3 nodes, though they are small in comparison)
>
> > (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.
I don't think we can eliminate isomorphic graphs.
Whether a bug appears or not often depends on the data order.
--
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.