This is the mail archive of the
mailing list for the binutils project.
Re: Use stable sort for ld -r relocs
- From: Jiong Wang <jiong dot wang at arm dot com>
- To: Alan Modra <amodra at gmail dot com>
- Cc: "binutils\ at sourceware dot org" <binutils at sourceware dot org>
- Date: Tue, 15 Sep 2015 13:58:08 +0100
- Subject: Re: Use stable sort for ld -r relocs
- Authentication-results: sourceware.org; auth=none
- References: <20150826140258 dot GB24814 at bubble dot grove dot modra dot org>
Alan Modra writes:
> A number of targets emit multiple relocs at a given r_offset, and
> depend on those relocs staying in their original order. qsort doesn't
> satisfy this requirement, although it appears from my non-rigorous
> testing that glibc's msort.c implementation may in fact be stable.
> I made the mistake of backporting my PR 17666 fix to 2.25.1, thinking
> the code had enough time to settle on mainline, but for anyone with a
> system libc that provides an unstable qsort this will mean 2.25.1
> ld -r may be broken on some targets.
> PR 18867
> * elflink.c (cmp_ext32l_r_offset, cmp_ext32b_r_offset): Delete.
> (cmp_ext64l_r_offset, cmp_ext64b_r_offset): Delete.
> (ext32l_r_offset, ext32b_r_offset, ext64l_r_offset, ext64b_r_offset):
> New functions.
> (elf_link_adjust_relocs): Use an insertion sort to sort relocs.
After this patch, the linking speed becomes much slower when linking
AArch64 kernel on x86 cross environment.
Link time before your patch
after your patch
Below is the simple perf result on the hot functions.
61.46% ld-new libc-2.19.so [.] __memmove_ssse3_back
32.24% ld-new ld-new [.] ext64l_r_offset
5.51% ld-new ld-new [.] elf_link_adjust_relocs
Could you please have a look at this?