(patch) hpjyg09: bcache optimizations

Jimmy Guo guo@cup.hp.com
Thu Nov 4 13:48:00 GMT 1999


***
Patch dependency: hpjyg05 (config/pa/tm-hppa.h)
***

Couple of bcache.c optimizations:

1) Introduction and use of inlined hash function, and attempt to reduce
   the memcmp call.

2) Ability to bypass bcache duplicate handling (initial behavior
   controlled by a target dependent macro def), and to adjust such
   behavior at runtime through two convenience functions.

ChangeLog:

1999-11-04	Jimmy Guo	<guo@cup.hp.com>

	* config/pa/tm-hppa.h (BCACHE_ALLOW_DUPLICATES): Declare.

	* bcache.c (BCACHE_USE_INLINED_HASH): Define, enables use of
	the macro equivalent of the hash () function instead.
	(BCACHE_HASH): Define, the macro equivalent of the hash () function.
	(lookup_cache): Bypass if ignore_duplicates (new static var) is
	set; use BCACHE_HASH macro ifdef BCACHE_USE_INLINED_HASH;
	optimize (reduce) memcmp() call.
	(bcache_ignore_duplicates,bcache_eliminate_duplicates): New
	functions, to control turning on/off duplicate handling at
	runtime.

	* bcache.h (bcache_ignore_duplicates,bcache_eliminate_duplicates):
	Declare.

Index: gdb/config/pa/tm-hppa.h
/opt/gnu/bin/diff -r -c -N  /view/guo.wdb.c//CLO/Components/WDB/Src/gnu/gdb/config/pa/tm-hppa.h gdb/config/pa/tm-hppa.h
*** /view/guo.wdb.c//CLO/Components/WDB/Src/gnu/gdb/config/pa/tm-hppa.h	Tue Nov  2 16:04:12 1999
--- gdb/config/pa/tm-hppa.h	Thu Nov  4 13:28:28 1999
***************
*** 811,816 ****
--- 811,818 ----
  		 || ((symname)[0] == '$' && isdigit ((symname)[1]))     \
  		 ))
  
+ #define BCACHE_ALLOW_DUPLICATES
+ 
  /* Here's how to step off a permanent breakpoint.  */
  #define SKIP_PERMANENT_BREAKPOINT (hppa_skip_permanent_breakpoint)
       extern void hppa_skip_permanent_breakpoint (void);
Index: gdb/bcache.c
/opt/gnu/bin/diff -r -c -N  /view/guo.wdb.c//CLO/Components/WDB/Src/gnu/gdb/bcache.c gdb/bcache.c
*** /view/guo.wdb.c//CLO/Components/WDB/Src/gnu/gdb/bcache.c	Thu Nov  4 10:57:42 1999
--- gdb/bcache.c	Thu Nov  4 13:28:20 1999
***************
*** 24,35 ****
--- 24,71 ----
  #include "bcache.h"
  #include "gdb_string.h"		/* For memcpy declaration */
  
+ /* CM: The hash function is called a LOT, so have a an inlined version.
+    This should help scaling to larger apps. Comment out the following
+    define to use the old method. */
+ 
+ #define BCACHE_USE_INLINED_HASH
+ 
  /* Prototypes for local functions. */
  
+ #ifndef BCACHE_USE_INLINED_HASH
  static unsigned int hash PARAMS ((void *, int));
+ #endif
  
  static void *lookup_cache PARAMS ((void *, int, int, struct bcache *));
  
+ #ifdef BCACHE_USE_INLINED_HASH
+ 
+ /* CM: The hash method should exactly match the function defined below. */
+ 
+ #define BCACHE_HASH(retval, bytes, temp_count) \
+   { \
+     int bcache_hash_count = (temp_count); \
+     unsigned int bcache_hash_len; \
+     unsigned long bcache_hash_hashval; \
+     unsigned int bcache_hash_c; \
+     const unsigned char *bcache_hash_data = (bytes); \
+     \
+     bcache_hash_hashval = 0; \
+     bcache_hash_len = 0; \
+     while (bcache_hash_count-- > 0) \
+       { \
+         bcache_hash_c = *bcache_hash_data++; \
+         bcache_hash_hashval += bcache_hash_c + (bcache_hash_c << 17); \
+         bcache_hash_hashval ^= bcache_hash_hashval >> 2; \
+         ++bcache_hash_len; \
+       } \
+     bcache_hash_hashval += bcache_hash_len + (bcache_hash_len << 17); \
+     bcache_hash_hashval ^= bcache_hash_hashval >> 2; \
+     (retval) = (bcache_hash_hashval % BCACHE_HASHSIZE); \
+   }
+ 
+ #else
+ 
  /* FIXME:  Incredibly simplistic hash generator.  Probably way too expensive
     (consider long strings) and unlikely to have good distribution across hash
     values for typical input. */
***************
*** 58,63 ****
--- 94,123 ----
    return (hashval % BCACHE_HASHSIZE);
  }
  
