[patch 0/2] Accelerate symbol lookups 15x

[patch 0/2] Accelerate symbol lookups 15x

[Jan Kratochvil]

Hi,

this patchset has been developed+tested only on top of
	[patchv2] Fix 100x slowdown regression on DWZ files
	https://sourceware.org/ml/gdb-patches/2014-10/msg00031.html

While this patchset is technically independent the GDB performance and memory
requirements would not make testing of this patchset possible.

Originally I expected with the patch above (fixing backtrace performance) even
the sluggish interactive GDB performance would get fixed.  It was not fixed.
During debugging I get 10-30 seconds for a response to simple commands like:
	(gdb) print vectorvar.size()

With this patch the performance gets to 1-2 seconds which is somehow
acceptable.  The problem is that dwarf2_gdb_index_functions.lookup_symbol
(quick_symbol_functions::lookup_symbol) may return (and returns) NULL even for
symbols which are present in .gdb_index but which can be found in already
expanded symtab.  But searching in the already expanded symtabs is just too
slow when there are 400000+ expanded symtabs.  There would be needed some
single global hash table for each objfile so that one does not have to iterate
all symtabs.  Which .gdb_index could perfectly serve for, just its
lookup_symbol() would need to return authoritative yes/no answers.

Even after such fix these two simple patches are useful for example for
non-.gdb_index files.

One can reproduce the slugging interactive GDB performance with:
	#include <string>
	using namespace std;
	string var;
	class C {
	public:
	  void m() {}
	};
	int main() {
	  C c;
	  c.m();
	  return 0;
	}
g++ -o slow slow.C -Wall -g $(pkg-config --libs gtkmm-3.0)
gdb ./slow -ex 'b C::m' -ex 'maintenance set per-command space' -ex 'maintenance set per-command symtab' -ex 'maintenance set per-command time' -ex r 
[...]
(gdb) p <tab><tab>
Display all 183904 possibilities? (y or n) n
(gdb) p/r var
$1 = {static npos = <optimized out>, _M_dataplus = {<std::allocator<char>> = {<__gnu_cxx::new_allocator<char>> = {<No data fields>}, <No data fields>}, _M_p = 0x3a4db073d8 <std::string::_Rep::_S_empty_rep_storage+24> ""}}
Command execution time: 20.023000 (cpu), 20.118665 (wall)
                        ^^^^^^^^^
Space used: 927997952 (+0 for this command)
#symtabs: 186099 (+0), #primary symtabs: 21573 (+0), #blocks: 290353 (+0)

For a non-trivial application with all symtabs expanded it takes 113 seconds.

Benchmark on non-trivial application without 'p <tab><tab>':
Command execution time:   0.496000 (cpu),   0.496882 (wall) --- both fixes
Command execution time:   0.899000 (cpu),   0.908062 (wall) --- just lookup_symbol_aux_objfile fix
Command execution time:   3.492000 (cpu),   3.491791 (wall) --- FSF GDB HEAD

Benchmark on non-trivial application with    'p <tab><tab>':
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


No regressions on {x86_64,x86_64-m32,i686}-fedora21pre-linux-gnu in standard
and .gdb_index-enabled runs.  Neither of the patches should cause any visible
behavior change.


Jan

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

[Doug Evans]

