Re: [patchv2 2/2] Accelerate lookup_symbol_aux_objfile 14.5x [Re: [patch 0/2] Accelerate symbol lookups 15x]

[Doug Evans <xdje42 at gmail dot com>]

Doug Evans <xdje42@gmail.com> writes:

> On Fri, Oct 24, 2014 at 12:33 AM, Jan Kratochvil
> <jan.kratochvil@redhat.com> wrote:
>> On Fri, 24 Oct 2014 09:16:01 +0200, Doug Evans wrote:
>>> One thought I have is that significant changes at a higher level will
>>> minimize the impact of this patch.  One change I'm thinking of making
>>> is replacing iterating over every symbol table and then if that fails
>>> going to the index with instead just going straight to the index: the
>>> index knows where the symbols are (you mentioned this as well).
>>
>> Yes, I tried that first.
>>
>> For the performance testcase I provided the issue is in
>> lookup_symbol_global_iterator_cb():
>>
>>   data->result = lookup_symbol_aux_objfile (objfile, GLOBAL_BLOCK,
>>                                             data->name, data->domain);
>>   if (data->result == NULL)
>>     data->result = lookup_symbol_aux_quick (objfile, GLOBAL_BLOCK,
>>                                             data->name, data->domain);
>>
>> Changing their order does not fix the performance as lookup_symbol_aux_quick()
>> (that is quick_symbol_functions::lookup_symbol) can return NULL
>>  * either if the symbol is really not present in the index.
>>  * or if the symbol's symtab is already expanded.
>>
>> For the latter case (commonly happening) quick_symbol_functions::lookup_symbol
>> finds the right symtab but then it drops that information.
>>
>> Changing the quick_symbol_functions::lookup_symbol semantics may fix it.
>
> Yeah, the experiment I want to try is a bit more invasive such that,
> for example, we only go to the index (and expand any symtabs found if
> necessary and only search those ones). E.g., If the index returns NULL
> there's no point in searching the full set of symtabs.
>
>> But then it will get fixed only for .gdb_index files while my two patches also
>> improve performance of non-.gdb_index files.
>
> That's still an open issue, sure.

Here's the first experiment I tried.
It's a quick hack to *only* search the index (or psyms).

I get a massive speed up.
I was able to recreate your slow.cc example on my fc20 box and got
similar numbers.  For me, without your dictionary hash caching patch
I see 13.8M calls to iter_match_first_hashed for "p/r var".
13.8 million.  Yikes.
With your dictionary hash caching patch that reduces to 31.
With the appended experiment it is reduced to 55.
Not as good, though the difference from 13.8M is in the noise at this
point :-).
The experiment also provides more general speedups.
I'd be grateful if you could replace your 1/2 and 2/2 with this experiment
and see what numbers you get.  It's good to have data.

Alas, the experiment is just that because gdb only looks up
some symbols from expanded symtabs and not partial symtabs/gdb_index,
because neither partial syms nor the index record all symbols,
and thus there are several testsuite regressions.
We would have to fix this.
Note that while the fixes may mitigate some of the speedups,
I think it'll still be a significant enough of a win that we'll
want to do this.

However, for basic symbol lookup, only searching the index, and never
searching already expanded symtabs, makes sense: the index knows
where the symbol lives, so why search anywhere else?  And in the null case,
which is what is killing performance in your example, we certainly want to
go to the index first, not second.  Thus I think the thing to do is make
this work.  It will require more substantial changes in GDB, sure.
One thought I have is to make the data structure that records a
class be a symtab itself.  In some ways it already is.

So the question is, what to do in the meantime.

