From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12856 invoked by alias); 27 Mar 2013 07:47:53 -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 12827 invoked by uid 48); 27 Mar 2013 07:47:46 -0000 From: "dhatch at ilm dot com" To: glibc-bugs@sourceware.org Subject: [Bug dynamic-link/15310] New: _dl_sort_fini is O(n^3) causing slow exit when many dsos Date: Wed, 27 Mar 2013 07:47:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new 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: 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/msg00124.txt.bz2 http://sourceware.org/bugzilla/show_bug.cgi?id=15310 Bug #: 15310 Summary: _dl_sort_fini is O(n^3) causing slow exit when many dsos Product: glibc Version: unspecified Status: NEW Severity: critical Priority: P2 Component: dynamic-link AssignedTo: unassigned@sourceware.org ReportedBy: dhatch@ilm.com Classification: Unclassified The fix for Bug 13882 ("Cycle detection in dynamic loader is broken ") fixed premature termination of the inner loop of _dl_sort_fini, making the function (closer to) correct, but it also changes this function's runtime from O(n^2) to O(n^3) where n is the number of items (resident DSOs) to be sorted. (The same is true for the corresponding init sorts in dl-open.c and dl-deps.c.) This can be readily seen by looking at Jeff Law's example in the description of bug 13882 (a linear chain of dependencies that _dl_sort_fini needs to completely reverse). In this case, each of O(n) objects gets moved O(n) times; furthermore the analysis leading to each such move (as well as the move itself) takes O(n) time. That's O(n)*O(n)*O(n) = O(n^3). Another easy way to get O(n^3) behavior is with cycles: any node that's part of a nontrivial cycle is guaranteed to keep getting moved repeatedly until its moved-too-many-times counter expires, which is O(n) times (for O(n) of the items anyway). So for example, if the dependency graph consists of mutually dependent pairs of DSOs: A<->B C<->D E<->F ... that will result in O(n^3) run time as well. We observed the O(n^3) behavior in real life, in our application that had 575 DSOs upon exit-- in RHEL5.3 (glibc 2.5), it took less than 1 second to exit; upon upgrading to RHEL6.3 (glibc 2.12), the same app took 15 seconds to exit. Instrumenting _dl_sort_fini (i.e. putting a counter in it and printing it at the end) revealed that the innermost loop body was entered more than 1.7 billion times, roughly confirming the O(n^3) claim in practice. This is just a topsort, which can be done simply in O(n) time with no fancy data structures. -- 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.