From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id AD7C0384EF72 for ; Fri, 25 Nov 2022 16:44:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AD7C0384EF72 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id E9BF21FD81 for ; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1669394663; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=d+gx9wyJMaoCVxWUO6RjlmI/VC/jfTqhPH9ribFVyL4=; b=g9RL/lA97BAQcMIIm/DaJT41oSFKdElR2e9pwaAsat0d1cWkhxtF6cwrLMAqCpMxKKgXQ8 Sxxj1Wiz6nwharKv1XfXkj05IE9YI93Hv8feA5ZSbxEuVdMPJK7BfRkdBNPkm6CDme0/d3 FXAJuEK/mPJTo5jOuKotzkUrm2AwcEg= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1669394663; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=d+gx9wyJMaoCVxWUO6RjlmI/VC/jfTqhPH9ribFVyL4=; b=wHVqu+AW9Y4sZIU9TPnLTDe+/iL0dD3ahnWpz0TajFxt2k+PH/+agZEzhZvvJXQzG7eJAD bxJYhh9keFxG0+Aw== Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id E569C2C141 for ; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) Received: by wotan.suse.de (Postfix, from userid 10510) id DDCE46586; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by wotan.suse.de (Postfix) with ESMTP id DBF1A6238 for ; Fri, 25 Nov 2022 16:44:23 +0000 (UTC) Date: Fri, 25 Nov 2022 16:44:23 +0000 (UTC) From: Michael Matz To: binutils@sourceware.org Subject: [PATCH 0/8] ld: Speed up section selection Message-ID: User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-3.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Hello, so this series rewrites how ld selects sections, i.e. how the globs inside linker scripts are evaluated. My speed testcase is always linking cc1, a reasonably sized c++ program with many input files and sections (due to templates and section groups). I will use x86-64. The characteristics of that testcase are: * 674 input files * 300050 input sections * 129 wild statements in the linker script * 179 section selecttors in these wild statements (not all of them globs) With an -O2 build ld.bfd we start with this before the series: overall link time: 4.2823 +- 0.0188 seconds time elapsed ( +- 0.44% ) relevant pieces of the profile (overall this has 16900 samples): percentage Samples program shared object symbol name 5.82% 937 ld-new ld-new walk_wild_section_specs3_wild2 4.45% 718 ld-new ld-new walk_wild_section_specs1_wild1 2.97% 480 ld-new ld-new walk_wild_section_specs2_wild1 1.97% 317 ld-new ld-new walk_wild_section_general 0.85% 137 ld-new ld-new match_simple_wild After the series this will be: overall link time: 3.62733 +- 0.00779 seconds time elapsed ( +- 0.21% ) relevant pieces of the profile (overall this has 14244 samples): percentage Samples program shared object symbol name 0.67% 97 ld-new ld-new resolve_wild_sections.part.0 Yep, that's it, 97 samples remain from the initial 2500 samples for the whole of section selection. I have further patches that speedup GNU ld, but this series is only about the section selection process, which is the second top-most profile entry and the only code taking considerable time that isn't in libbfd. The way the series works is to first reshuffle the order of the overall loop structure matching all sections against all wild statements. Then we can memoize these results (which needs some adjustments), then we can use a prefix tree to quickly rule out possible matches, and then we cleaup. For review purpose I decided to not merge together some of the patches in the series. In particular it adds some interface into libbfd (in 2/8) that gets removed again later (in 7/8). Also the patches adding functionality often only comment out the old variants that are then only removed in a later patch. I think in this case that makes it easier to review (I looked at the overall squashed patch and it's quite confusing). I will also have a question in 4/8 whose answer might make the bfd change useful, so that it wouldn't have to be removed. I've tested the whole series without regression on all of Alans targets (158 of them). So, okay for master? :) Ciao, Michael. Michael Matz (8): section-select: Lazily resolve section matches section-select: Deal with sections added late section-select: Implement a prefix-tree section-select: Completely rebuild matches section-select: Remove unused code section-select: Cleanup section-select: Remove bfd_max_section_id again section-select: Fix exclude-file-3 ld/ldlang.c | 672 +++++++++------------ ld/ldlang.h | 13 +- ld/testsuite/ld-scripts/exclude-file-3.map | 4 +- 3 files changed, 295 insertions(+), 394 deletions(-) -- 2.36.1