From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16595 invoked by alias); 2 Apr 2013 13:07:08 -0000 Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: glibc-bugs-owner@sourceware.org Received: (qmail 16520 invoked by uid 48); 2 Apr 2013 13:07:00 -0000 From: "dhatch at ilm dot com" To: glibc-bugs@sourceware.org Subject: [Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos Date: Tue, 02 Apr 2013 13:07:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: glibc X-Bugzilla-Component: dynamic-link X-Bugzilla-Keywords: X-Bugzilla-Severity: critical X-Bugzilla-Who: dhatch at ilm dot com X-Bugzilla-Status: WAITING X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: unassigned at sourceware dot org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: X-Bugzilla-URL: http://sourceware.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 X-SW-Source: 2013-04/txt/msg00011.txt.bz2 http://sourceware.org/bugzilla/show_bug.cgi?id=15310 --- Comment #17 from Don Hatch 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.