From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 6691 invoked by alias); 28 Mar 2013 07:42:39 -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 6457 invoked by uid 55); 28 Mar 2013 07:42:32 -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: Thu, 28 Mar 2013 07:42: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-03/txt/msg00165.txt.bz2 http://sourceware.org/bugzilla/show_bug.cgi?id=15310 --- Comment #10 from Ondrej Bilka 2013-03-28 07:42:31 UTC --- On Thu, Mar 28, 2013 at 12:31:40AM +0000, dhatch at ilm dot com wrote: > I hadn't thought about creating the graph structure explicitly as you > suggest... > arguably that would result in cleaner topsort code, but > I was just going to work directly with the data structure that's > already there instead. > Note that an explicit auxiliary graph representation would have size O(N+E) > (number of nodes plus number of edges) > whereas the size of needed auxiliary structures is currently only O(N) > (making it feasible to allocate them as local variables on the runtime stack) > and I wasn't planning on changing that. > I mainly wanted do it to separate alg from domain specific bits. Next one where I do not know if its necesarry or just optimization is /* We can skip looking for the binary itself which is at the front of the search list for the main namespace. */ -- 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.