From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14336 invoked by alias); 17 Dec 2019 11:06:14 -0000 Mailing-List: contact dwz-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Post: List-Help: List-Subscribe: Sender: dwz-owner@sourceware.org Received: (qmail 14327 invoked by uid 89); 17 Dec 2019 11:06:13 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Checked: by ClamAV 0.100.3 on sourceware.org X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.2 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 spammy= X-Spam-Status: No, score=-25.2 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on sourceware.org X-Spam-Level: X-HELO: mx2.suse.de X-Virus-Scanned: by amavisd-new at test-mx.suse.de Date: Tue, 01 Jan 2019 00:00:00 -0000 From: Tom de Vries To: dwz@sourceware.org, jakub@redhat.com Subject: [committed] Use incoming_tail for superset/subset in create_import_tree Message-ID: <20191217110607.GA17838@delia> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.10.1 (2018-07-13) X-SW-Source: 2019-q4/txt/msg00165.txt.bz2 Hi, Use the new incoming_tail field of struct import_cu to speed up the superset/subset test in create_import_tree. [ The baseline for the measurements is the commit before the incoming_tail field addition. The incoming_tail commit is separate from this one, in order to allow easy identification of performance regressions specifically related to that commit. But we measure here the performance of the two commits combined. ] This reduces execution time for vmlinux with ~38%: ... real: mean: 26802.80 100.00% stddev: 582.58 mean: 16590.60 61.90% stddev: 92.71 user: mean: 26271.80 100.00% stddev: 207.98 mean: 16278.80 61.96% stddev: 86.84 sys: mean: 392.00 100.00% stddev: 177.20 mean: 310.40 79.18% stddev: 28.09 ... This at the cost of 0.01% more memory: ... $ time.sh ./dwz.1 vmlinux.debug -lnone -Lnone maxmem: 2163948 real: 26.96 user: 26.60 system: 0.35 $ time.sh ./dwz.2 vmlinux.debug -lnone -Lnone maxmem: 2164120 real: 16.63 user: 16.30 system: 0.32 ... Committed to trunk. Thanks, - Tom Use incoming_tail for superset/subset in create_import_tree 2019-12-17 Tom de Vries PR dwz/25276 * dwz.c (create_import_tree): Use incoming_tail to speed up calculation of maybe_superset and maybe_subset. --- dwz.c | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/dwz.c b/dwz.c index 82b7d83..48833bc 100644 --- a/dwz.c +++ b/dwz.c @@ -7318,6 +7318,26 @@ create_import_tree (void) maybe_subset = (e1 == ipu->incoming && ipu->incoming_count <= ipu2->incoming_count); maybe_superset = ipu->incoming_count >= ipu2->incoming_count; + if (maybe_superset) + { + /* If the referrer nodes of ipu are a superset of the + referrer nodes of ipu2, then ipu's last referrer node + should have index larger or equal to the last referrer + node of ipu2. */ + maybe_superset + = (ipu->incoming_tail->icu->idx + >= ipu2->incoming_tail->icu->idx); + } + if (maybe_subset) + { + /* If the referrer nodes of ipu are a subset of the + referrer nodes of ipu2, then ipu's last referrer node + should have index smaller or equal to the last referrer + node of ipu2. */ + maybe_subset + = (ipu->incoming_tail->icu->idx + <= ipu2->incoming_tail->icu->idx); + } e3 = e1; e4 = ipu2->incoming; intersection = 0;