This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
Re: [patch] ld speedup 1/3 (suffix merge)
- From: Alan Modra <amodra at bigpond dot net dot au>
- To: Michael Matz <matz at suse dot de>
- Cc: binutils at sources dot redhat dot com, Lars Knoll <lars at trolltech dot com>
- Date: Wed, 10 Sep 2003 13:01:55 +0930
- Subject: Re: [patch] ld speedup 1/3 (suffix merge)
- References: <20030909150800.GU1443@bubble.modra.org> <Pine.LNX.4.44.0309091743500.13736-100000@wotan.suse.de>
On Tue, Sep 09, 2003 at 06:06:06PM +0200, Michael Matz wrote:
> size = a - array;
>
> qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
>
> + /* now loop over the sorted array and merge suffixes */
> for (a = array, end = array + size; a < end; a++)
> {
> e = *a;
> + if (e->len > 1)
> {
> + struct elf_strtab_hash_entry **b = a+1;
> + int found = 0;
> + while (b < end)
> {
> + struct elf_strtab_hash_entry *cmp = *b;
> + if (!is_suffix(cmp, e))
> + break;
> + e->u.suffix = cmp;
> + found = 1;
> + ++b;
> }
> + if (found)
> + e->len = 0;
> }
> }
Hmm, I think we can do better here. Remove the inner loop and use a
negative len to flag merges. I'm fiddling with the following at the
moment.
size = a - array;
if (size > 1)
{
qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
/* Loop over the sorted array and merge suffixes. Start from the
end because we want eg.
s1 -> "d"
s2 -> "bcd"
s3 -> "abcd"
to end up as
s3 -> "abcd"
s2 _____^
s1 _______^
ie. we don't want s1 pointing into the old s2. */
e = *--a;
while (--a >= array)
{
struct elf_strtab_hash_entry *cmp = *a;
if (is_suffix (e, cmp))
{
cmp->u.suffix = e;
cmp->len = -cmp->len;
}
else
e = cmp;
}
}
--
Alan Modra
IBM OzLabs - Linux Technology Centre