From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jimmy Guo To: gdb-patches@sourceware.cygnus.com Subject: (patch) hpjyg09: bcache optimizations Date: Thu, 04 Nov 1999 13:48:00 -0000 Message-id: X-SW-Source: 1999-q4/msg00175.html *** 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 * 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 */