Optimization of add_dt_to_dt_list() in resolve.c

[Richard Biener]

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)

Richard.

> Thanks,
> Andrew

> --

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

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