[Bug binutils/29993] New: objcopy --merge-notes slow for large .so with many annobin notes

[fche at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=29993

            Bug ID: 29993
           Summary: objcopy --merge-notes slow for large .so with many
                    annobin notes
           Product: binutils
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: binutils
          Assignee: unassigned at sourceware dot org
          Reporter: fche at redhat dot com
  Target Milestone: ---

A modern firefox build includes construction of a 3.9GB libxul.so (including
debuginfo) on x86-64.  On a f37 toolchain, readelf -S reports

  [30] .gnu.build.a[...] NOTE             00000000093022c8  088cef2c
       00000000076734c8  0000000000000000           0     0     4

i.e., 118MB of .gnu.build.attributes, of some 4 million entries.
The fedora rpm build process includes an

% objcopy --merge-notes .... libxul.so

stage to gather those together.  On a 5GHz machine with ample RAM, this process
takes around ten minutes of 100% cpu time.  That's about 1/3rd of the total
build time for the package.

objcopy.c's merge copy seems to be responsible.  There is a
doubly nested loop over the notes, resulting in O(n**2) complexity.

   2406   for (pnote = pnotes; pnote < pnotes_end; pnote ++)
   2407     {
[...]
   2426       /* Rule 2: Check to see if there is an identical previous note. 
*/
   2427       for (iter = 0, back = pnote - 1; back >= pnotes; back --)
   2428         {
   2429           if (is_deleted_note (back))
   2430             continue;

Please consider improving the algorithm's performance on this sort of large
dataset.

-- 
You are receiving this mail because:
You are on the CC list for the bug.