On Mon, Oct 20, 2014 at 2:44 PM, Jan Kratochvil
<jan.kratochvil@redhat.com> wrote:
> Hi,
>
> this patchset has been developed+tested only on top of
>         [patchv2] Fix 100x slowdown regression on DWZ files
>         https://sourceware.org/ml/gdb-patches/2014-10/msg00031.html
>
> While this patchset is technically independent the GDB performance and memory
> requirements would not make testing of this patchset possible.
>
> Originally I expected with the patch above (fixing backtrace performance) even
> the sluggish interactive GDB performance would get fixed.  It was not fixed.
> During debugging I get 10-30 seconds for a response to simple commands like:
>         (gdb) print vectorvar.size()
>
> With this patch the performance gets to 1-2 seconds which is somehow
> acceptable.  The problem is that dwarf2_gdb_index_functions.lookup_symbol
> (quick_symbol_functions::lookup_symbol) may return (and returns) NULL even for
> symbols which are present in .gdb_index but which can be found in already
> expanded symtab.  But searching in the already expanded symtabs is just too
> slow when there are 400000+ expanded symtabs.  There would be needed some
> single global hash table for each objfile so that one does not have to iterate
> all symtabs.  Which .gdb_index could perfectly serve for, just its
> lookup_symbol() would need to return authoritative yes/no answers.
>
> Even after such fix these two simple patches are useful for example for
> non-.gdb_index files.
>
> One can reproduce the slugging interactive GDB performance with:
>         #include <string>
>         using namespace std;
>         string var;
>         class C {
>         public:
>           void m() {}
>         };
>         int main() {
>           C c;
>           c.m();
>           return 0;
>         }
> g++ -o slow slow.C -Wall -g $(pkg-config --libs gtkmm-3.0)
> gdb ./slow -ex 'b C::m' -ex 'maintenance set per-command space' -ex 'maintenance set per-command symtab' -ex 'maintenance set per-command time' -ex r
> [...]
> (gdb) p <tab><tab>
> Display all 183904 possibilities? (y or n) n
> (gdb) p/r var
> $1 = {static npos = <optimized out>, _M_dataplus = {<std::allocator<char>> = {<__gnu_cxx::new_allocator<char>> = {<No data fields>}, <No data fields>}, _M_p = 0x3a4db073d8 <std::string::_Rep::_S_empty_rep_storage+24> ""}}
> Command execution time: 20.023000 (cpu), 20.118665 (wall)
>                         ^^^^^^^^^
> Space used: 927997952 (+0 for this command)
> #symtabs: 186099 (+0), #primary symtabs: 21573 (+0), #blocks: 290353 (+0)
>
> For a non-trivial application with all symtabs expanded it takes 113 seconds.
>
> Benchmark on non-trivial application without 'p <tab><tab>':
> Command execution time:   0.496000 (cpu),   0.496882 (wall) --- both fixes
> Command execution time:   0.899000 (cpu),   0.908062 (wall) --- just lookup_symbol_aux_objfile fix
> Command execution time:   3.492000 (cpu),   3.491791 (wall) --- FSF GDB HEAD
>
> Benchmark on non-trivial application with    'p <tab><tab>':
> 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
>
>
> No regressions on {x86_64,x86_64-m32,i686}-fedora21pre-linux-gnu in standard
> and .gdb_index-enabled runs.  Neither of the patches should cause any visible
> behavior change.

Hi.
I've been playing with the patches a bit.
I still have some more research to do, I'd like to make sure I have a
deep understanding of why this works before this goes in.
Thanks.

For example, the count of calls to dict_hash before/after goes from 13.8M to 31.
I'm guessing one t hing we're doing here is coping with an artifact of
dwz: what was once one global block to represent the entire objfile is
now N.
[I'm sure the patches help in the non-dwz case, but I suspect it's less.
Which isn't to say the patches aren't useful.
I just need play with a few more examples.]

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

[Doug Evans]

On Mon, Oct 20, 2014 at 2:44 PM, Jan Kratochvil
<jan.kratochvil@redhat.com> wrote:
> [...]
> g++ -o slow slow.C -Wall -g $(pkg-config --libs gtkmm-3.0)
> gdb ./slow -ex 'b C::m' -ex 'maintenance set per-command space' -ex 'maintenance set per-command symtab' -ex 'maintenance set per-command time' -ex r
> [...]

Oh, btw, if you want to simplify this, replace all the maintenance
commands with "mt set per on", that'll turn everything on.

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

[Jan Kratochvil]

