Optimization of add_dt_to_dt_list() in resolve.c

[Andrew Benson]

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

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.diff
Type: text/x-patch
Size: 8423 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20180529/90770f5d/attachment.bin>