Re: linkonce and exceptions on Solaris

[Bruno Haible <haible at ilog dot fr>]

> When investigating this, I found that the out-of-order FDEs come from
> gnu.linkonce sections. All linkonce functions are after all regular
> functions, but their FDEs are spread all over the place. As more an
> more of these FDEs are added, inserting regular FDEs will get more and
> more expensive.

Very interesting analysis. Does the following patch help?

Bruno



Sat Jan 10 04:23:00 1998  Bruno Haible  <bruno@linuix.mathematik.uni-karlsruhe.de>

        * frame.c (fde_insert, add_fdes, frame_init): Use two-stack insertion
          sort algorithm.

*** egcs-971225/gcc/frame.c.bak	Fri Jan  9 01:41:32 1998
--- egcs-971225/gcc/frame.c	Sat Jan 10 03:51:27 1998
*************** next_fde (fde *p)
*** 192,212 ****
  }
  
  /* One iteration of an insertion sort, for adding new FDEs to the array.
!    Usually the new FDE will go in at the end, so we can expect close to
!    O(n) performance.  If this turns out to be overly optimistic, we can have
!    the linker sort the FDEs so we don't have to do it at run time.  */
  
  static void
! fde_insert (fde **array, size_t i, fde *this_fde)
  {
!   array[i] = this_fde;
  
!   for (; i > 0 && fde_compare (array[i], array[i-1]) < 0; --i)
      {
-       this_fde = array[i];
        array[i] = array[i-1];
!       array[i-1] = this_fde;
      }
  }
  
  static size_t
--- 192,253 ----
  }
  
  /* One iteration of an insertion sort, for adding new FDEs to the array.
!    This is a special kind of insertion sort, optimized for data sets that
!    look like  101 102 103 201 202 105 203 204 106 107 205 206 207.
!    Usually the new FDE will go in at the end or at the last insertio point,
!    so we can expect O(n) performance, instead of the worst-case O(n^2).
!    If this turns out to be overly optimistic, we can have the linker sort
!    the FDEs so we don't have to do it at run time, or we can use an AVL
!    tree for O(n log(n)) performance.  */
! 
! typedef struct fde_accumulator
! {
!   fde **array1;
!   size_t count1;
!   fde **array2;
!   size_t count2;
! } fde_accumulator;
  
  static void
! fde_insert (fde_accumulator *accu, fde *this_fde)
  {
!   fde **array;
!   size_t i;
  
!   if (accu->count2 == 0 || fde_compare (this_fde, accu->array2[0]) < 0)
!     {
!       array = accu->array1;
!       i = accu->count1;
!     }
!   else
!     {
!       array = accu->array2;
!       i = accu->count2;
!     }
! 
!   while (i > 0 && fde_compare (this_fde, array[i-1]) < 0)
      {
        array[i] = array[i-1];
!       i--;
      }
+   if (array == accu->array1)
+     {
+       if (i < accu->count1 && accu->count2 == 0)
+ 	{
+ 	  fde **ptr1 = accu->array1 + i + 1;
+ 	  fde **ptr2 = accu->array2;
+ 	  size_t count = accu->count1 - i;
+ 	  accu->count2 = count;
+ 	  do *ptr2++ = *ptr1++; while (--count > 0);
+ 	  accu->count1 = i;
+ 	}
+       accu->count1++;
+     }
+   else
+     {
+       accu->count2++;
+     }
+   array[i] = this_fde;
  }
  
  static size_t
*************** count_fdes (fde *this_fde)
*** 227,236 ****
  }
  
  static void
! add_fdes (fde *this_fde, fde **array, size_t *i_ptr,
! 	  void **beg_ptr, void **end_ptr)
  {
-   size_t i = *i_ptr;
    void *pc_begin = *beg_ptr;
    void *pc_end = *end_ptr;
  
--- 268,275 ----
  }
  
  static void
! add_fdes (fde *this_fde, fde_accumulator *accu, void **beg_ptr, void **end_ptr)
  {
    void *pc_begin = *beg_ptr;
    void *pc_end = *end_ptr;
  
*************** add_fdes (fde *this_fde, fde **array, si
*** 240,246 ****
        if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
  	continue;
  
!       fde_insert (array, i++, this_fde);
  
        if (this_fde->pc_begin < pc_begin)
  	pc_begin = this_fde->pc_begin;
--- 279,285 ----
        if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
  	continue;
  
!       fde_insert (accu, this_fde);
  
        if (this_fde->pc_begin < pc_begin)
  	pc_begin = this_fde->pc_begin;
*************** add_fdes (fde *this_fde, fde **array, si
*** 248,254 ****
  	pc_end = this_fde->pc_begin + this_fde->pc_range;
      }
  
-   *i_ptr = i;
    *beg_ptr = pc_begin;
    *end_ptr = pc_end;
  }
--- 287,292 ----
*************** add_fdes (fde *this_fde, fde **array, si
*** 260,268 ****
  static void
  frame_init (struct object* ob)
  {
-   fde *this_fde;
    size_t count;
!   fde **array;
    void *pc_begin, *pc_end;
  
    if (ob->fde_array)
--- 298,305 ----
  static void
  frame_init (struct object* ob)
  {
    size_t count;
!   fde_accumulator accu;
    void *pc_begin, *pc_end;
  
    if (ob->fde_array)
*************** frame_init (struct object* ob)
*** 275,296 ****
      count = count_fdes (ob->fde_begin);
  
    ob->count = count;
!   array = (fde **) malloc (sizeof (fde *) * count);
  
    pc_begin = (void*)(uaddr)-1;
    pc_end = 0;
-   count = 0;
  
    if (ob->fde_array)
      {
        fde **p = ob->fde_array;
        for (; *p; ++p)
! 	add_fdes (*p, array, &count, &pc_begin, &pc_end);
      }
    else
!     add_fdes (ob->fde_begin, array, &count, &pc_begin, &pc_end);
  
!   ob->fde_array = array;
    ob->pc_begin = pc_begin;
    ob->pc_end = pc_end;
  }
--- 312,346 ----
      count = count_fdes (ob->fde_begin);
  
    ob->count = count;
!   accu.array1 = (fde **) malloc (sizeof (fde *) * count);
!   accu.array2 = (fde **) alloca (sizeof (fde *) * count);
!   accu.count1 = 0;
!   accu.count2 = 0;
  
    pc_begin = (void*)(uaddr)-1;
    pc_end = 0;
  
    if (ob->fde_array)
      {
        fde **p = ob->fde_array;
        for (; *p; ++p)
! 	add_fdes (*p, &accu, &pc_begin, &pc_end);
      }
    else
!     add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end);
! 
!   if (accu.count1 + accu.count2 != count)
!     abort ();
! 
!   if (accu.count2 > 0)
!     {
!       fde **ptr1 = accu.array1 + accu.count1;
!       fde **ptr2 = accu.array2;
!       size_t c = accu.count2;
!       do *ptr1++ = *ptr2++; while (--c > 0);
!     }
  
!   ob->fde_array = accu.array1;
    ob->pc_begin = pc_begin;
    ob->pc_end = pc_end;
  }