Re: [patch] Improve symbol lookup performance noted in PR 15519

[Pedro Alves <palves@redhat.com>]

On 05/31/2013 11:33 PM, Doug Evans wrote:
> Pedro Alves writes:
>  > On 05/31/2013 12:27 AM, Doug Evans wrote:
>  > > Hi.
>  > > Here's the patch I intend to check in to "fix"
>  > > http://sourceware.org/bugzilla/show_bug.cgi?id=15519
>  > > [It's not a complete "fix", there's still some performance gains
>  > > to be had, but I'm leaving that for a separate pass.  This gets
>  > > us >95% of the way there, at least in the benchmarks I've been using,
>  > > including the one in the PR.  Thanks Paul!]
>  > > 
>  > > No regressions on amd64-linux, with/without Fission.
>  > > 
>  > > I'll let it sit for a few days in case there are any more comments.
>  > > I'd also like to commit this to the 7.6 branch.  Ok Joel?
>  > > [I need to rerun the testsuite in that tree before committing there.]
>  > 
>  > Thanks!
>  > 
>  > Absolutely no objections, but for my own education, and for the archives,
>  > could you describe the gist of it?  E.g., what is it that is slow, and what
>  > is it that is being avoided to get the speedup?  (where's the win?)
>  > It isn't super obvious to me from reading the patch.
> 
> I think the speedup can be illustrated nicely with this example.
> 
> Apply this patch to the before/after gdbs.
> 
> --- cp-namespace.c~	2013-05-31 12:23:44.000000000 -0700
> +++ cp-namespace.c	2013-05-31 12:28:26.000000000 -0700
> @@ -250,6 +250,7 @@ cp_lookup_symbol_in_namespace (const cha
>                                 const struct block *block,
>                                 const domain_enum domain, int search)
>  {
> +  printf_filtered ("cp_lookup_symbol_in_namespace (\"%s\", \"%s\", block=%p, search=%d)\n", namespace, name, block, search);
>    if (namespace[0] == '\0')
>      {
>        return lookup_symbol_file (name, block, domain, 0, search);
> 
> Running gdb on one example I see this in the "before" case (cvs head):
> 
> (gdb) p masterCatalog->traceLog->slots
> cp_lookup_symbol_in_namespace ("", "PlatformRecords", block=0x2be2ab0, search=1)
...
> $1 = 200
> (gdb) 
> 
> Running gdb on the same example in the "after" case:
> 
> (gdb) p masterCatalog->traceLog->slots
> cp_lookup_symbol_in_namespace ("", "PlatformRecords", block=0x2d56920, search=1)
...
> $1 = 200
> (gdb) 
> 
> Now imagine scaling up the excessive duplicate searches due to
> - a larger binary (bigger/more complex classes, namespaces, imports, etc.)
> - or a deeper call stack (some places iterate over the block chain),
> - or because it's being done in some loop in a macro.
> The latter is Paul's case.
> In another example (Chrome) a 5 second lookup becomes 10s of minutes!
> 
> So the speedup comes from calling a more specific lookup routine for the task at hand.

Thanks.

What I guess I'm still missing to understand it,
is a short blurb describing what is being skipped and why is
it safe to be skipped.  :-)

Just to make sure I understand the change -- I see
cp_lookup_symbol_namespace does:

...
  /* Search for name in namespaces imported to this and parent
     blocks.  */
  while (block != NULL)
    {
      sym = cp_lookup_symbol_imports (scope, name, block,
				      domain, 0, 1);

      if (sym)
	return sym;

      block = BLOCK_SUPERBLOCK (block);
    }

and a chunk of the speedup comes from skipping that, correct?
That is, it is supposedly unnecessary to look symbol imports
when looking up a symbol in a baseclass, right?

The patch then also replaces a lookup_symbol_static with a specific
block call followed by a fallback lookup_static_symbol_aux search over all
objfiles, by always doing the lookup_static_symbol_aux search over
all objfiles.  It makes me wonder if it was there for a reason things were
done that way before, like for something like the same named class/methods
being implemented/hidden/private in different sos/dlls (therefore not
really subject to ODR), therefore making it desirable to lookup in the
same context first.  I have no idea, probably not.  :-)  I guess I'm just
after getting the analysis/conclusion that led to the change
recorded for posterity.  :-)

> Also note that even in the "after" case we are still doing
> a lot of duplicate lookups.
> cp-namespace.c is a bit clumsy in some of the lookups it does.
> Although it's hampered by having to work with the data structures
> gdb provides it.  My plan is to work on both this summer.

Thanks.

-- 
Pedro Alves