[-- Attachment #1: Type: text/plain, Size: 2023 bytes --]

On Wed, 22 Oct 2014 10:55:18 +0200, Doug Evans wrote:
> For example, the count of calls to dict_hash before/after goes from 13.8M to 31.
> I'm guessing one t hing we're doing here is coping with an artifact of
> dwz:

During my simple test on non-DWZ file (./gdb itself) it went 3684->3484.

The problem is that dict_cash(val) is called for the same val for each block
(== symtab).

On DWZ the saving is probably much larger as there are many more symtabs due
to DW_TAG_partial_unit ones.


> what was once one global block to represent the entire objfile is
> now N.

Without DWZ there are X global blocks for X primary symtabs for X CUs of
objfile.  With DWZ there are X+Y global blocks for X+Y primary symtabs for
X+Y CUs where Y are 'DW_TAG_partial_unit's.

For 'DW_TAG_partial_unit's (Ys) their blockvector is usually empty.  But not
always, I have found there typedef symbols, there can IMO be optimized-out
static variables etc.


> [I'm sure the patches help in the non-dwz case, but I suspect it's less.
> Which isn't to say the patches aren't useful.
> I just need play with a few more examples.]

I agree.

[patch 2/2] could needlessly performance-regress non-DWZ cases, therefore
I have put back original ALL_OBJFILE_PRIMARY_SYMTABS (instead of my
ALL_OBJFILE_SYMTABS) as it is perfectly sufficient.  For the performance
testcase of mine:

Benchmark on non-trivial application with    'p <tab><tab>':
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 additional 1.75x improvement, making the total improvement 26.8x.


No regressions on {x86_64,x86_64-m32,i686}-fedora21pre-linux-gnu in standard
and .gdb_index-enabled runs.  Neither of the patches should cause any visible
behavior change.


Thanks,
Jan

[-- Attachment #2: idxcache2doug.patch --]
[-- Type: text/plain, Size: 1160 bytes --]

gdb/
2014-10-23  Jan Kratochvil  <jan.kratochvil@redhat.com>

	* symtab.c (lookup_symbol_aux_objfile): Use ALL_OBJFILE_SYMTABS, inline
	lookup_block_symbol.

diff --git a/gdb/symtab.c b/gdb/symtab.c
index c530d50..da13861 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -1657,15 +1657,25 @@ lookup_symbol_aux_objfile (struct objfile *objfile, int block_index,
   const struct block *block;
   struct symtab *s;
 
+  gdb_assert (block_index == GLOBAL_BLOCK || block_index == STATIC_BLOCK);
+
   ALL_OBJFILE_PRIMARY_SYMTABS (objfile, s)
     {
+      struct dict_iterator dict_iter;
+
       bv = BLOCKVECTOR (s);
       block = BLOCKVECTOR_BLOCK (bv, block_index);
-      sym = lookup_block_symbol (block, name, domain);
-      if (sym)
+
+      for (sym = dict_iter_name_first (block->dict, name, &dict_iter);
+	   sym != NULL;
+	   sym = dict_iter_name_next (name, &dict_iter))
 	{
-	  block_found = block;
-	  return fixup_symbol_section (sym, objfile);
+	  if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
+				     SYMBOL_DOMAIN (sym), domain))
+	    {
+	      block_found = block;
+	      return fixup_symbol_section (sym, objfile);
+	    }
 	}
     }
 

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

[Doug Evans]

On Thu, Oct 23, 2014 at 11:24 AM, Jan Kratochvil
<jan.kratochvil@redhat.com> wrote:
> On Wed, 22 Oct 2014 10:55:18 +0200, Doug Evans wrote:
>> For example, the count of calls to dict_hash before/after goes from 13.8M to 31.
>> I'm guessing one t hing we're doing here is coping with an artifact of
>> dwz:
>
> During my simple test on non-DWZ file (./gdb itself) it went 3684->3484.
>
> The problem is that dict_cash(val) is called for the same val for each block
> (== symtab).
>
> On DWZ the saving is probably much larger as there are many more symtabs due
> to DW_TAG_partial_unit ones.

Much larger indeed.

One worry I have is that while this helps dwz does it harm something else.
Seems unlikely, but some simple measurements I took make me want to take more.

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).
Perhaps not what we want to do for partial syms (though maybe partial
syms could work similarly, haven't gotten that far).  But with an
index it seems clumsy to iterate over all symtabs and then go to the
index.

It should be easy enough to do a quick hack to do an experiment to
collect some data.
I'll try to get to it this weekend.

>> what was once one global block to represent the entire objfile is
>> now N.
>
> Without DWZ there are X global blocks for X primary symtabs for X CUs of
> objfile.  With DWZ there are X+Y global blocks for X+Y primary symtabs for
> X+Y CUs where Y are 'DW_TAG_partial_unit's.

Yep.

> For 'DW_TAG_partial_unit's (Ys) their blockvector is usually empty.  But not
> always, I have found there typedef symbols, there can IMO be optimized-out
> static variables etc.
>
>
>> [I'm sure the patches help in the non-dwz case, but I suspect it's less.
>> Which isn't to say the patches aren't useful.
>> I just need play with a few more examples.]
>
> I agree.
>
> [patch 2/2] could needlessly performance-regress non-DWZ cases, therefore
> I have put back original ALL_OBJFILE_PRIMARY_SYMTABS (instead of my
> ALL_OBJFILE_SYMTABS) as it is perfectly sufficient.  For the performance
> testcase of mine:
>
> Benchmark on non-trivial application with    'p <tab><tab>':
> 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 additional 1.75x improvement, making the total improvement 26.8x.
>
>
> No regressions on {x86_64,x86_64-m32,i686}-fedora21pre-linux-gnu in standard
> and .gdb_index-enabled runs.  Neither of the patches should cause any visible
> behavior change.
>
>
> Thanks,
> Jan
>
> gdb/
> 2014-10-23  Jan Kratochvil  <jan.kratochvil@redhat.com>
>
>         * symtab.c (lookup_symbol_aux_objfile): Use ALL_OBJFILE_SYMTABS, inline
>         lookup_block_symbol.
>
> diff --git a/gdb/symtab.c b/gdb/symtab.c
> index c530d50..da13861 100644
> --- a/gdb/symtab.c
> +++ b/gdb/symtab.c
> @@ -1657,15 +1657,25 @@ lookup_symbol_aux_objfile (struct objfile *objfile, int block_index,
>    const struct block *block;
>    struct symtab *s;
>
> +  gdb_assert (block_index == GLOBAL_BLOCK || block_index == STATIC_BLOCK);
> +
>    ALL_OBJFILE_PRIMARY_SYMTABS (objfile, s)
>      {
> +      struct dict_iterator dict_iter;
> +
>        bv = BLOCKVECTOR (s);
>        block = BLOCKVECTOR_BLOCK (bv, block_index);
> -      sym = lookup_block_symbol (block, name, domain);
> -      if (sym)
> +
> +      for (sym = dict_iter_name_first (block->dict, name, &dict_iter);
> +          sym != NULL;
> +          sym = dict_iter_name_next (name, &dict_iter))
>         {
> -         block_found = block;
> -         return fixup_symbol_section (sym, objfile);
> +         if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
> +                                    SYMBOL_DOMAIN (sym), domain))
> +           {
> +             block_found = block;
> +             return fixup_symbol_section (sym, objfile);
> +           }
>         }
>      }
>
>

