From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 4898 invoked by alias); 26 Nov 2014 16:41:57 -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 4829 invoked by uid 48); 26 Nov 2014 16:41:51 -0000 From: "carlos at redhat dot com" To: glibc-bugs@sourceware.org Subject: [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies. Date: Wed, 26 Nov 2014 16:41: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-Version: unspecified X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: carlos at redhat 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-Flags: X-Bugzilla-Changed-Fields: cc Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-Bugzilla-URL: http://sourceware.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-SW-Source: 2014-11/txt/msg00204.txt.bz2 https://sourceware.org/bugzilla/show_bug.cgi?id=17645 Carlos O'Donell changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |carlos at redhat dot com --- Comment #4 from Carlos O'Donell --- (In reply to Paulo Andrade from comment #1) > Created attachment 7972 [details] > Proposed patch > > This patch implements a simple stable topological sort that moves > an entry at most once, by keeping track of, and resetting the weight > of the entries after every move. It breaks loops by choosing the > ones that appear first with the lowest weight, that is, less > dependencies. > If there is a loop, the "c" variable in the "sort" function will > be larger than 0. At the high-level your patch is almost ready. You refactor the sorting code out into a static function that the compiler can inline and you use the same pattern in all places where sorting happens. This is good. You are missing two important things: * More code comments. You should comment each sort routine with a high-level comment about what you're doing and why. This is particularly important for the weight functions. * Tests. The existing set of tests are insufficient to cover the changes you are proposing. While it seems unfair, and I understand that, this kind of change has not been undertaken because of the lack of testing. You need to add more tests. The *best* testing is actually a test which deterministically generates a sequence of permutations of linked objects and verifies they are sorted correctly by the algorithms in question. This way we can show that the sorting works for a large set of object dependency orderings. When we get a bug report, and we will, we can enlarge the set of automated testing to include the case the bug report claims and see what went wrong. If you can cover those two things, then you're ready to post the patch to libc-alpha for more formal review. This looks really good though and you're making great progress in a difficult part of the dynamic loader. -- You are receiving this mail because: You are on the CC list for the bug.