Re: Optimization of add_dt_to_dt_list() in resolve.c

[Andrew Benson <abenson@carnegiescience.edu>]

[-- Attachment #1: Type: text/plain, Size: 4317 bytes --]

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

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 8423 bytes --]

Index: gcc/fortran/gfortran.h
===================================================================
--- gcc/fortran/gfortran.h	(revision 260682)
+++ gcc/fortran/gfortran.h	(working copy)
@@ -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 */
+  struct gfc_symbol *dt_next;
 }
 gfc_symbol;
 
@@ -1712,19 +1715,9 @@ typedef struct gfc_symtree
 }
 gfc_symtree;
 
-/* A linked list of derived types in the namespace.  */
-typedef struct gfc_dt_list
-{
-  struct gfc_symbol *derived;
-  struct gfc_dt_list *next;
-}
-gfc_dt_list;
+/* A list of all derived types.  */
+extern gfc_symbol *gfc_derived_types;
 
-#define gfc_get_dt_list() XCNEW (gfc_dt_list)
-
-  /* A list of all derived types.  */
-  extern gfc_dt_list *gfc_derived_types;
-
 typedef struct gfc_oacc_routine_name
 {
   struct gfc_symbol *sym;
@@ -1809,7 +1802,7 @@ typedef struct gfc_namespace
 
   gfc_charlen *cl_list;
 
-  gfc_dt_list *derived_types;
+  gfc_symbol *derived_types;
 
   int save_all, seen_save, seen_implicit_none;
 
Index: gcc/fortran/parse.c
===================================================================
--- gcc/fortran/parse.c	(revision 260682)
+++ gcc/fortran/parse.c	(working copy)
@@ -6047,7 +6047,7 @@ add_global_program (void)
 static void
 resolve_all_program_units (gfc_namespace *gfc_global_ns_list)
 {
-  gfc_free_dt_list ();
+  gfc_derived_types = NULL;
   gfc_current_ns = gfc_global_ns_list;
   for (; gfc_current_ns; gfc_current_ns = gfc_current_ns->sibling)
     {
Index: gcc/fortran/resolve.c
===================================================================
--- gcc/fortran/resolve.c	(revision 260682)
+++ gcc/fortran/resolve.c	(working copy)
@@ -2504,7 +2504,7 @@ resolve_global_procedure (gfc_symbol *sym, locus *
       /* Resolve the gsymbol namespace if needed.  */
       if (!gsym->ns->resolved)
 	{
-	  gfc_dt_list *old_dt_list;
+	  gfc_symbol *old_dt_list;
 
 	  /* Stash away derived types so that the backend_decls do not
 	     get mixed up.  */
@@ -13435,16 +13435,17 @@ resolve_typebound_procedures (gfc_symbol* derived)
 static void
 add_dt_to_dt_list (gfc_symbol *derived)
 {
-  gfc_dt_list *dt_list;
 
-  for (dt_list = gfc_derived_types; dt_list; dt_list = dt_list->next)
-    if (derived == dt_list->derived)
-      return;
-
-  dt_list = gfc_get_dt_list ();
-  dt_list->next = gfc_derived_types;
-  dt_list->derived = derived;
-  gfc_derived_types = dt_list;
+  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;
+  }
+  
 }
 
 
Index: gcc/fortran/symbol.c
===================================================================
--- gcc/fortran/symbol.c	(revision 260682)
+++ gcc/fortran/symbol.c	(working copy)
@@ -107,7 +107,7 @@ gfc_namespace *gfc_global_ns_list;
 
 gfc_gsymbol *gfc_gsym_root = NULL;
 
-gfc_dt_list *gfc_derived_types;
+gfc_symbol *gfc_derived_types;
 
 static gfc_undo_change_set default_undo_chgset_var = { vNULL, vNULL, NULL };
 static gfc_undo_change_set *latest_undo_chgset = &default_undo_chgset_var;
@@ -3119,6 +3119,7 @@ gfc_new_symbol (const char *name, gfc_namespace *n
   p->common_block = NULL;
   p->f2k_derived = NULL;
   p->assoc = NULL;
+  p->dt_next = NULL;
   p->fn_result_spec = 0;
 
   return p;
@@ -3878,23 +3879,6 @@ free_sym_tree (gfc_symtree *sym_tree)
 }
 
 
-/* Free the derived type list.  */
-
-void
-gfc_free_dt_list (void)
-{
-  gfc_dt_list *dt, *n;
-
-  for (dt = gfc_derived_types; dt; dt = n)
-    {
-      n = dt->next;
-      free (dt);
-    }
-
-  gfc_derived_types = NULL;
-}
-
-
 /* Free the gfc_equiv_info's.  */
 
 static void
@@ -4080,7 +4064,7 @@ gfc_symbol_done_2 (void)
       gfc_free_namespace (gfc_current_ns);
       gfc_current_ns = NULL;
     }
-  gfc_free_dt_list ();
+  gfc_derived_types = NULL;
 
   enforce_single_undo_checkpoint ();
   free_undo_change_set_data (*latest_undo_chgset);
@@ -4343,7 +4327,7 @@ gfc_get_gsymbol (const char *name)
 static gfc_symbol *
 get_iso_c_binding_dt (int sym_id)
 {
-  gfc_dt_list *dt_list;
+  gfc_symbol *dt_list;
 
   dt_list = gfc_derived_types;
 
@@ -4350,15 +4334,17 @@ get_iso_c_binding_dt (int sym_id)
   /* Loop through the derived types in the name list, searching for
      the desired symbol from iso_c_binding.  Search the parent namespaces
      if necessary and requested to (parent_flag).  */
-  while (dt_list != NULL)
-    {
-      if (dt_list->derived->from_intmod != INTMOD_NONE
-	  && dt_list->derived->intmod_sym_id == sym_id)
-        return dt_list->derived;
+  if (dt_list) {
+    while (dt_list->dt_next != gfc_derived_types)
+      {
+	if (dt_list->from_intmod != INTMOD_NONE
+	    && dt_list->intmod_sym_id == sym_id)
+	  return dt_list;
+	
+	dt_list = dt_list->dt_next;
+      }
+  }
 
-      dt_list = dt_list->next;
-    }
-
   return NULL;
 }
 
@@ -4762,11 +4748,13 @@ generate_isocbinding_symbol (const char *mod_name,
       if (tmp_sym->attr.flavor == FL_DERIVED
 	  && !get_iso_c_binding_dt (tmp_sym->intmod_sym_id))
 	{
-	  gfc_dt_list *dt_list;
-	  dt_list = gfc_get_dt_list ();
-	  dt_list->derived = tmp_sym;
-	  dt_list->next = gfc_derived_types;
-  	  gfc_derived_types = dt_list;
+	  if (gfc_derived_types) {
+	    tmp_sym->dt_next = gfc_derived_types->dt_next;
+	    gfc_derived_types->dt_next = tmp_sym;
+	  } else {
+	    tmp_sym->dt_next = tmp_sym;
+	  }
+	  gfc_derived_types = tmp_sym;
         }
 
       return tmp_symtree;
@@ -4874,7 +4862,6 @@ generate_isocbinding_symbol (const char *mod_name,
       case ISOCBINDING_FUNPTR:
 	{
 	  gfc_symbol *dt_sym;
-	  gfc_dt_list **dt_list_ptr = NULL;
 	  gfc_component *tmp_comp = NULL;
 
 	  /* Generate real derived type.  */
@@ -4936,18 +4923,14 @@ generate_isocbinding_symbol (const char *mod_name,
 	  dt_sym->ts.u.derived = dt_sym;
 
 	  /* Add the symbol created for the derived type to the current ns.  */
-	  dt_list_ptr = &(gfc_derived_types);
-	  while (*dt_list_ptr != NULL && (*dt_list_ptr)->next != NULL)
-	    dt_list_ptr = &((*dt_list_ptr)->next);
-
-	  /* There is already at least one derived type in the list, so append
-	     the one we're currently building for c_ptr or c_funptr.  */
-	  if (*dt_list_ptr != NULL)
-	    dt_list_ptr = &((*dt_list_ptr)->next);
-	  (*dt_list_ptr) = gfc_get_dt_list ();
-	  (*dt_list_ptr)->derived = dt_sym;
-	  (*dt_list_ptr)->next = NULL;
-
+	  if (gfc_derived_types) {
+	    dt_sym->dt_next = gfc_derived_types->dt_next;
+	    gfc_derived_types->dt_next = dt_sym;
+	  } else {
+	    dt_sym->dt_next = dt_sym;
+	  }
+	  gfc_derived_types = dt_sym;
+      	  
 	  gfc_add_component (dt_sym, "c_address", &tmp_comp);
 	  if (tmp_comp == NULL)
 	    gcc_unreachable ();
Index: gcc/fortran/trans-types.c
===================================================================
--- gcc/fortran/trans-types.c	(revision 260682)
+++ gcc/fortran/trans-types.c	(working copy)
@@ -2534,7 +2534,7 @@ gfc_get_derived_type (gfc_symbol * derived, int co
   bool got_canonical = false;
   bool unlimited_entity = false;
   gfc_component *c;
-  gfc_dt_list *dt;
+  gfc_symbol *dt;
   gfc_namespace *ns;
   tree tmp;
   bool coarray_flag;
@@ -2599,13 +2599,18 @@ gfc_get_derived_type (gfc_symbol * derived, int co
 	   ns->translated && !got_canonical;
 	   ns = ns->sibling)
 	{
-	  dt = ns->derived_types;
-	  for (; dt && !canonical; dt = dt->next)
-	    {
-	      gfc_copy_dt_decls_ifequal (dt->derived, derived, true);
-	      if (derived->backend_decl)
-		got_canonical = true;
-	    }
+	  if (ns->derived_types) {
+	    dt = ns->derived_types;
+	    for (;;)
+	      {
+		gfc_copy_dt_decls_ifequal (dt, derived, true);
+		if (derived->backend_decl)
+		  got_canonical = true;
+		if (dt->dt_next == ns->derived_types)
+		  break;
+		dt = dt->dt_next;
+	      }
+	  }
 	}
     }
 
@@ -2867,9 +2872,16 @@ copy_derived_types:
 	}
     }
 
-  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;
+      }
+  }
   return derived->backend_decl;
 }