public inbox for glibc-bugs@sourceware.org help / color / mirror / Atom feed
From: "dhatch at ilm dot com" <sourceware-bugzilla@sourceware.org> 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 [thread overview] Message-ID: <bug-15310-131@http.sourceware.org/bugzilla/> (raw) 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.
next reply other threads:[~2013-03-27 7:47 UTC|newest] Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top 2013-03-27 7:47 dhatch at ilm dot com [this message] 2013-03-27 8:12 ` [Bug dynamic-link/15310] " dhatch at ilm dot com 2013-03-27 8:45 ` dhatch at ilm dot com 2013-03-27 12:57 ` carlos at redhat dot com 2013-03-27 14:19 ` ppluzhnikov at google dot com 2013-03-27 20:33 ` dhatch at ilm dot com 2013-03-27 20:50 ` neleai at seznam dot cz 2013-03-27 20:50 ` [Bug dynamic-link/15310] New: " Ondřej Bílka 2013-03-27 21:00 ` [Bug dynamic-link/15310] " carlos at redhat dot com 2013-03-27 21:07 ` carlos at redhat dot com 2013-03-27 21:13 ` law at redhat dot com 2013-03-27 23:44 ` dhatch at ilm dot com 2013-03-28 0:31 ` dhatch at ilm dot com 2013-03-28 7:42 ` Ondřej Bílka 2013-03-28 7:42 ` neleai at seznam dot cz 2013-03-28 10:00 ` dhatch at ilm dot com 2013-03-28 10:19 ` dhatch at ilm dot com 2013-03-28 17:09 ` law at redhat dot com 2013-03-28 17:31 ` dhatch at ilm dot com 2013-04-02 9:54 ` dhatch at ilm dot com 2013-04-02 11:31 ` Ondřej Bílka 2013-04-02 11:31 ` neleai at seznam dot cz 2013-04-02 13:07 ` dhatch at ilm dot com 2013-04-02 23:37 ` dhatch at ilm dot com 2013-04-03 7:57 ` Ondřej Bílka 2013-04-03 7:57 ` neleai at seznam dot cz 2013-04-06 21:07 ` carlos at redhat dot com 2014-06-13 13:51 ` fweimer at redhat dot com 2014-06-13 18:37 ` fweimer at redhat dot com 2021-10-27 14:58 ` adhemerval.zanella at linaro dot org 2021-10-27 14:59 ` adhemerval.zanella at linaro dot org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-15310-131@http.sourceware.org/bugzilla/ \ --to=sourceware-bugzilla@sourceware.org \ --cc=glibc-bugs@sourceware.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).