To: djgpp AT sun DOT soe DOT clarkson DOT edu
Subject: Profiling performance improvements
Organization: Code Generation Technology, Fremont, CA
Date: Tue, 09 Jun 92 14:10:49 -0700
From: "Thomas J. Merritt" <tjm AT netcom DOT com>

The following patch for /gnu/lib/mcount.c dramatically improves the
performance of programs that are being profiled.  The linear searching
in mcount.c is replaced by a hashed search.  Memory usage for profile
data is increased by 50% though.

TJ Merritt
tjm AT netcom DOT com

*** mcount.old	Mon Apr 20 19:56:58 1992
--- mcount.c	Tue May 26 23:28:58 1992
***************
*** 1,3 ****
--- 1,4 ----
+ 
  #include <fcntl.h>
  
  typedef struct {
***************
*** 12,27 ****
      unsigned long count;
  } MTABE;
  
  typedef struct MTAB {
!   MTABE calls[341];
    struct MTAB *prev;
  } MTAB;
  
  static header h;
  short *histogram asm("mcount_histogram");
  short mcount_skip asm("mcount_skip");
  static int histlen;
  static MTAB *mtab=0;
  
  void mcount(_to)
  {
--- 13,42 ----
      unsigned long count;
  } MTABE;
  
+ #define MTABEPERBLOCK 227
+ 
  typedef struct MTAB {
!   MTABE calls[MTABEPERBLOCK];
!   struct MTAB *nextptr[MTABEPERBLOCK];
!   short nextoffset[MTABEPERBLOCK];
    struct MTAB *prev;
  } MTAB;
  
+ #define INDEXESPERBLOCK 512	/* We use this value so the '%' becomes '&'
+ /*#define INDEXESPERBLOCK 682  / * This is the maximum value for a 4k block*/
+ 
+ typedef struct {
+   MTAB *hashptr[INDEXESPERBLOCK];
+   short hashoffset[INDEXESPERBLOCK];
+ } MINDEX;
+ 
  static header h;
  short *histogram asm("mcount_histogram");
  short mcount_skip asm("mcount_skip");
  static int histlen;
  static MTAB *mtab=0;
+ static MINDEX *mindex=0;
+ static int freeoffset = MTABEPERBLOCK;
  
  void mcount(_to)
  {
***************
*** 31,36 ****
--- 46,56 ----
    int ebp;
    int from;
    int mtabi;
+   int hv;
+   MTAB *ptr;
+   short offset;
+   MTABE *entry;
+   MTAB *tmp;
    MTABE **cache;
  
    mcount_skip = 1;
***************
*** 44,86 ****
      mcount_skip = 0;
      return;
    }
!   mtabi = -1;
!   for (m=mtab; m; m=m->prev)
    {
!     for (i=0; i<341; i++)
      {
!       if (m->calls[i].from == 0)
!       {
!         mtabi = i;
!         break;
!       }
!       if ((m->calls[i].from == from) &&
!           (m->calls[i].to == to))
!         {
!           m->calls[i].count ++;
!           *cache = m->calls + i;
!           mcount_skip = 0;
!           return;
!         }
      }
    }
!   if (mtabi != -1)
    {
!     mtab->calls[mtabi].from = from;
!     mtab->calls[mtabi].to = to;
!     mtab->calls[mtabi].count = 1;
!     *cache = mtab->calls + mtabi;
!     mcount_skip = 0;
!     return;
    }
!   m = (MTAB *)sbrk(sizeof(MTAB));
!   memset(m, 0, sizeof(MTAB));
!   m->prev = mtab;
!   mtab = m;
!   m->calls[0].from = from;
!   m->calls[0].to = to;
!   m->calls[0].count = 1;
!   *cache = m->calls;
    mcount_skip = 0;
  }
  
--- 64,109 ----
      mcount_skip = 0;
      return;
    }
!   hv = (from + to) % INDEXESPERBLOCK;
!   if (mindex == NULL)
!   {
!     mindex = (MINDEX *)sbrk(sizeof(MINDEX));
!     memset(mindex, 0, sizeof(MINDEX));
!   }
!   ptr = mindex->hashptr[hv];
!   offset = mindex->hashoffset[hv];
!   while (ptr != NULL)
    {
!     entry = &(ptr->calls[offset]);
!     if (entry->from == from && entry->to == to)
      {
!       entry->count++;
!       *cache = entry;
!       mcount_skip = 0;
!       return;
      }
+     tmp = ptr->nextptr[offset];
+     offset = ptr->nextoffset[offset];
+     ptr = tmp;
    }
!   if (freeoffset>=MTABEPERBLOCK)
    {
!     m = (MTAB *)sbrk(sizeof(MTAB));
!     memset(m, 0, sizeof(MTAB));
!     m->prev = mtab;
!     mtab = m;
!     freeoffset=0;
    }
!   offset = freeoffset++;
!   mtab->nextptr[offset] = mindex->hashptr[hv];
!   mtab->nextoffset[offset] = mindex->hashoffset[hv];
!   mindex->hashptr[hv] = mtab;
!   mindex->hashoffset[hv] = offset;
!   entry=&(mtab->calls[offset]);
!   entry->from = from;
!   entry->to = to;
!   entry->count = 1;
!   *cache = entry;
    mcount_skip = 0;
  }
  
***************
*** 111,117 ****
    write(f, histogram, histlen);
    for (m=mtab; m; m=m->prev)
    {
!     for (i=0; i<341; i++)
        if (m->calls[i].from == 0)
          break;
      write(f, m->calls, i*12);
--- 134,140 ----
    write(f, histogram, histlen);
    for (m=mtab; m; m=m->prev)
    {
!     for (i=0; i<MTABEPERBLOCK; i++)
        if (m->calls[i].from == 0)
          break;
      write(f, m->calls, i*12);