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.
