Re: [patch] ld speedup 1/3 (suffix merge)

[Alan Modra <amodra at bigpond dot net dot au>]

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