This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
[PATCH] gdb script performance
- From: Jean-Marc Saffroy <saffroy at gmail dot com>
- To: gdb-patches at sources dot redhat dot com
- Date: Thu, 30 Nov 2006 01:33:02 +0100 (CET)
- Subject: [PATCH] gdb script performance
Hi folks,
It seems the patches I posted yesterday on the gdb list have gone
completely unnoticed, so I guess I should resend them here.
Back in October, I had reported performance problems I observed when
scripting gdb to analyze a kdump core, and even after applying the patch
gdb-lookup-internal-first-3, gprof showed something like this:
http://jeanmarc.saffroy.free.fr/gdb/gdb-baseline.html
Daniel Jacobowitz suggested the following:
On Thu, 5 Oct 2006, Daniel Jacobowitz wrote:
26.14 381.31 381.31 141867 2.69 3.50 find_pc_sect_psymtab
18.54 651.82 270.51 331876 0.82 0.82 find_pc_sect_section
17.88 912.69 260.87 144847060 0.00 0.00 lookup_partial_symbol
11.01 1073.33 160.64 1254595136 0.00 0.00 strcmp_iw
4.98 1145.97 72.64 34010 2.14 16.50 lookup_symbol_aux_psymtabs
4.78 1215.73 69.75 9584 7.28 8.12 fixup_section
4.46 1280.79 65.06 lbasename
3.42 1330.64 49.85 12183 4.09 4.09 lookup_partial_symtab
1.83 1357.34 26.70 33844664 0.00 0.00 strcmp_iw_ordered
1.68 1381.82 24.48 1288426966 0.00 0.00 symbol_natural_name
1.09 1397.71 15.89 1288426966 0.00 0.00 symbol_search_name
Well then. Observations:
- We're looking up partial symbols way too often.
- It's taking way too long.
- And oh my lord is that a lot of calls to the (fairly inefficient)
strcmp_iw.
It looks like only about three calls to find_pc_sect_psymtab per
expression evaluation, which is bad but not too bad - sounds like
a last-searched-item cache may be useful.
Recently I took some time and followed Daniel's advice, ie. I implemented
a (trivial) cache for the last-searched PC, as well as another (more
convoluted) for the last-searched symbol. The symbol cache patch gives
this profile:
http://jeanmarc.saffroy.free.fr/gdb/gdb-symcache.html
With both patches applied:
http://jeanmarc.saffroy.free.fr/gdb/gdb-symcache-pc_cache.html
On a regular build (no profiling), my script now runs in 23 seconds
instead of 158. :-)
This is still unfinished (hooks for invalidating the caches are missing,
and I'm sure performance can still be enhanced significantly), but before
going further, I'd like to know how you feel about integrating such
changes.
Cheers,
--
saffroy@gmail.com
Index: gdb-6.5-prof/gdb/symtab.c
===================================================================
--- gdb-6.5-prof.orig/gdb/symtab.c 2006-11-29 03:27:18.000000000 +0100
+++ gdb-6.5-prof/gdb/symtab.c 2006-11-29 03:27:20.000000000 +0100
@@ -2022,8 +2022,8 @@
/* Find the symtab associated with PC and SECTION. Look through the
psymtabs and read in another symtab if necessary. */
-struct symtab *
-find_pc_sect_symtab (CORE_ADDR pc, asection *section)
+static struct symtab *
+find_pc_sect_symtab_uncached (CORE_ADDR pc, asection *section)
{
struct block *b;
struct blockvector *bv;
@@ -2123,6 +2123,24 @@
return (s);
}
+struct symtab *
+find_pc_sect_symtab (CORE_ADDR pc, asection *section)
+{
+ static CORE_ADDR cached_pc;
+ static asection *cached_section;
+ static struct symtab *cached_symtab;
+ static int try_cache = 0;
+
+ if (try_cache && (cached_pc == pc) && (cached_section == section))
+ return cached_symtab;
+
+ try_cache = 1;
+ cached_pc = pc;
+ cached_section = section;
+ cached_symtab = find_pc_sect_symtab_uncached (pc, section);
+ return cached_symtab;
+}
+
/* Find the symtab associated with PC. Look through the psymtabs and
read in another symtab if necessary. Backward compatibility, no section */
Index: gdb-6.5-prof/gdb/symtab.c
===================================================================
--- gdb-6.5-prof.orig/gdb/symtab.c 2006-11-27 03:01:22.000000000 +0100
+++ gdb-6.5-prof/gdb/symtab.c 2006-11-28 01:21:28.000000000 +0100
@@ -94,6 +94,20 @@
struct symtab **symtab);
static
+int symcache_lookup (const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symbol **sym,
+ struct symtab **symtab);
+
+static
+void symcache_add (struct symbol *sym,
+ const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symtab **symtab);
+
+static
struct symbol *lookup_symbol_aux_symtabs (int block_index,
const char *name,
const char *linkage_name,
@@ -1113,6 +1127,9 @@
}
}
+ if (symcache_lookup (name, linkage_name, domain, &sym, symtab))
+ return sym;
+
/* Now do whatever is appropriate for the current language to look
up static and global variables. */
@@ -1120,7 +1137,7 @@
block, domain,
symtab);
if (sym != NULL)
- return sym;
+ goto out;
/* Now search all static file-level symbols. Not strictly correct,
but more useful than an error. Do the symtabs first, then check
@@ -1131,16 +1148,19 @@
sym = lookup_symbol_aux_symtabs (STATIC_BLOCK, name, linkage_name,
domain, symtab);
if (sym != NULL)
- return sym;
-
+ goto out;
+
sym = lookup_symbol_aux_psymtabs (STATIC_BLOCK, name, linkage_name,
domain, symtab);
if (sym != NULL)
- return sym;
+ goto out;
if (symtab != NULL)
*symtab = NULL;
- return NULL;
+
+ out:
+ symcache_add (sym, name, linkage_name, domain, symtab);
+ return sym;
}
/* Check to see if the symbol is defined in BLOCK or its superiors.
@@ -1215,6 +1235,177 @@
return NULL;
}
+/* Check for a cached symbol lookup.
+ */
+
+struct symcache_entry {
+ const char *name;
+ const char *linkage_name;
+ domain_enum domain;
+ struct symbol *sym;
+ struct symtab *symtab;
+ struct symcache_entry *next, *prev; /* mru list */
+};
+
+/* max number of entries in symcache */
+#define SYMCACHE_SIZE 256
+
+/* fixed-size hash table of symcache entries */
+static htab_t symcache_hashtab;
+
+/* most recently accessed symcache entry */
+static struct symcache_entry *symcache_newest;
+
+static hashval_t
+symcache_hash(const void *e)
+{
+ struct symcache_entry *entry = (struct symcache_entry *)e;
+
+ return htab_hash_string (entry->name) + entry->domain;
+}
+
+static int
+symcache_eq(const void *e, const void *f)
+{
+ struct symcache_entry *a = (struct symcache_entry *)e;
+ struct symcache_entry *b = (struct symcache_entry *)f;
+
+ return ! strcmp (a->name, b->name)
+ // FIXME && !strcmp(a->linkage_name, b->linkage_name)
+ && (a->domain == b->domain);
+}
+
+static void
+symcache_list_add(struct symcache_entry *entry)
+{
+ if (symcache_newest == NULL)
+ {
+ /* init mru */
+ entry->prev = entry;
+ entry->next = entry;
+ symcache_newest = entry;
+ }
+ else
+ {
+ /* add entry at head of mru */
+ entry->next = symcache_newest;
+ entry->prev = symcache_newest->prev;
+ entry->prev->next = entry;
+ entry->next->prev = entry;
+ symcache_newest = entry;
+ }
+}
+
+static void
+symcache_list_del(struct symcache_entry *entry)
+{
+ /* remove entry from mru */
+ entry->prev->next = entry->next;
+ entry->next->prev = entry->prev;
+}
+
+static void
+symcache_del(void *e)
+{
+ struct symcache_entry *entry = (struct symcache_entry *)e;
+
+ symcache_list_del (entry);
+ free (entry->name);
+ free (entry->linkage_name);
+ free (entry);
+}
+
+static void
+symcache_add (struct symbol *sym,
+ const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symtab **symtab)
+{
+ struct symcache_entry request, *entry, **slot;
+
+ /* initialize on first use */
+ if (!symcache_hashtab)
+ symcache_hashtab = htab_create_alloc (SYMCACHE_SIZE,
+ symcache_hash,
+ symcache_eq,
+ symcache_del,
+ xcalloc,
+ free);
+
+ /* sym can be known, but with unknown symtab: add it if possible */
+ request.name = name;
+ request.linkage_name = linkage_name;
+ request.domain = domain;
+ entry = htab_find (symcache_hashtab, &request);
+ if (entry != HTAB_EMPTY_ENTRY)
+ {
+ if (symtab != NULL)
+ entry->symtab = *symtab;
+ return;
+ }
+
+ /* when cache is full, remove oldest element */
+ if (htab_elements (symcache_hashtab) == SYMCACHE_SIZE)
+ {
+ struct symcache_entry *oldest;
+
+ oldest = symcache_newest->prev;
+ htab_remove_elt (symcache_hashtab, oldest);
+ }
+
+ /* this is really a new entry */
+ entry = xcalloc (1, sizeof(*entry));
+ entry->name = strdup (name);
+ entry->linkage_name = linkage_name ? strdup (linkage_name) : NULL;
+ entry->domain = domain;
+ entry->sym = sym;
+ if (symtab != NULL)
+ entry->symtab = *symtab;
+ symcache_list_add (entry);
+
+ slot = htab_find_slot (symcache_hashtab, entry, INSERT);
+ *slot = entry;
+}
+
+static int
+symcache_lookup (const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symbol **sym,
+ struct symtab **symtab)
+{
+ struct symcache_entry request, *entry;
+
+ if (!symcache_hashtab)
+ return 0;
+
+ request.name = name;
+ request.linkage_name = linkage_name;
+ request.domain = domain;
+ entry = htab_find (symcache_hashtab, &request);
+ if (entry == HTAB_EMPTY_ENTRY)
+ return 0;
+
+ if (symtab != NULL)
+ {
+ if (entry->symtab == NULL)
+ /* symtab is requested, but cached entry does not have it */
+ return 0;
+ *symtab = entry->symtab;
+ }
+ *sym = entry->sym;
+
+ /* keep mru list sorted */
+ if (entry != symcache_newest)
+ {
+ symcache_list_del (entry);
+ symcache_list_add (entry);
+ }
+
+ return 1;
+}
+
/* Check to see if the symbol is defined in one of the symtabs.
BLOCK_INDEX should be either GLOBAL_BLOCK or STATIC_BLOCK,
depending on whether or not we want to search global symbols or