This breaks an abstraction boundary, IWBN to preserve it.
[IOW, I look at dict_* as being an implementation detail of blocks.]

If we were to go this route (and apologies for the delay), can you
write a routine like lookup_block_symbol which does the above and call
that here instead?

lookup_block_symbol should live in block.c, not symtab.c.
That's where this new routine should go too.

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

[Doug Evans]

On Mon, Oct 20, 2014 at 2:44 PM, Jan Kratochvil
<jan.kratochvil@redhat.com> wrote:
> Hi,
>
> this patchset has been developed+tested only on top of
>         [patchv2] Fix 100x slowdown regression on DWZ files
>         https://sourceware.org/ml/gdb-patches/2014-10/msg00031.html
>
> [...]
> g++ -o slow slow.C -Wall -g $(pkg-config --libs gtkmm-3.0)
> gdb ./slow -ex 'b C::m' -ex 'maintenance set per-command space' -ex 'maintenance set per-command symtab' -ex 'maintenance set per-command time' -ex r
> [...]
> (gdb) p <tab><tab>
> Display all 183904 possibilities? (y or n) n
> (gdb) p/r var

Sorry I didn't mention this sooner.  I wanted to point this out since
it's a more straightforward way to expand symtabs.  Instead of using
"p <tab><tab>" to expand symtabs, there is "mt expand-symtabs".

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

[Jan Kratochvil]

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.
But then it will get fixed only for .gdb_index files while my two patches also
improve performance of non-.gdb_index files.

For each objfile .gdb_index presence is orthogonal to DWZ application.

Sure a question remains if we should care about performance of non-.gdb_index
files at all.  Even for continuous edit-build-debug cycles it is worth to run
gdb-add-index during each build.


> If we were to go this route (and apologies for the delay), can you
> write a routine like lookup_block_symbol which does the above and call
> that here instead?

OK.


Jan

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

[Doug Evans]

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.

> For each objfile .gdb_index presence is orthogonal to DWZ application.
>
> Sure a question remains if we should care about performance of non-.gdb_index
> files at all.  Even for continuous edit-build-debug cycles it is worth to run
> gdb-add-index during each build.

Or have the compiler/linker build the index.

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

[Doug Evans]

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

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

[Doug Evans]

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.

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

[Jan Kratochvil]

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

[patchv3 2/2] Accelerate lookup_symbol_aux_objfile 85x

[Jan Kratochvil]

