RFC: LD: Changing the size of the delta used when growing merge offset maps

[Michael Matz]

Hello,

On Mon, 16 Mar 2026, Nick Clifton wrote:

>   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 ?

Have you tried to establish the best case possible for this scenario?  
Measure the maxsize of these and realloc that size right from the start, 
so that no reallocs are ever called in that run?

See also commit 21160d8a1 about a related but opposite problem: very many 
tiny mergable sections; a larger increment would have aggrevated 
that specific, but now fixed, problem.

Thing is: every reallocation is interspersed with a fixed number of new 
offset/entry pairs for mergable sections, and each of these pairs is only 
created after parsing and hashing the sections contents.  So the final 
size of the offset map will be directly related to the number of hashed 
blobs in it, and hence roughly related to its size.  So another approach I 
considered but didn't follow up on, was to approximate the initial number 
of entries to (say) section-size divided by 16, guarded by some minimum 
and maximum, or to perhaps make the increment itself somewhat depending on 
that (i.e. large input sections will get a larger increment).

The "16" above would make it so that a mergable string section whose 
average string length is 16 would come out exactly preallocated.

If we'd go with your patch I'd say we don't need it runtime configurable.  
Just use the larger value.  Due to the commit above, after a mergable 
section is parsed that map will be reallocated back to its really used 
size anyway, so any waste during that parsing will be returned back to the 
allocator immediately.  And that waste will be strictly bounded by the 
increment size.  I.e. for your new value of 8192 the waste will be max 
8191 entries (total, not per input section), which translates to 98k .


Ciao,
Michael.