From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <glibc-bugs-return-18265-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Received: (qmail 6490 invoked by alias); 28 Mar 2013 07:42:37 -0000
Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <glibc-bugs.sourceware.org>
List-Subscribe: <mailto:glibc-bugs-subscribe@sourceware.org>
List-Post: <mailto:glibc-bugs@sourceware.org>
List-Help: <mailto:glibc-bugs-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: glibc-bugs-owner@sourceware.org
Received: (qmail 6412 invoked by uid 89); 28 Mar 2013 07:42:30 -0000
X-Spam-SWARE-Status: No, score=-0.8 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,SPF_NEUTRAL autolearn=no version=3.3.1
X-Spam-User: qpsmtpd, 2 recipients
Received: from popelka.ms.mff.cuni.cz (HELO popelka.ms.mff.cuni.cz) (195.113.20.131)    by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Thu, 28 Mar 2013 07:42:28 +0000
Received: from domone.kolej.mff.cuni.cz (popelka.ms.mff.cuni.cz [195.113.20.131])	by popelka.ms.mff.cuni.cz (Postfix) with ESMTPS id E31EC51FFD;	Thu, 28 Mar 2013 08:42:19 +0100 (CET)
Received: by domone.kolej.mff.cuni.cz (Postfix, from userid 1000)	id E1F3F6045C; Thu, 28 Mar 2013 08:37:48 +0100 (CET)
Date: Thu, 28 Mar 2013 07:42:00 -0000
From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= <neleai@seznam.cz>
To: dhatch at ilm dot com <sourceware-bugzilla@sourceware.org>
Cc: glibc-bugs@sourceware.org
Subject: Re: [Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos
Message-ID: <20130328073748.GB4879@domone.kolej.mff.cuni.cz>
References: <bug-15310-131@http.sourceware.org/bugzilla/> <bug-15310-131-D5nN3rhVfh@http.sourceware.org/bugzilla/>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <bug-15310-131-D5nN3rhVfh@http.sourceware.org/bugzilla/>
User-Agent: Mutt/1.5.20 (2009-06-14)
X-SW-Source: 2013-03/txt/msg00164.txt.bz2

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.  */