[-- Attachment #1: Type: text/plain, Size: 858 bytes --]

On Fri, 24 Oct 2014 09:16:01 +0200, Doug Evans wrote:
> This breaks an abstraction boundary, IWBN to preserve it.
> [IOW, I look at dict_* as being an implementation detail of blocks.]
> 
> If we were to go this route (and apologies for the delay), can you
> write a routine like lookup_block_symbol which does the above and call
> that here instead?
> 
> lookup_block_symbol should live in block.c, not symtab.c.
> That's where this new routine should go too.

Done.

For the 'slow.C' test the performance gain is even higher; but I have not
re-benchmarked the 'non-trivial app':
	Command execution time: 26.540344 (cpu), 26.575254 (wall)
	->
	Command execution time: 0.310607 (cpu), 0.311062 (wall)
	 = 85x

OK for check-in?

No regressions on {x86_64,x86_64-m32,i686}-fedora21-linux-gnu native and in
DWZ and in -fdebug-types-section modes.


Thanks,
Jan

[-- Attachment #2: idx2.patch --]
[-- Type: text/plain, Size: 2806 bytes --]

gdb/
2014-11-28  Jan Kratochvil  <jan.kratochvil@redhat.com>

	* block.c (block_lookup_symbol_primary): New function.
	* block.h (block_lookup_symbol_primary): New declaration.
	* symtab.c (lookup_symbol_in_objfile_symtabs): Assert BLOCK_INDEX.
	Call block_lookup_symbol_primary.

diff --git a/gdb/block.c b/gdb/block.c
index 597d143..e791c73 100644
--- a/gdb/block.c
+++ b/gdb/block.c
@@ -746,3 +746,28 @@ block_lookup_symbol (const struct block *block, const char *name,
       return (sym_found);	/* Will be NULL if not found.  */
     }
 }
+
+/* See block.h.  */
+
+struct symbol *
+block_lookup_symbol_primary (const struct block *block, const char *name,
+			     const domain_enum domain)
+{
+  struct symbol *sym;
+  struct dict_iterator dict_iter;
+
+  /* Verify BLOCK is STATIC_BLOCK or GLOBAL_BLOCK.  */
+  gdb_assert (BLOCK_SUPERBLOCK (block) == NULL
+	      || BLOCK_SUPERBLOCK (BLOCK_SUPERBLOCK (block)) == NULL);
+
+  for (sym = dict_iter_name_first (block->dict, name, &dict_iter);
+       sym != NULL;
+       sym = dict_iter_name_next (name, &dict_iter))
+    {
+      if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
+				 SYMBOL_DOMAIN (sym), domain))
+	return sym;
+    }
+
+  return NULL;
+}
diff --git a/gdb/block.h b/gdb/block.h
index bd358d6..409a5c7 100644
--- a/gdb/block.h
+++ b/gdb/block.h
@@ -276,6 +276,14 @@ extern struct symbol *block_lookup_symbol (const struct block *block,
 					   const char *name,
 					   const domain_enum domain);
 
+/* Search BLOCK for symbol NAME in DOMAIN but only in primary symbol table of
+   BLOCK.  BLOCK must be STATIC_BLOCK or GLOBAL_BLOCK.  Function is useful if
+   one iterates all global/static blocks of an objfile.  */
+
+extern struct symbol *block_lookup_symbol_primary (const struct block *block,
+						   const char *name,
+						   const domain_enum domain);
+
 /* Macro to loop through all symbols in BLOCK, in no particular
    order.  ITER helps keep track of the iteration, and must be a
    struct block_iterator.  SYM points to the current symbol.  */
