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

Pedro Alves
2013-06-03T17:27:48Z

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