Re: gdb script performance

[Jean-Marc Saffroy <saffroy@gmail.com>]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2810 bytes --]

Hello,

I'm resurrecting this old thread on gdb performance since I took some time 
to look into the problem recently.

On Thu, 5 Oct 2006, Daniel Jacobowitz wrote:

> On Thu, Oct 05, 2006 at 05:29:30PM +0200, Jean-Marc Saffroy wrote:
>> On Thu, 5 Oct 2006, Daniel Jacobowitz wrote:
>>
>> Please find attached gprof output (this is with gdb 6.5 +
>> gdb-lookup-internal-first-3.patch running the lsmaps script I posted
>> earlier).
>>
>> Thanks for helping!
>
> 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.

Some interesting facts:
  - readelf reports no less than 7871 section headers in the vmlinux I'm 
analyzing (this is 2.6.18): any attempt to traverse the list of sections 
costs a *lot*
  - even with the patch lookup-internal-first-3, it seems lookup_symbol_aux 
is sometimes called for gdb script vars

Anyway, I followed your advice and added caching to find_pc_sect_symtab 
and lookup_symbol_aux, which together divided execution time by 6 on my 
benchmark. :-) See gprof output here (baseline is gdb 6.5 with 
gdb-lookup-internal-first-3.patch):
   http://siegfried.dnsalias.net/~saffroy/gdb-baseline.html
   http://siegfried.dnsalias.net/~saffroy/gdb-symcache.html
   http://siegfried.dnsalias.net/~saffroy/gdb-symcache-pc_cache.html
Obviously there is still room for improvement with lbasename.

For completeness I have to mention that gprof reports a completely wrong 
count of seconds on my system (x86-64 box), but it seems there is only a 
bad multiplier somewhere.

Incomplete patches are attached: they lack proper cache invalidation (eg. 
on loading of a new object), but let's discuss the approach first.


Cheers,

-- 
saffroy@gmail.com

[-- Attachment #2: Type: TEXT/PLAIN, Size: 1306 bytes --]

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 */
 

[-- Attachment #3: Type: TEXT/PLAIN, Size: 6375 bytes --]

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