Re: (patch) hpjyg09: bcache optimizations

[Andrew Cagney <ac131313@cygnus.com>]

Jimmy Guo wrote:
> 
> Andrew,
> 
> 1) Not all compilers support the inline keyword (HP C compiler for
>    example), so it will be a nop change in such cases.  Therefore the
>    macro def might be the only way to optimize this away.

BTW, how do you get a HP compiler to inline a function?  Will it just do
it if -O<very-large-number> is given?

In the case of the simulators, the decision was to build a fast correct
program when built with GCC and a slower correct program when built with
other compilers.

> 2) The macro def is duplicating the hash() implementation.  I agree that
>    one implementation is much maintainable.  While hash() could use
>    BCACHE_HASH macro, what about the 1st point you made about debugging
>    and use of macros?

Yes, I know the two comments appear contradictary.  I'm assuming the
macro is approved.  In that case I think a single (un-debuggable?)
implementation is better than a macro and function duplicating code.

Even having a function with a macro as its body helps - at least you can
set breakpoints on that hash function and watch what is being returned.

> 3) In the actual use of BCACHE_HASH vs. the hash() call, yes a default
>    BCACHE_HASH can be provided which calls hash().  However, this would
>    introduce yet another macro wrapper (to address both 2 and 3 ... one
>    for the hash implementation -- 2; another for the hash call wrapper
>    using the macro implementation directly or through an actual hash()
>    wrapper).

True. However, I believe it is more important to avoid littering C files
with further:

	#if ...
		one variant
	#else
		another variant
	#endif

If we did that we need to ensure that each alternatives continued to be
compilable.

> 
> >       o       I'm in too minds over the first argument
> >               (HASHVAL). I recently spent time eliminating
> >               several really bad macro definitions that
> >               abused the fact that they had direct access to
> >               arguments - changing them to multi-arch functions
> >               was, er, non-trivial.
> >
> >               However, in this case, the rational and use is
> >               clean.
> 
> I'm not sure I understand your last point about changing macros to
> multi-arch functions.

(Er, yes, sorry, my quandry isn't very clear).  Some of the old GDB
macro's would do things like:
	#define X(Y) (memset (&(Y), sizeof (Y), 0); (Y).A = 1; (Y).B = 2)

I'd still prefer to see retval = BCACHE_HASH (bytes, temp_count). 
Unfortunatly, that can't be implemented as an ISO-C macro so it won't
happen :-)

> Since:
>  a) the macro def is pretty much necessary to make the change
>     meaningful (see 1),
>  b) to have one implementation of hash and make the usage clean (see 2 &
>     3),
> I think we should just use the macro def and blow away hash() altogether.

I think there first needs to be a technical decision made about how much
of a price we're willing to pay for performance VS maintainability.  As
you can probably tell, I have a very strong preference for the latter
:-)

If the decision is to use the macro then the corresponding hash()
function should be deleted.

	enjoy,
		Andrew
From guo@cup.hp.com Thu Nov 04 18:07:00 1999
From: Jimmy Guo <guo@cup.hp.com>
To: Andrew Cagney <ac131313@cygnus.com>
Cc: gdb-patches@sourceware.cygnus.com
Subject: Revision: (patch) hpjyg09: bcache optimizations
Date: Thu, 04 Nov 1999 18:07:00 -0000
Message-id: <Pine.LNX.4.10.9911041739340.15357-100000@hpcll168.cup.hp.com>
References: <382232AF.7E3ED811@cygnus.com>
X-SW-Source: 1999-q4/msg00182.html
Content-length: 10394

***
Following my reply to Andrew is the revision of this patch.
Patch dependency: hpjyg05 (config/pa/tm-hppa.h)
***

>BTW, how do you get a HP compiler to inline a function?  Will it just do
>it if -O<very-large-number> is given?

