Re: linkonce and exceptions on Solaris

[Jason Merrill <jason at cygnus dot com>]

>>>>> Martin von Loewis <martin@mira.isdn.cs.tu-berlin.de> writes:

> When I run a g++ 2.8 compiled image on Solaris, exception handling may
> consume a lot of computing power. In one particular case, I have an
> image which has 9MB of text size. Throwing the first exception will
> take about 10 seconds on an UltraSparc 1.

> So it seems that the bubble sort is the expensive operation
> here. The assumption of O(n) is apparently broken.

Here's a patch to make frame.c use qsort.  I didn't put this in because not
all targets have qsort, and quicksort does badly on already-sorted input.
Anyone want to adapt introsort (see libstdc++/stl/stl_algo.h) for frame.c?

1997-11-25  Teemu Torma  <tot@trema.com>

	* frame.c (fde_compare_sort): New function #if ! DONT_USE_QSORT.
	(fde_compare): Define only #if DONT_USE_QSORT.
	(fde_insert): Insertion sort is now #if DONT_USE_QSORT.
	(add_fdes): Use qsort to sort the array #if ! DONT_USE_QSORT.

Index: frame.c
===================================================================
RCS file: /trema/cvs/gnu/egcs/gcc/frame.c,v
retrieving revision 1.6
diff -u -u -p -r1.6 frame.c
--- frame.c	1997/11/17 09:03:22	1.6
+++ frame.c	1997/11/25 10:17:08
@@ -201,11 +201,19 @@ read_8byte (void *p)
 /* Ordering function for FDEs.  Functions can't overlap, so we just compare
    their starting addresses.  */
 
+#if DONT_USE_QSORT
 static inline saddr
 fde_compare (fde *x, fde *y)
 {
   return (saddr)x->pc_begin - (saddr)y->pc_begin;
 }
+#else
+static int
+fde_compare_sort (fde **x, fde **y)
+{
+  return (saddr)(*x)->pc_begin - (saddr)(*y)->pc_begin;
+}
+#endif
 
 /* Return the address of the FDE after P.  */
 
@@ -220,17 +228,19 @@ next_fde (fde *p)
    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
+static inline void
 fde_insert (fde **array, size_t i, fde *this_fde)
 {
   array[i] = this_fde;
 
+#if DONT_USE_QSORT
   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;
     }
+#endif
 }
 
 static size_t
@@ -271,6 +281,10 @@ add_fdes (fde *this_fde, fde **array, si
       if (this_fde->pc_begin + this_fde->pc_range > pc_end)
 	pc_end = this_fde->pc_begin + this_fde->pc_range;
     }
+
+#if ! DONT_USE_QSORT
+  qsort (array, i, sizeof *array, fde_compare_sort);
+#endif
 
   *i_ptr = i;
   *beg_ptr = pc_begin;