From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 4060 invoked by alias); 27 Mar 2013 20:33:33 -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 4025 invoked by uid 48); 27 Mar 2013 20:33:24 -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: Wed, 27 Mar 2013 20:33: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: NEW 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-03/txt/msg00145.txt.bz2 http://sourceware.org/bugzilla/show_bug.cgi?id=15310 --- Comment #3 from Don Hatch 2013-03-27 20:33:23 UTC --- (In reply to comment #2) > Don, > > I agree that the sorting could be made *far* faster. > > Thanks for submitting this. We were well aware that the minimal fix for bug > 13882 would cause some kind of performance regression, but it was a balance > between a minimal fix and low risk of breakage. I reviewed the patch for 13882 > and even build a minimal framework for testing that dynamic loader function > outside of the build. > > Do you have the time to investigate this and propose a patch (requires > copyright assignment)? I do. I am working on a patch that resolves both this and bug 15311, and I'll submit it here in a day or two. I am very interested in what you came up with in the way of a unit testing scheme for this function... I could certainly use it. I've found it frustrating that the existing tests run by "make check" (the ones I saw anyway) involve just creating/compiling/running a handful of real programs... to really stress test an implementation of _dl_sort_fini properly, I'd want to (at least) enumerate all possible graphs of up to 3 or 4 nodes, and call it on each of them, which would be millions of examples... and a few million randomly generated larger examples as well. It's *really* easy to get this stuff wrong otherwise. Also I'd like to start by moving the init sorting code into a function. It looks to me like this code is duplicated in two places (dl-open.c and dl-deps.c), and (after the fix for bug 15309) it's identical in both places except that one of them starts at i0=0 and the other starts at i0=1. So this could be expressed cleanly as a new function _dl_sort_init that takes i0 as a parameter. Should I start by submitting a patch that does that, with no functional change, and go from there? Or should I let you or someone else do this refactoring (possibly in conjunction with making these sorting functions unit testable)? Let me know how to proceed. -- 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.