Re: Optimization of add_dt_to_dt_list() in resolve.c

[Richard Biener <richard.guenther@gmail.com>]

On Fri, May 25, 2018 at 9:06 AM Richard Biener <richard.guenther@gmail.com>
wrote:

> On Fri, May 25, 2018 at 12:53 AM Andrew Benson <
abenson@carnegiescience.edu>
> wrote:

> > I've been attempting to track down some of the causes of very long
compile
> > times for files which use modules that contain a large number of
symbols.
> The
> > worst case offender in my code takes around 12 minutes to compile.

> > After profiling f951 for this source file it turns out that the majority
> of the
> > time is spent in add_dt_to_dt_list() in resolve.c. In cases where the
> number
> > of symbols imported becomes very large (~10,000 in some cases in this
> code),
> > the O(N) search in this function becomes inefficient.

> > A simple optimization for this problem seems to be to just have the
> gfc_symbol
> > struct include a pointer back to the corresponding entry in the
> > gfc_derived_types list. It's then fast to check if a symbol is already
on
> that
> > list by checking if this pointer is non-null. (It could just as easily
be
> an
> > int in gfc_symbol which indicates if the symbol is already added to the
> list -
> > I don't know if having a pointer to the list entry is useful for any
other
> > reason.)

> > With this change in place compile times are much faster - my worst case
> > offender now takes just under 1 minute to compile.

> > My patch is attached. I freely admit that I have only a very shallow
> > understanding of the inner workings of the compiler, so I would not be
> > surprised if there are good reasons not to do this. I did "make
> check-fortran"
> > and did not see any failures. If any one wants to try this out and/or
> provide
> > any feedback I'd be happy to hear it.

> It looks like it would be cheaper to simply embed gtc_dt_list *next in
> gfc_symbol?
> (in case a gfc_symbol can be only on one gfc_dt_list which your patch
> assumes as well)

Note you'll need to make the list cyclic to make the member test work
as sym->next_dt != NULL.

Also note that gfc_get_derived_type has another linear list walk so it
looks like derived type processing is still quadratic in the number of
derived types after the change.  That suggests that eventually
making the derived_types list a hash-map of gfc_symbol to
the common derived type (symbol) would be a better fix, thus doing
the merging at dt-"list" insertion time.

Of course that's likely a bigger change that needs more thorough
understanding
of how derived types work.  A fix along your idea looks simple enough
and has obvious benefits as you show so it might be even appropriate for
release branches.

Richard.

> Richard.

> > Thanks,
> > Andrew

> > --

> > * Andrew Benson:
http://users.obs.carnegiescience.edu/abenson/contact.html

> > * Galacticus: https://bitbucket.org/abensonca/galacticus