Optimization of add_dt_to_dt_list() in resolve.c

[Richard Biener]

On Tue, May 29, 2018 at 10:24 PM Andrew Benson <abenson@carnegiescience.edu>
wrote:

> Yes - definitely possible to remove gfc_dt_list entirely - new patch is
> attached.

This looks good to me but it still requires review/ack from fortran people.

Note another trick commonly used for cyclic lists is to make the "head"
always present which could be done by making gfc_derived_types a
gfc_symbol  (non-pointer), chaining to itself.  Then you can elide
the if (gfc_derived_types) checks and iterate via

for (gfc_sybol *sym = gfc_derived_types.dt_next; sym != &gfc_derived_types;
sym = sym->dt_next)
   ...

similar appending and removing lose some special cases.

Having a global gfc_symbol with just one pointer in it used may seem a
litte ugly though
(and you have to init it somewhere suitable unless you want to write up a
huge mostly
zero static initializer).

Richard.

> Thanks,
> Andrew

> On Monday, May 28, 2018 11:54:41 AM PDT Richard Biener wrote:
> > 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


> --

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

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