From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23965 invoked by alias); 2 Apr 2013 09:54:25 -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 23916 invoked by uid 48); 2 Apr 2013 09:54:18 -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 09:54: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/msg00007.txt.bz2 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 (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). As Carlos pointed out in the referenced email thread, this test would have prevented the last several generations of bugs in these sorting routines, and it should help ensure that the impending overhaul properly fixes the bugs it intends to fix, without introducing new ones, and that no similar bugs appear in the future. In addition to lots of expected failures of _dl_sort_fini due to bug 15311, the testing of _dl_sort_init on graphs up to 4 nodes revealed that the existing algorithm doesn't keep SCCs contiguous, which was a surprise to me. I just opened bug 15329 on that. (Not sure whether that's technically a bug... but it's certainly not a nice behavior, and we can do better.) Is it okay to add a test that currently fails due to bugs that we intend to fix very soon? -- 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.