From mboxrd@z Thu Jan 1 00:00:00 1970 From: Srikanth Adayapalam To: jimb@cygnus.com Cc: gdb-patches@sourceware.cygnus.com Subject: Re: (patch) hpjyg09: bcache optimizations Date: Fri, 05 Nov 1999 10:50:00 -0000 Message-id: <199911051850.KAA28555@flytrap.cup.hp.com> References: X-SW-Source: 1999-q4/msg00190.html > > > 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 Cc: Jimmy Guo , 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: X-SW-Source: 1999-q4/msg00191.html Content-length: 2247 >>>>> "Jim" == Jim Blandy 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 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: X-SW-Source: 1999-q4/msg00192.html Content-length: 427 >>>>> "Jim" == Jim Blandy 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 To: Srikanth Adayapalam 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: 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