Bug 28058 - 300x performance regression in strip
Summary: 300x performance regression in strip
Status: RESOLVED FIXED
Alias: None
Product: binutils
Classification: Unclassified
Component: binutils (show other bugs)
Version: unspecified
: P2 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2021-07-06 19:56 UTC by Niklas Hambüchen
Modified: 2021-07-09 15:58 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Niklas Hambüchen 2021-07-06 19:56:05 UTC
Dear maintainer,

I found a performance regression between binutils 2.34 and 2.35.1 that makes stripping a 50 MB `.a` take 300 seconds instead of 1 second.

Original investigation, including `.a` file for testing:

https://github.com/NixOS/nixpkgs/issues/129467

I bisected the issue to this commit:

    a8e14f4cc2badfcf959f5e2cc57a941dc43f72d4 is the first bad commit
    commit a8e14f4cc2badfcf959f5e2cc57a941dc43f72d4
    Author: Nick Clifton <nickc@redhat.com>
    Date:   Thu Mar 5 15:47:15 2020 +0000

        Add support for ELF files which contain multiple reloc sections which all target the same section.


Note that this is the same commit that introduced the performance regression in `as` in this bug:

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

However, the commit that fixed `as` in there does not fix this regression.

I would appreciate if you could have a look!

Niklas
Comment 1 Niklas Hambüchen 2021-07-07 00:13:40 UTC
Ah, master actually has a fix from 1 month ago that I hadn't spotted:

    commit 956ea65cd707707c0f725930214cbc781367a831
    Author: Michael Matz <matz@suse.de>
    Date:   Mon Jun 7 15:52:31 2021 +0200

        bfd/elf: Don't read non-existing secondary relocs
        
        Without this we unconditionally try to slurp in secondary
        relocs for each input section, leading to quadratic behaviour
        even for strip(1).  On write-out we already used a flag to avoid
        this.
        
        So track existence of secondary relocs on read-in as well and
        only slurp in when needed.  This still doesn't implement a proper
        list of secondary reloc sections, and still would exhibit quadratic
        behaviour if most input sections have a secondary reloc section.
        But at least on normal input this avoids any slowdown from trying
        to handle secondary relocation sections.

It would be great if a point release could be made that includes it.

Thank you!
Comment 2 Nick Clifton 2021-07-07 14:30:00 UTC
(In reply to Niklas Hambüchen from comment #1)
 
> It would be great if a point release could be made that includes it.

Sorry - since we are just about to make a new release (2.37 - due in two weeks time) - there does not seem to be much benefit in creating yet another point release just for this one issue.

Cheers
  Nick
Comment 3 Niklas Hambüchen 2021-07-07 14:45:13 UTC
OK, makes sense.

I was hoping that a point release for the past binutils (e.g. 2.35, 2.36 series) could make the fix available to current Linux distributions possible, as they often do upgrade to bugfix releases, but not major releases in the same OS release cycle.

I'm not certain what binutils's point release policy is overall -- there seems to be some of it (e.g. 2.35.1 being released after 2.36), so I wasn't sure whether such a thing would qualify or not.

Thanks for looking into it!

(Marking as resolved as the fix will be in 2.37.)
Comment 4 cvs-commit@gcc.gnu.org 2021-07-09 15:55:46 UTC
The binutils-2_36-branch branch has been updated by Nick Clifton <nickc@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=84fd26d8209e99fc3a432dd0b09b6c053de1ce65

commit 84fd26d8209e99fc3a432dd0b09b6c053de1ce65
Author: Nick Clifton <nickc@redhat.com>
Date:   Fri Jul 9 16:54:59 2021 +0100

    Backport patch to fix a quadratic slow down in the BFD library.
    
            PR 28058
    bfd     * elf.c (bfd_section_from_shdr): Set has_secondary_relocs flag.
            (_bfd_elf_slurp_secondary_reloc_section): Use it for early-out.
Comment 5 Nick Clifton 2021-07-09 15:57:39 UTC
(In reply to Niklas Hambüchen from comment #1)
> It would be great if a point release could be made that includes it.

I have added the patch to the 2.36 branch so that any distribution that uses that (rather than the official releases) will gain the fix.  It is not the same as a point release, but I hope that it will help.
Comment 6 Niklas Hambüchen 2021-07-09 15:58:31 UTC
Thank you!