From patchwork Mon Mar 16 16:35:34 2026 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nick Clifton X-Patchwork-Id: 131822 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from vm01.sourceware.org (localhost [127.0.0.1]) by sourceware.org (Postfix) with ESMTP id 922FE4BB58F9 for ; Mon, 16 Mar 2026 16:37:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 922FE4BB58F9 Authentication-Results: sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=S+cgzEFG X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 0AC644BCA427 for ; Mon, 16 Mar 2026 16:35:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0AC644BCA427 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0AC644BCA427 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1773678942; cv=none; b=ZGEqEwf5MtVa4mt8AdlxGzkql/W5YHQJuUTZ8iCU2GjvUhM2e9q1NzzlkMWmKwsUcRZKjf1CHPPWitUarH9NhH4j3zjk/Jcl2wO+Ff2Buw+XMXG15fdSWBd+kjuTKNMXxT1ElIK6x7V/62fVGWfj1MCuiOvLD9zmMP0E6cNU1vQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1773678942; c=relaxed/simple; bh=jXyRCVhlz0IMTFPoiiNPectmMw9gISLTViMy+HsQz7Q=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=gLe4K5pWQFyD+rw0D1833FG7+gBwvNGGenLVEttBQ9PWrIdDypZ3vKm7MM5XnOKQly/6c2iEqXcx8B/mnohb19civNPFqvfnVXcz2Bke6g0l7ea1Z51RgPnRxcotxR/jTTq6QwRG1wKXcaZRJSZAU35XaChPrq1lbXi2sppbdUY= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0AC644BCA427 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1773678941; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type; bh=amhIhP2uHwotmACvX/9CCVR5fguV0LNlk2KG3BpYyF8=; b=S+cgzEFGmuqZMkL7dI5sb44sWJKfBu7GhfK0/l15XVkPPxQfA/emDZbyU/wkctgKkhCjXo P1ft1vBJA12vavSG6/ZRq4kqIZ2AZNov28hHDs1IEo49DWoB3AjQZpGUE2QCVIK+Ayxkv8 m8+uegy6hssr2HFnWit91+UEjNg0hSI= Received: from mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (ec2-35-165-154-97.us-west-2.compute.amazonaws.com [35.165.154.97]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-494-OIdl_IwgNCCnOyqrcWKYyA-1; Mon, 16 Mar 2026 12:35:40 -0400 X-MC-Unique: OIdl_IwgNCCnOyqrcWKYyA-1 X-Mimecast-MFC-AGG-ID: OIdl_IwgNCCnOyqrcWKYyA_1773678939 Received: from mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.12]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 2E33518002C8 for ; Mon, 16 Mar 2026 16:35:39 +0000 (UTC) Received: from prancer.redhat.com (unknown [10.45.226.110]) by mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 60C4019560AB for ; Mon, 16 Mar 2026 16:35:37 +0000 (UTC) From: Nick Clifton To: binutils@sourceware.org Subject: RFC: LD: Changing the size of the delta used when growing merge offset maps Date: Mon, 16 Mar 2026 16:35:34 +0000 Message-ID: <87ikavvijt.fsf@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.0 on 10.30.177.12 X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: xd727wOYp6AqCngrNq1kZ6MNdlYWOZar2vxVRVY_pb4_1773678939 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-8.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_BLOCKED, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, RCVD_IN_VALIDITY_RPBL_BLOCKED, RCVD_IN_VALIDITY_SAFE_BLOCKED, SPF_HELO_PASS, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on 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 Hi Guys, Running the linker under sysprof shows that the append_offsetmap() function in merge.c is responsible for a large amount of the memory allocated during a link, and a lot of those allocations are calls to bfd_realloc(). Since reallocating memory takes time, and represents an inefficiency it seems to me that we can do better than having a fixed delta for increasing the size of the offset maps. So I am proposing the attached patch. It creates a new static variable called map_delta which is used for the array increments. The value of map_delta is selected based upon whether --reduce-memory-overheads or -O have been specified on the command line. (I am not sure about the use of the -O flag here, but I could not find a more relevant flag to indicate 'this is a big link'). The results are underwhelming, but still do still make a small amount of difference. For example linking LLVM's ld.llc executable on my machine uses 7,121,480 Kb of memory by default and takes around 14.97 seconds. But with the patch applied and adding -O to the link command line this changes to 7,120,196 Kb and 14.89 seconds. Not a lot I know but maybe a step in the right direction. Thoughts / comments ? Cheers Nick diff --git a/bfd/merge.c b/bfd/merge.c index 25798e15cb5..8b35af7e854 100644 --- a/bfd/merge.c +++ b/bfd/merge.c @@ -469,6 +469,38 @@ sec_merge_init (unsigned int entsize, bool strings) return table; } +/* Choose the size increment for the offset maps. A large value means + that we will not have to call bfd_realloc() as many times, if we are + dealing with large input sections, and hence the link will be faster. + But a large value can also waste a lot of memory if we are dealing + with a big number of small input sections. Which is a problem if we + are linking in an environment with a restricted amount of memory. + + FIXME: The values below are a bit arbitrary. It would be better to + create a tuneable parameter that could be set by the user. */ +#define MAP_DELTA_SMALL 1024 +#define MAP_DELTA_NORM 2048 +#define MAP_DELTA_LARGE 8192 + +/* In order to avoid the possibility of using map_delta before it + has been set to a value selected by choose_map_delta() we initialise + it to a semi-reasonable value. */ +#define MAP_DELTA_UNSET 4096 +static unsigned int map_delta = MAP_DELTA_UNSET; + +static unsigned int +choose_map_delta (struct bfd_link_info *info) +{ + if (info->reduce_memory_overheads) + return MAP_DELTA_SMALL; + + /* FIXME: The optimize flag is not really the right flag to test here. */ + if (info->optimize) + return MAP_DELTA_LARGE; + + return MAP_DELTA_NORM; +} + /* Append the tuple of input-offset O corresponding to hash table ENTRY into SECINFO, such that we later may lookup the entry just by O. */ @@ -478,10 +510,12 @@ append_offsetmap (struct sec_merge_sec_info *secinfo, mapofs_type o, struct sec_merge_hash_entry *entry) { - if ((secinfo->noffsetmap & 2047) == 0) + // BFD_ASSERT (map_delta != MAP_DELTA_UNSET); + // BFD_ASSERT (map_delta != 0); + if ((secinfo->noffsetmap & (map_delta - 1)) == 0) { bfd_size_type amt; - amt = (secinfo->noffsetmap + 2048); + amt = (secinfo->noffsetmap + map_delta); secinfo->map_ofs = bfd_realloc (secinfo->map_ofs, amt * sizeof(secinfo->map_ofs[0])); if (!secinfo->map_ofs) @@ -784,7 +818,8 @@ record_section (struct sec_merge_info *sinfo, free (contents); contents = NULL; - /* We allocate the ofsmap arrays in blocks of 2048 elements. + /* We allocate the ofsmap arrays in blocks of map_delta elements. + (See choose_map_delta() above). In case we have very many small input files/sections, this might waste large amounts of memory, so reallocate these arrays here to their true size. */ @@ -1066,6 +1101,9 @@ bfd_merge_sections (bfd *obfd, struct bfd_link_info *info) if (!obfd->xvec->merge_sections) return true; + if (map_delta == MAP_DELTA_UNSET) + map_delta = choose_map_delta (info); + for (ibfd = info->input_bfds; ibfd != NULL; ibfd = ibfd->link.next) if ((ibfd->flags & DYNAMIC) == 0) for (sec = ibfd->sections; sec != NULL; sec = sec->next)