Re: (patch) hpjyg09: bcache optimizations

[Srikanth Adayapalam <srikanth@cup.hp.com>]

> 
> 
> The first red flag here is that this patch adds a new target macro,
> BCACHE_ALLOW_DUPLICATES (in config/pa/tm-hppa.h), which is actually
> dependent on the application being debugged, not the architecture.
> Whether the bcache helps you depends on the contents of your debug
> info, not whether it's running on a PA microprocessor.  Hmm.

	While it is true that it is not tied to the microprocessor,
(and the placement of the macro is not ideal perhaps,) it is tied 
somewhat to the HP-UX platform in that :

	o The bcache is beneficial, when there is high degree of
          duplication and redundancy in the debug info generated
          by a set of compilers for a platform (e.g : stabs + gcc + linux.)

        o and is useless and high overhead item , if there is little
          or no duplication (e.g : som + HP cc + HP-UX).


	On HP-UX systems, we have a tool called pxdb, which is a linker
post processor (or a debugger preprocessor if you want to look at it 
that way) which runs thro the a.out and removes all duplicates. So when
gdb enters the picture there is no duplicate debug info at all. Further 
this overhead is not particular to the C compiler, it is seen for all
applications compiled with HP compilers. The C compiler's case just
happened to be mentioned. That we waste 140 MB trying to eliminate the 
non-existent dups was a big concern for us.	

Hope this clarifies the picture. As for how to proceed with the patch,
I'll leave it to Jimmy and this forum to evolve the best course.

Thanks
Srikanth

	 
From jtc@redback.com Fri Nov 05 11:17:00 1999
From: jtc@redback.com (J.T. Conklin)
To: Jim Blandy <jimb@cygnus.com>
Cc: Jimmy Guo <guo@cup.hp.com>, gdb-patches@sourceware.cygnus.com
Subject: Re: (patch) hpjyg09: bcache optimizations
Date: Fri, 05 Nov 1999 11:17:00 -0000
Message-id: <5mwvrw92gx.fsf@jtc.redbacknetworks.com>
References: <Pine.LNX.4.10.9911041332020.15719-100000@hpcll168.cup.hp.com> <npaeoskevw.fsf@zwingli.cygnus.com>
X-SW-Source: 1999-q4/msg00191.html
Content-length: 2247

>>>>> "Jim" == Jim Blandy <jimb@cygnus.com> writes:
Jim> But this situation still sounds weird.  The bcache is a very
Jim> simple thing --- bcache.h and bcache.c total 289 lines of code.
Jim> You give it a string of bytes, and it either adds a copy of your
Jim> string to its hash table, or finds an identical copy already
Jim> present.  Either way, it hands you back a pointer to its stashed
Jim> copy.  So, a bcache is helpful if you expect a lot of duplicates.

This brings back memories.  

Many years ago, I discovered CVS had terrible hash behavior.  Date and
Revision strings were used as keys, and each character (of which there
were only digits, '.', and '/') was weighted equally.  I can't recall
exactly, but I think the original hash function resulted in ~10% bucket
utilization --- the remaining ~90% would not be used by any valid keys.
And even among the remaning ~10%, the distribution was non-uniform.

I changed it to one of the functions compared in the Red Dragon book's
discussion of hash functions and their suitability for use for hashing
identifiers (which tend to have a lot of duplication/redundency). This
change resulted in a uniform distribution across all buckets and a
cooresponding performance improvement.

For the longest time, I used to keep a histogram plot of the original
and new hash functions in a folder, and would show them to anyone who
would listen to the tale: switching from a nieve to a complex data
structure will not automatically result in a performance improvement.

So I agree with Jim, fixing bcache to use a better hash table is a
much better approach than microoptimizing the existing hash function
by making it an inline function or a macro.  Many thanks for spending
the time and tracking down the root cause.

For reference, here is hash function I used:

    unsigned int 
    hashpjw(const char* x)
    {
      unsigned int h = 0;
      unsigned int g;

      while (*x != 0)
      {
        h = (h << 4) + *x++;
        if ((g = h & 0xf0000000) != 0)
          h = (h ^ (g >> 24)) ^ g;
      }
      return h;
    }

It will have to be modified slightly for use in bcache, but it may
result in acceptable behavior in this case as well.

        --jtc

-- 
J.T. Conklin
RedBack Networks
From tromey@cygnus.com Fri Nov 05 12:00:00 1999
From: Tom Tromey <tromey@cygnus.com>
To: gdb-patches@sourceware.cygnus.com
Subject: Re: (patch) hpjyg09: bcache optimizations
Date: Fri, 05 Nov 1999 12:00:00 -0000
Message-id: <87u2n0lnbn.fsf@cygnus.com>
References: <Pine.LNX.4.10.9911041332020.15719-100000@hpcll168.cup.hp.com> <npaeoskevw.fsf@zwingli.cygnus.com>
X-SW-Source: 1999-q4/msg00192.html
Content-length: 427

>>>>> "Jim" == Jim Blandy <jimb@cygnus.com> writes:

Jim> - growing the hash table when the average chain length grows beyond 
Jim>   a certain limit, so the time overhead remains the same as the
Jim>   problem size grows

Greg McGary recently pointed out to me that libiberty now contains a
hash table implementation.  You still have to write the hash function,
but the growing, etc, are handled automatically.

Tom
From guo@cup.hp.com Fri Nov 05 12:38:00 1999
From: Jimmy Guo <guo@cup.hp.com>
To: Srikanth Adayapalam <srikanth@cup.hp.com>
Cc: jimb@cygnus.com, gdb-patches@sourceware.cygnus.com
Subject: Re: (patch) hpjyg09: bcache optimizations
Date: Fri, 05 Nov 1999 12:38:00 -0000
Message-id: <Pine.LNX.4.10.9911051142210.12517-100000@hpcll168.cup.hp.com>
References: <199911051850.KAA28555@flytrap.cup.hp.com>
X-SW-Source: 1999-q4/msg00193.html
Content-length: 1485

Given Jim Blandy's comments:
  http://sourceware.cygnus.com/ml/gdb-patches/1999-q4/msg00188.html

and Srikanth's clarification:
  http://sourceware.cygnus.com/ml/gdb-patches/1999-q4/msg00190.html

I think we should look at the issue of bypassing and the issue of bcache
hash implementation separately.

Bcache is introduced to deal with duplicate symbols.  Where it is not
necessary, it just adds time and space overheads, and that could be
significant for HP customers debugging large applications.  The tuning
of bcache hash is probably necessary, but that's a general and separate
issue.

I'd like to tackle the bypass scheme initially to introduce an
acceptable bypass mechanism which gives gdb users with platform compiler
combintations like HP-UX + HP cc compiler a faster / smaller footprint
gdb for large apps -- 
    Controlling the bypass through a target dependent macro def is out.
    The bcache_ignore_duplicates() and bcache_filter_duplicates() calls
    still need to be added, and be used to bypass bcache when detecting
    that the HP compiler is used (and if gcc is used, gdb will still use
    bcache).
Comments?

As to the macro implementation of hash(), that is a smaller issue and
will be looked at with some more performance benchmarking to answer
whether or not "Inlining such a relatively large body of code is
definitely not a definite win".  Again, the focus will be debugging
large applications, as typical for HP customers.

- Jimmy Guo, guo@cup.hp.com