diff --git a/gdb/symtab.c b/gdb/symtab.c
index 345c20d..fd93fb8 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -1618,6 +1618,8 @@ lookup_symbol_in_objfile_symtabs (struct objfile *objfile, int block_index,
 {
   struct compunit_symtab *cust;
 
+  gdb_assert (block_index == GLOBAL_BLOCK || block_index == STATIC_BLOCK);
+
   ALL_OBJFILE_COMPUNITS (objfile, cust)
     {
       const struct blockvector *bv;
@@ -1626,7 +1628,7 @@ lookup_symbol_in_objfile_symtabs (struct objfile *objfile, int block_index,
 
       bv = COMPUNIT_BLOCKVECTOR (cust);
       block = BLOCKVECTOR_BLOCK (bv, block_index);
-      sym = block_lookup_symbol (block, name, domain);
+      sym = block_lookup_symbol_primary (block, name, domain);
       if (sym)
 	{
 	  block_found = block;

Re: [patchv3 2/2] Accelerate lookup_symbol_aux_objfile 85x

[Doug Evans]

Jan Kratochvil <jan.kratochvil@redhat.com> writes:

> On Fri, 24 Oct 2014 09:16:01 +0200, Doug Evans wrote:
>> This breaks an abstraction boundary, IWBN to preserve it.
>> [IOW, I look at dict_* as being an implementation detail of blocks.]
>> 
>> If we were to go this route (and apologies for the delay), can you
>> write a routine like lookup_block_symbol which does the above and call
>> that here instead?
>> 
>> lookup_block_symbol should live in block.c, not symtab.c.
>> That's where this new routine should go too.
>
> Done.
>
> For the 'slow.C' test the performance gain is even higher; but I have not
> re-benchmarked the 'non-trivial app':
> 	Command execution time: 26.540344 (cpu), 26.575254 (wall)
> 	->
> 	Command execution time: 0.310607 (cpu), 0.311062 (wall)
> 	 = 85x
>
> OK for check-in?
>
> No regressions on {x86_64,x86_64-m32,i686}-fedora21-linux-gnu native and in
> DWZ and in -fdebug-types-section modes.
>
>
> Thanks,
> Jan
> gdb/
> 2014-11-28  Jan Kratochvil  <jan.kratochvil@redhat.com>
>
> 	* block.c (block_lookup_symbol_primary): New function.
> 	* block.h (block_lookup_symbol_primary): New declaration.
> 	* symtab.c (lookup_symbol_in_objfile_symtabs): Assert BLOCK_INDEX.
> 	Call block_lookup_symbol_primary.

Hi.

I was reviewing all the callers of lookup_symbol_in_objfile_symtabs.

This patch assumes we're looping over all objfiles,
but some callers aren't.  e.g., lookup_symbol_in_objfile_from_linkage_name.
It seems like we'll need to make a copy of lookup_symbol_in_objfile_symtabs
and call that in lookup_symbol_in_objfile (plus I'd add some comments
to lookup_symbol_in_objfile warning the reader that included symtabs
are not searched).

I could be missing something though.

Re: [patchv3 2/2] Accelerate lookup_symbol_aux_objfile 85x

[Jan Kratochvil]

On Tue, 02 Dec 2014 04:06:28 +0100, Doug Evans wrote:
> I was reviewing all the callers of lookup_symbol_in_objfile_symtabs.

I do not see why, see below.


> This patch assumes we're looping over all objfiles,

No.  each objfile is considered completely independent wrt various kinds of
symbol tables and their inter-refefences.

Function block_lookup_symbol_primary() assumes we're looping over all
'compunit_symtabs's (of an objfile).  This is satisfied by the current only
caller of block_lookup_symbol_primary()
(which is lookup_symbol_in_objfile_symtabs()).


> but some callers aren't.  e.g., lookup_symbol_in_objfile_from_linkage_name.
> It seems like we'll need to make a copy of lookup_symbol_in_objfile_symtabs
> and call that in lookup_symbol_in_objfile (plus I'd add some comments
> to lookup_symbol_in_objfile warning the reader that included symtabs
> are not searched).
> 
> I could be missing something though.

I also can be missing something but I do not see why
block_lookup_symbol_primary() should have any dependencies on other objfiles
than the one that is passed to it.


Thanks,
Jan

Re: [patchv3 2/2] Accelerate lookup_symbol_aux_objfile 85x

[Doug Evans]

On Wed, Dec 3, 2014 at 10:05 AM, Jan Kratochvil
<jan.kratochvil@redhat.com> wrote:
> Function block_lookup_symbol_primary() assumes we're looping over all
> 'compunit_symtabs's (of an objfile).

Ah, righto.

LGTM

[commit] [patchv3 2/2] Accelerate lookup_symbol_aux_objfile 85x

[Jan Kratochvil]

On Thu, 04 Dec 2014 07:21:15 +0100, Doug Evans wrote:
> On Wed, Dec 3, 2014 at 10:05 AM, Jan Kratochvil
> <jan.kratochvil@redhat.com> wrote:
> > Function block_lookup_symbol_primary() assumes we're looping over all
> > 'compunit_symtabs's (of an objfile).
> 
> Ah, righto.
> 
> LGTM

Checked in:
	ba715d7fe49c8a59660fbd571b935b29eb7cfbdb


Thanks,
Jan