This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
Re: Use stable sort for ld -r relocs
- From: <Paul_Koning at Dell dot com>
- To: <amodra at gmail dot com>
- Cc: <binutils at sourceware dot org>
- Date: Wed, 26 Aug 2015 14:15:06 +0000
- 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>
> On Aug 26, 2015, at 10:02 AM, Alan Modra <amodra@gmail.com> wrote:
>
> 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.
Stability is (or isn't) a property of the algorithm. It is not necessary to do "non-rigorous testing" and such testing is not conclusive.
If a stable sort is needed, a sort function whose API specification includes stability as a promised property should be used. It doesn't seem a good idea to rely on one that today seems to be stable but does not promise that; if the API leaves it open, then tomorrow the implementation might be replaced by an unstable sort. Or the implementation of that API might be stable on one platform, and unstable on another.
paul