+ #endif /* BCACHE_USE_INLINED_HASH */
+ 
+ /* srikanth, 990314, JAGaa80452, the bcache seems to be an extremely high 
+    overhead data structure. See that the overhead (which is really every 
+    byte that is not used to store GDB's data i.e., cells used for
+    housekeeping info like pointers, hash chain heads etc.,) is of the order
+    of O(m * n * 64k) where m is the number of load modules compiled with -g, 
+    and n is the number of strings that have unique length. This spells doom 
+    for applications wih a large number of shared libraries (m increases) 
+    and C++ (n increases since we also stick demangled names into the cache.) 
+    When debugging HP's C compiler more than 140 MB or about 48% of memory is
+    due to the bcache overhead. Not the data just the overhead !
+ 
+    Further research, communication with Cygnus and Fred Fish (the original
+    implementor) shows that this module is extremely effective saving as much 
+    as 60% in gcc + stabs + linux combination. So I am disabling it just for
+    the Wildebeest and only for non-doom mode. */
+ 
+ #ifdef BCACHE_ALLOW_DUPLICATES
+ static int ignore_duplicates = 1;
+ #else
+ static int ignore_duplicates = 0;
+ #endif
+ 
  static void *
  lookup_cache (bytes, count, hashval, bcachep)
       void *bytes;
***************
*** 69,81 ****
    struct hashlink **hashtablep;
    struct hashlink *linkp;
  
    hashtablep = bcachep->indextable[count];
    if (hashtablep != NULL)
      {
        linkp = hashtablep[hashval];
        while (linkp != NULL)
  	{
! 	  if (memcmp (BCACHE_DATA (linkp), bytes, count) == 0)
  	    {
  	      location = BCACHE_DATA (linkp);
  	      break;
--- 129,153 ----
    struct hashlink **hashtablep;
    struct hashlink *linkp;
  
+   if (ignore_duplicates)	/* don't care if it exists already */
+     return NULL;
+ 
    hashtablep = bcachep->indextable[count];
    if (hashtablep != NULL)
      {
        linkp = hashtablep[hashval];
        while (linkp != NULL)
  	{
! 	  /* CM: The following helps to avoid excessive (possibly shared
! 	     library--i.e. indirect) function calls. This function is
! 	     called a LOT, so this should help scaling to larger apps.
! 
! 	     The original line was:
! 	     if (memcmp (BCACHE_DATA (linkp), bytes, count) == 0) */
! 
! 	  if ((*((char *) (BCACHE_DATA (linkp))) == *((char *) bytes))
! 	      ? (memcmp (BCACHE_DATA (linkp), bytes, count) == 0)
! 	      : 0)
  	    {
  	      location = BCACHE_DATA (linkp);
  	      break;
***************
*** 108,114 ****
--- 180,192 ----
      }
    else
      {
+       /* CM: Use the inlined hash function if requested. */
+ #ifdef BCACHE_USE_INLINED_HASH
+       BCACHE_HASH (hashval, bytes, count);
+ #else
        hashval = hash (bytes, count);
+ #endif
+ 
        location = lookup_cache (bytes, count, hashval, bcachep);
        if (location != NULL)
  	{
***************
*** 139,144 ****
--- 217,235 ----
    return (location);
  }
  
+ /* srikanth, 990323, now we can toggle the bcache behavior on the fly */
+ void
+ bcache_ignore_duplicates ()
+ {
+   ignore_duplicates = 1;
+ }
+ 
+ void
+ bcache_eliminate_duplicates ()
+ {
+   ignore_duplicates = 0;
+ }
+ 
  void
  print_bcache_statistics (bcachep, id)
       struct bcache *bcachep;
***************
*** 146,152 ****
  {
    struct hashlink **hashtablep;
    struct hashlink *linkp;
!   int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt, lmaxh;
  
    for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++)
      {
--- 237,243 ----
  {
    struct hashlink **hashtablep;
    struct hashlink *linkp;
!   int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt = 0, lmaxh = 0;
  
    for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++)
      {
Index: gdb/bcache.h
/opt/gnu/bin/diff -r -c -N  /view/guo.wdb.c//CLO/Components/WDB/Src/gnu/gdb/bcache.h gdb/bcache.h
*** /view/guo.wdb.c//CLO/Components/WDB/Src/gnu/gdb/bcache.h	Thu Nov  4 11:11:13 1999
--- gdb/bcache.h	Thu Nov  4 11:12:53 1999
***************
*** 68,73 ****
--- 68,79 ----
    bcache PARAMS ((void *bytes, int count, struct bcache * bcachep));
  
  extern void
+ bcache_ignore_duplicates PARAMS (());
+ 
+ extern void
+ bcache_eliminate_duplicates PARAMS (());
+ 
+ extern void
  print_bcache_statistics PARAMS ((struct bcache *, char *));
  
  #endif /* BCACHE_H */



More information about the Gdb-patches mailing list