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

  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
  

On Mon, Mar 16, 2026 at 9:37 AM Nick Clifton <nickc@redhat.com> wrote:
>
> 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

Is bfd_realloc really the bottleneck? If yes, why are the execution times almost
the same? It looks like that the memory usage doesn't change much.  If we can't
improve both execution time and memory usage at the same time, shouldn't we
focus on one of them?

>   but maybe a step in the right direction.
>
>   Thoughts / comments ?
>
> Cheers
>   Nick
>
  

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.
  

Hi H.J.

>>    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().

> Is bfd_realloc really the bottleneck?

Not really no.  It does take a small amount of time, of course, especially
if a new memory region needs to be used.  But in the grand scheme of things
it is not actually a significant time hog.

Cheers
   Nick
  

Hi Michael,

>>    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().  

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

Hmm, no ...


> 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).

Actually that sounds like an interesting idea.  I may have a go myself.

> If we'd go with your patch 

I think that I am going to withdraw the patch.  It did not achieve enough
of a gain to make it really useful and your idea of preallocating enough
space at the start looks like it might be far more effective.

Cheers
   Nick