diff mbox

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

Message ID m3k33mjbw8.fsf@sspiff.org
State New
Headers show

Commit Message

Doug Evans Oct. 27, 2014, 5:54 a.m. UTC 
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.

Comments

Doug Evans Oct. 27, 2014, 6:02 a.m. UTC | #1 
On Sun, Oct 26, 2014 at 10:54 PM, Doug Evans <xdje42@gmail.com> wrote:
> [...]
> 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 :-).

Sorry, poor wording.
The latter number, 55, is the number of calls to
iter_match_first_hashed with the experimental patch.
The 13.8M number is the number of calls to iter_match_first_hashed
with your 1/2 patch and
the 31 number is the number of times a new hash is computed.
Jan Kratochvil Oct. 27, 2014, 8:54 a.m. UTC | #2 
On Mon, 27 Oct 2014 06:54:15 +0100, Doug Evans wrote:
> 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.

Benchmark on non-trivial application with    'p <tab><tab>':
Command execution time:   0.091000 (cpu),   0.092709 (wall) --- Doug's fix
Command execution time:   4.215000 (cpu),   4.241466 (wall) --- both fixes with new [patch 2/2]
Command execution time:   7.373000 (cpu),   7.395095 (wall) --- both fixes
Command execution time:  13.572000 (cpu),  13.592689 (wall) --- just lookup_symbol_aux_objfile fix
Command execution time: 113.036000 (cpu), 113.067995 (wall) --- FSF GDB HEAD

That is 113.067995/0.092709 = 1219x improvement.


> 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.

OK, so running a regression testsuite with your patch is pointless now.


> 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?

What about inlined function instances? Are they in .gdb_index? And if they are
we need all their instances while .gdb_index always points to only one
instance.  I did not check/test it, just an idea now.


> 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.

I was looking if Tom Tromey justified why
quick_symbol_functions::lookup_symbol returns NULL on already expanded symtabs
- this was introduced by:
	Subject: [0/4] RFC: refactor partial symbol tables
	Message-ID: <m38wbyc31o.fsf@fleche.redhat.com>
But I haven't found anything, probably just to make the implementation
safer/easier.


> 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]

OK, I will rebase the patch 2/2 after it gets checked in.


> 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.

The improvements above IIUC apply only for objfiles with .gdb_index.
That patch 1/2 applied even for non-.gdb_index objfiles.


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

It matches my benchmark above.


Thanks,
Jan
diff mbox

Patch

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)
   {