Optimization of add_dt_to_dt_list() in resolve.c

[Janus Weil]

Hi Andrew,

2018-05-29 22:24 GMT+02:00 Andrew Benson <abenson@carnegiescience.edu>:
> Yes - definitely possible to remove gfc_dt_list entirely - new patch is
> attached.

since you already got some 'contentual' comments, I'll give you some
more 'formal' ones ...


+  if (!derived->dt_next) {
+    if (gfc_derived_types) {
+      derived->dt_next = gfc_derived_types->dt_next;
+      gfc_derived_types->dt_next = derived;
+    } else {
+      derived->dt_next = derived;
+    }
+    gfc_derived_types = derived;
+  }

Here and in some other hunks you're not conforming with the GNU coding
style, which demands that opening and closing braces should be on
separate lines (and at a new indentation level).


-  for (dt = gfc_derived_types; dt; dt = dt->next)
-    gfc_copy_dt_decls_ifequal (derived, dt->derived, false);
-
+  if (gfc_derived_types) {
+    dt = gfc_derived_types;
+    for (;;)
+      {
+    gfc_copy_dt_decls_ifequal (derived, dt, false);
+    if (dt->dt_next == gfc_derived_types)
+      break;
+    dt = dt->dt_next;
+      }
+  }

Is there a particular reason why you changed the loop to "for (;;)" ?
I find the old style a bit clearer and more compact. Also I think it's
more common in gfortran.

Btw, do you already have a copyright assignment on file? If not,
you'll probably need one (see https://gcc.gnu.org/contribute.html).

Thanks for your contribution and welcome to the gfortran team :)

Cheers,
Janus



> 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