The HP C compiler will inline functions at +O3 and +O4.  And
+Oinlinebudget=<n> controls the aggressiveness in inlining:
                                  = 100     Default level on inlining.
                                  > 100     More aggressive inlining.
                                  2 - 99    Less aggressive inlining.
                                  = 1       Only inline if it reduces
				  code
                                            size.

>> 2) The macro def is duplicating the hash() implementation.  I agree that
>>    one implementation is much maintainable.  While hash() could use
>>    BCACHE_HASH macro, what about the 1st point you made about debugging
>>    and use of macros?
>
>Yes, I know the two comments appear contradictary.  I'm assuming the
>macro is approved.  In that case I think a single (un-debuggable?)
>implementation is better than a macro and function duplicating code.
>
>Even having a function with a macro as its body helps - at least you can
>set breakpoints on that hash function and watch what is being returned.

I look forward to the same (that the use of the macro is approved) :)

>If the decision is to use the macro then the corresponding hash()
>function should be deleted.

I'm attaching a revision of this patch to use the macro only.  Given two
choices of using only the macro vs. providing a macro and also a
function wrapping around the macro, I also prefer the first choice,
assuming the decision is to use the macro.

Thanks!

Here is the revision of the patch:

ChangeLog:

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

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

        * bcache.c (BCACHE_HASH): Define, the macro equivalent of the
        hash () function this macro is replacing.
        (lookup_cache): Bypass if ignore_duplicates (new static var) is
        set; use BCACHE_HASH macro instead of hash() function call;
        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:49:12 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 15:13:44 1999
--- gdb/bcache.c	Thu Nov  4 17:56:03 1999
***************
*** 24,62 ****
  #include "bcache.h"
  #include "gdb_string.h"		/* For memcpy declaration */
  
! /* Prototypes for local functions. */
! 
! static unsigned int hash PARAMS ((void *, int));
! 
! static void *lookup_cache PARAMS ((void *, int, int, struct bcache *));
! 
  /* FIXME:  Incredibly simplistic hash generator.  Probably way too expensive
     (consider long strings) and unlikely to have good distribution across hash
     values for typical input. */
  
! static unsigned int
! hash (bytes, count)
!      void *bytes;
!      int count;
! {
!   unsigned int len;
!   unsigned long hashval;
!   unsigned int c;
!   const unsigned char *data = bytes;
! 
!   hashval = 0;
!   len = 0;
!   while (count-- > 0)
!     {
!       c = *data++;
!       hashval += c + (c << 17);
!       hashval ^= hashval >> 2;
!       ++len;
!     }
!   hashval += len + (len << 17);
!   hashval ^= hashval >> 2;
!   return (hashval % BCACHE_HASHSIZE);
! }
  
  static void *
  lookup_cache (bytes, count, hashval, bcachep)
--- 24,87 ----
  #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. */
! /* guo: Replaced hash() implementation with the equivalent BCACHE_HASH
!    macro definition, since having two implementations (macro vs. function)
!    of the same functionality is harder to maintain, and specific function
!    inlining by compiler is not supported by all compilers (i.e. the use of
!    'inline' keyword supported by GCC). */
  /* FIXME:  Incredibly simplistic hash generator.  Probably way too expensive
     (consider long strings) and unlikely to have good distribution across hash
     values for typical input. */
  
! #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); \
!   }
! 
! /* Prototypes for local functions. */
! 
! static void *lookup_cache PARAMS ((void *, int, int, struct bcache *));
! 
! /* 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)
***************
*** 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;
--- 94,118 ----
    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 ****
      }
    else
      {
!       hashval = hash (bytes, count);
        location = lookup_cache (bytes, count, hashval, bcachep);
        if (location != NULL)
  	{
--- 145,152 ----
      }
    else
      {
!       BCACHE_HASH (hashval, bytes, count);
! 
        location = lookup_cache (bytes, count, hashval, bcachep);
        if (location != NULL)
  	{
***************
*** 139,144 ****
--- 177,195 ----
    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++)
      {
--- 197,203 ----
  {
    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 13:49:11 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 */