[patchv2,2/2] Accelerate lookup_symbol_aux_objfile 14.5x [Re: [patch 0/2] Accelerate symbol lookups 15x]
Commit Message
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
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.
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
@@ -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)
@@ -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);
@@ -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)
{