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

["dhatch at ilm dot com" <sourceware-bugzilla at sourceware dot org>]

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.