From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 7915 invoked by alias); 2 Apr 2013 11:31:06 -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 7810 invoked by uid 89); 2 Apr 2013 11:30:59 -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; Tue, 02 Apr 2013 11:30:55 +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 59EF950542; Tue, 2 Apr 2013 13:30:51 +0200 (CEST) Received: by domone.kolej.mff.cuni.cz (Postfix, from userid 1000) id D2F416046C; Tue, 2 Apr 2013 13:30:46 +0200 (CEST) Date: Tue, 02 Apr 2013 11:31:00 -0000 From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= To: dhatch at ilm dot com 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: <20130402113046.GA5823@domone.kolej.mff.cuni.cz> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) X-SW-Source: 2013-04/txt/msg00009.txt.bz2 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.