Inefficient frame_init in large programs

[Teemu Torma <tot at trema dot com>]

I have noticed that frame_init is very ineffecient in large
programs with big shared libraries.  It turns out that fde_insert
uses quite a long time doing insertion sort.

The comment in fde_insert suggests to move the sorting into
the linker, but meanwhile, using qsort to sort the fde array instead
makes the whole operation much faster.  I don't have any figures,
but it feels to be ~10 times faster, fractions of seconds instead
of couple of seconds in my case.

Teemu

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;