From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8171 invoked by alias); 2 Apr 2013 11:31:09 -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 7865 invoked by uid 55); 2 Apr 2013 11:31:01 -0000 From: "neleai at seznam dot cz" 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 11:31: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: neleai at seznam dot cz 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/msg00010.txt.bz2 http://sourceware.org/bugzilla/show_bug.cgi?id=15310 --- Comment #16 from Ondrej Bilka 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 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.