Optimization of add_dt_to_dt_list() in resolve.c

[Richard Biener]

On Fri, May 25, 2018 at 11:54 PM Andrew Benson <abenson@carnegiescience.edu>
wrote:

> Richard:

> Thanks for the suggestion. I changed my patch (new version attached) so
that
> there's a *dt_next in gfc_symbol, which is now used to construct the
> (circular) linked list. There were a couple places where I had to change
the
> order in which clean up of symbols and derived type lists were done -
it's now
> necessary to free the derived type list before its associated symbols
(since
> the symbols carry the links for the derived type list).

Hmm, it still has the indirection via gfc_dt_list.  I think it should be
possible
to do away with gfc_dt_list objects alltogether by no doing
sym->dt_next->derived
but sym->derived thus

@@ -1611,6 +1611,9 @@ typedef struct gfc_symbol

    /* Link to corresponding association-list if this is an associate name.
  */
    struct gfc_association_list *assoc;
+
+  /* Link to next entry in derived type list */
+  gfc_symbol *dt_next;
  }
  gfc_symbol;

that means for example gfc_free_dt_list can be simply removed.  The
gfc_derived_types global would then point to the first derived type
directly.

Richard.

> This passes "make check-fortran" and seems to retain the speed-up from my
> original patch.

> Thanks,
> Andrew

> On Friday, May 25, 2018 9:06:22 AM PDT Richard Biener 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)
> >
> > Richard.
> >
> > > Thanks,
> > > Andrew
> > >
> > > --
> > >
> > > * Andrew Benson:
http://users.obs.carnegiescience.edu/abenson/contact.html
> > >
> > > * Galacticus: https://bitbucket.org/abensonca/galacticus


> --

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

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