From patchwork Wed Oct 16 13:41:31 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Matz X-Patchwork-Id: 99009 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 231CD3857002 for ; Wed, 16 Oct 2024 13:42:16 +0000 (GMT) X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2a07:de40:b251:101:10:150:64:1]) by sourceware.org (Postfix) with ESMTPS id 156C43858420 for ; Wed, 16 Oct 2024 13:41:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 156C43858420 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 156C43858420 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:1 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729086099; cv=none; b=UaMTlmrs1JkIpRMljC4wi6Cbre1cNK68gfyx92SEu/i7a2xpqSb7MqgAcGIXlJ7Cq6wNGl5gz1kgaojkfNoChlE3tHteWxA9UIfMGbCbv7zNyQjvM8Bv5wtoeS4KnnKYP0LwgMo+nBy1hwD8kWzDYpasui+NDN57VZviMyZD8a4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729086099; c=relaxed/simple; bh=XZsnlHcYjyAg4pmbjI/JF3WHVU0ny6rVBQWc9wL7TYk=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:Message-ID:MIME-Version; b=b3WU85DtZtPtfvNg8DvVahBwjbGE/XPhIMUvX2GNloFJKUEHUoTlv33knAWHyrIHxcS6BueuzwkXKUjNQBmqGFNiObcQ8Nxo9UaOBPqYGP2lMDFEg7P5neaOglUhvAdwCtIlUDsQ0jUy2axpdumdJY22GkQs29BEzDpWyN5++Kc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from knuth.suse.de (unknown [10.168.5.16]) by smtp-out1.suse.de (Postfix) with ESMTP id 308F921E65 for ; Wed, 16 Oct 2024 13:41:31 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1729086091; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=UXqcalwn4S4yHlup2tBJVxgZbxREYH2njWfBxa9BZTE=; b=TKgiCvZXfKR/WbW98H0pcNobhbAxe7r6ayDpTPwnqEBq8HuxnAXXOjJEhCPolEttX7fVxK TmScifFp74FcVLKweEBJlh6DGq1WzZbZYEXQUQnMF/cNFfBwk+unUjM6qv0Lbk3ldaT+00 6UId44miJxxyf+RQ0gtCVKqRmjAmDRI= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1729086091; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=UXqcalwn4S4yHlup2tBJVxgZbxREYH2njWfBxa9BZTE=; b=KG6ouZcLIT/q/Wx6pSA+SgdmqizWWy+vbaySr/5Ulr19Bo8l2+ja6Qf8+cF6ZMhPQkvKF6 CuGqLGIkiCUd4wAQ== Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1729086091; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=UXqcalwn4S4yHlup2tBJVxgZbxREYH2njWfBxa9BZTE=; b=TKgiCvZXfKR/WbW98H0pcNobhbAxe7r6ayDpTPwnqEBq8HuxnAXXOjJEhCPolEttX7fVxK TmScifFp74FcVLKweEBJlh6DGq1WzZbZYEXQUQnMF/cNFfBwk+unUjM6qv0Lbk3ldaT+00 6UId44miJxxyf+RQ0gtCVKqRmjAmDRI= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1729086091; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=UXqcalwn4S4yHlup2tBJVxgZbxREYH2njWfBxa9BZTE=; b=KG6ouZcLIT/q/Wx6pSA+SgdmqizWWy+vbaySr/5Ulr19Bo8l2+ja6Qf8+cF6ZMhPQkvKF6 CuGqLGIkiCUd4wAQ== Received: by knuth.suse.de (Postfix, from userid 10510) id 28AC9529439; Wed, 16 Oct 2024 15:41:31 +0200 (CEST) Received: from localhost (localhost [127.0.0.1]) by knuth.suse.de (Postfix) with ESMTP id 18647529438 for ; Wed, 16 Oct 2024 15:41:31 +0200 (CEST) Date: Wed, 16 Oct 2024 15:41:31 +0200 (CEST) From: Michael Matz To: binutils@sourceware.org Subject: PR32260: Improve estimate of number of strings Message-ID: <84634a8b-773e-f7c6-c1fb-1b0bc5fbeab1@suse.de> MIME-Version: 1.0 X-Spam-Score: -4.20 X-Spamd-Result: default: False [-4.20 / 50.00]; BAYES_HAM(-3.00)[99.98%]; NEURAL_HAM_LONG(-1.00)[-1.000]; NEURAL_HAM_SHORT(-0.20)[-1.000]; RCVD_NO_TLS_LAST(0.10)[]; MIME_GOOD(-0.10)[text/plain]; MID_RHS_MATCH_FROM(0.00)[]; ARC_NA(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; MIME_TRACE(0.00)[0:+]; MISSING_XM_UA(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; FROM_HAS_DN(0.00)[]; RECEIVED_HELO_LOCALHOST(0.00)[]; RCVD_COUNT_TWO(0.00)[2]; FROM_EQ_ENVFROM(0.00)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; TO_DN_NONE(0.00)[]; PREVIOUSLY_DELIVERED(0.00)[binutils@sourceware.org]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[suse.de:mid] X-Spam-Level: X-Spam-Status: No, score=-9.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, 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 X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: binutils-bounces~patchwork=sourceware.org@sourceware.org we want to pre-size the hashtable for mergable strings, and so need an estimate for the number of them in one input section. This reduces the over-estimation a little. bfd/ PR ld/32260 * merge.c (record_section): Throttle down the overestimation of number of entries in a section. --- Tested without regressions on Alans list of targets. Okay for master? bfd/merge.c | 34 +++++++++++++++++++++++++++++++++- 1 file changed, 33 insertions(+), 1 deletion(-) diff --git a/bfd/merge.c b/bfd/merge.c index c811bc57eae..2b4d2e428d4 100644 --- a/bfd/merge.c +++ b/bfd/merge.c @@ -736,10 +736,42 @@ record_section (struct sec_merge_info *sinfo, /* Now populate the hash table and offset mapping. */ + /* We use an upper bounds of the number of strings that can be + possibly contained in this section. There are a maximum of + NMAX=255^n strings of length n, which then need NMAX*(n+1) + bytes. We also know that the section size fits into mapofs_type + (i.e. is smaller than 4G). */ + mapofs_type nestimate; + if (sec->flags & SEC_STRINGS) + { + mapofs_type nmax, slen, remaining; + nestimate = 1; + nmax = 255; + slen = 2; + remaining = sec->size; + while (remaining > 0) + { + mapofs_type fits = remaining / slen; + if (fits <= nmax) + { + nestimate += fits; + break; + } + nestimate += nmax; + /* Ensure that nmax doesn't overflow. */ + BFD_ASSERT (slen < 5); + remaining -= nmax * slen; + nmax *= 255; + slen++; + } + } + else + nestimate = sec->size / sec->entsize; + /* Presize the hash table for what we're going to add. We overestimate quite a bit, but if it turns out to be too much then other sections merged into this area will make use of that as well. */ - if (!sec_merge_maybe_resize (sinfo->htab, 1 + sec->size / 2)) + if (!sec_merge_maybe_resize (sinfo->htab, nestimate)) { free (contents); return 2;