I'm ok with your 2/2 patch (with the changes I've requested) since I think
it's reasonable regardless of anything else.
[btw, I've submitted a patch to move lookup_block_symbol to block.c:
https://sourceware.org/ml/gdb-patches/2014-10/msg00720.html]
Your 1/2 patch (dictionary hash caching) still gives me pause.
I didn't have time to collect more timing data this weekend.
I might be ok with it going in provided it can be removed without
effort if/when the above improvements are applied.
But I'd still like to collect a bit more perf data.

Before this patch with plain FSF GDB I get 7.5 seconds for "p/r var".
With this patch it's 0.005.


diff --git a/gdb/dwarf2read.c b/gdb/dwarf2read.c
index df5531d..4f947b2 100644
--- a/gdb/dwarf2read.c
+++ b/gdb/dwarf2read.c
@@ -3569,9 +3569,11 @@ dw2_symtab_iter_next (struct dw2_symtab_iterator *iter)
 
       per_cu = dw2_get_cutu (cu_index);
 
+#if 0 /* xyzdje: Just use index.  */
       /* Skip if already read in.  */
       if (per_cu->v.quick->symtab)
 	continue;
+#endif
 
       /* Check static vs global.  */
       if (attrs_valid)
diff --git a/gdb/psymtab.c b/gdb/psymtab.c
index 6c0c880..0f5ec93 100644
--- a/gdb/psymtab.c
+++ b/gdb/psymtab.c
@@ -505,8 +505,12 @@ lookup_symbol_aux_psymtabs (struct objfile *objfile,
 
   ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, ps)
   {
-    if (!ps->readin && lookup_partial_symbol (objfile, ps, name,
-					      psymtab_index, domain))
+    if (
+#if 0 /* xyzdje: Just use index.  */
+	!ps->readin &&
+#endif
+	lookup_partial_symbol (objfile, ps, name,
+			       psymtab_index, domain))
       {
 	struct symbol *sym = NULL;
 	struct symtab *stab = psymtab_to_symtab (objfile, ps);
diff --git a/gdb/symtab.c b/gdb/symtab.c
index c530d50..70349f7 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -87,10 +87,12 @@ struct symbol *lookup_symbol_aux_local (const char *name,
 					const domain_enum domain,
 					enum language language);
 
+#if 0 /* xyzdje: Just use index.  */
 static
 struct symbol *lookup_symbol_aux_symtabs (int block_index,
 					  const char *name,
 					  const domain_enum domain);
+#endif
 
 static
 struct symbol *lookup_symbol_aux_quick (struct objfile *objfile,
@@ -1504,9 +1506,11 @@ lookup_static_symbol_aux (const char *name, const domain_enum domain)
   struct objfile *objfile;
   struct symbol *sym;
 
+#if 0 /* xyzdje: Just use index.  */
   sym = lookup_symbol_aux_symtabs (STATIC_BLOCK, name, domain);
   if (sym != NULL)
     return sym;
+#endif
 
   ALL_OBJFILES (objfile)
   {
@@ -1621,6 +1625,7 @@ lookup_global_symbol_from_objfile (const struct objfile *main_objfile,
        objfile;
        objfile = objfile_separate_debug_iterate (main_objfile, objfile))
     {
+#if 0 /* xyzdje: Just use index.  */
       /* Go through symtabs.  */
       ALL_OBJFILE_PRIMARY_SYMTABS (objfile, s)
 	{
@@ -1633,6 +1638,7 @@ lookup_global_symbol_from_objfile (const struct objfile *main_objfile,
 	      return fixup_symbol_section (sym, (struct objfile *)objfile);
 	    }
 	}
+#endif
 
       sym = lookup_symbol_aux_quick ((struct objfile *) objfile, GLOBAL_BLOCK,
 				     name, domain);
@@ -1672,6 +1678,8 @@ lookup_symbol_aux_objfile (struct objfile *objfile, int block_index,
   return NULL;
 }
 
+#if 0 /* xyzdje: Just use index.  */
+
 /* Same as lookup_symbol_aux_objfile, except that it searches all
    objfiles.  Return the first match found.  */
 
@@ -1692,6 +1700,8 @@ lookup_symbol_aux_symtabs (int block_index, const char *name,
   return NULL;
 }
 
+#endif
+
 /* Wrapper around lookup_symbol_aux_objfile for search_symbols.
    Look up LINKAGE_NAME in DOMAIN in the global and static blocks of OBJFILE
    and all related objfiles.  */
@@ -1771,6 +1781,7 @@ lookup_symbol_aux_quick (struct objfile *objfile, int kind,
   sym = lookup_block_symbol (block, name, domain);
   if (!sym)
     error_in_psymtab_expansion (kind, name, symtab);
+  block_found = block;
   return fixup_symbol_section (sym, objfile);
 }
 
@@ -1865,8 +1876,10 @@ lookup_symbol_global_iterator_cb (struct objfile *objfile,
 
   gdb_assert (data->result == NULL);
 
+#if 0 /* xyzdje: Just use index.  */
   data->result = lookup_symbol_aux_objfile (objfile, GLOBAL_BLOCK,
 					    data->name, data->domain);
+#endif
   if (data->result == NULL)
     data->result = lookup_symbol_aux_quick (objfile, GLOBAL_BLOCK,
 					    data->name, data->domain);
@@ -1987,6 +2000,7 @@ basic_lookup_transparent_type (const char *name)
      of the desired name as a global, then do psymtab-to-symtab
      conversion on the fly and return the found symbol.  */
 
+#if 0 /* xyzdje: Just use index.  */
   ALL_OBJFILES (objfile)
   {
     ALL_OBJFILE_PRIMARY_SYMTABS (objfile, s)
@@ -2000,6 +2014,7 @@ basic_lookup_transparent_type (const char *name)
 	  }
       }
   }
+#endif
 
   ALL_OBJFILES (objfile)
   {
@@ -2015,6 +2030,7 @@ basic_lookup_transparent_type (const char *name)
      of the desired name as a file-level static, then do psymtab-to-symtab
      conversion on the fly and return the found symbol.  */
 
+#if 0 /* xyzdje: Just use index.  */
   ALL_OBJFILES (objfile)
   {
     ALL_OBJFILE_PRIMARY_SYMTABS (objfile, s)
@@ -2028,6 +2044,7 @@ basic_lookup_transparent_type (const char *name)
 	  }
       }
   }
+#endif
 
   ALL_OBJFILES (objfile)
   {