Optimization in load_generic_interfaces()

Optimization in load_generic_interfaces()

[Andrew Benson]

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

I'm continuing to look for optimizations to improve compile times for files 
which USE large numbers of modules containing large numbers of symbols. 

When the number of symbols becomes very large, find_symbol() becomes a slow-
point, because it can't use the structure of the balanced binary tree to 
rapidly search the symtree, so just has to go through the whole tree until it 
finds (or doesn't find) the symbol.

I don't see a simple way to improve the speed of this function, but there 
seems to be a simple change in load_generic_interfaces() which gives 
significant speed up:

Index: gcc/fortran/module.c
===================================================================
--- gcc/fortran/module.c        (revision 263667)
+++ gcc/fortran/module.c        (working copy)
@@ -4559,9 +4559,6 @@ load_generic_interfaces (void)
          /* Decide if we need to load this one or not.  */
          p = find_use_name_n (name, &i, false);
 
-         st = find_symbol (gfc_current_ns->sym_root,
-                           name, module_name, 1);
-
          if (!p || gfc_find_symbol (p, NULL, 0, &sym))
            {
              /* Skip the specific names for these cases.  */
@@ -4570,6 +4567,9 @@ load_generic_interfaces (void)
              continue;
            }
 
+         st = find_symbol (gfc_current_ns->sym_root,
+                           name, module_name, 1);
+
          /* If the symbol exists already and is being USEd without being
             in an ONLY clause, do not load a new symtree(11.3.2).  */
          if (!only_flag && st)


This just delays the call to find_symbol() until after the first test of whether 
the symbol needs to be loaded  - if that test fails then find_symbol() is never 
called.

This has no significant effect on compile time for files which import small 
numbers of symbols. But for cases where the number is large I find that the 
compile time can be reduced by up to 40% in the cases I've tried.

The change passes all regression tests cleanly.

-Andrew

-- 

* 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: 847 bytes --]

Index: gcc/fortran/module.c
===================================================================
--- gcc/fortran/module.c	(revision 263667)
+++ gcc/fortran/module.c	(working copy)
@@ -4559,9 +4559,6 @@ load_generic_interfaces (void)
 	  /* Decide if we need to load this one or not.  */
 	  p = find_use_name_n (name, &i, false);
 
-	  st = find_symbol (gfc_current_ns->sym_root,
-			    name, module_name, 1);
-
 	  if (!p || gfc_find_symbol (p, NULL, 0, &sym))
 	    {
 	      /* Skip the specific names for these cases.  */
@@ -4570,6 +4567,9 @@ load_generic_interfaces (void)
 	      continue;
 	    }
 
+	  st = find_symbol (gfc_current_ns->sym_root,
+			    name, module_name, 1);
+
 	  /* If the symbol exists already and is being USEd without being
 	     in an ONLY clause, do not load a new symtree(11.3.2).  */
 	  if (!only_flag && st)

[-- Attachment #3: ChangeLog --]
[-- Type: text/x-changelog, Size: 165 bytes --]

2018-08-20  Andrew Benson  <abenson@carnegiescience.edu>

	* module.c (load_generic_interfaces): Move call to find_symbol()
	so that only occurs if actually needed.

Re: Optimization in load_generic_interfaces()

[Thomas Koenig]

Hi Andrew,

[please also copy in gcc-patches for patches]

> I'm continuing to look for optimizations to improve compile times for files
> which USE large numbers of modules containing large numbers of symbols.
> 
> When the number of symbols becomes very large, find_symbol() becomes a slow-
> point, because it can't use the structure of the balanced binary tree to
> rapidly search the symtree, so just has to go through the whole tree until it
> finds (or doesn't find) the symbol.
> 
> I don't see a simple way to improve the speed of this function, but there
> seems to be a simple change in load_generic_interfaces() which gives
> significant speed up:
> 
> Index: gcc/fortran/module.c
> ===================================================================
> --- gcc/fortran/module.c        (revision 263667)
> +++ gcc/fortran/module.c        (working copy)
> @@ -4559,9 +4559,6 @@ load_generic_interfaces (void)
>            /* Decide if we need to load this one or not.  */
>            p = find_use_name_n (name, &i, false);
>   
> -         st = find_symbol (gfc_current_ns->sym_root,
> -                           name, module_name, 1);
> -
>            if (!p || gfc_find_symbol (p, NULL, 0, &sym))
>              {
>                /* Skip the specific names for these cases.  */
> @@ -4570,6 +4567,9 @@ load_generic_interfaces (void)
>                continue;
>              }
>   
> +         st = find_symbol (gfc_current_ns->sym_root,
> +                           name, module_name, 1);
> +
>            /* If the symbol exists already and is being USEd without being
>               in an ONLY clause, do not load a new symtree(11.3.2).  */
>            if (!only_flag && st)
> 
> 
> This just delays the call to find_symbol() until after the first test of whether
> the symbol needs to be loaded  - if that test fails then find_symbol() is never
> called.
> 
> This has no significant effect on compile time for files which import small
> numbers of symbols. But for cases where the number is large I find that the
> compile time can be reduced by up to 40% in the cases I've tried.
> 
> The change passes all regression tests cleanly.

The patch is OK for trunk.

Thanks!

Regards

	Thomas

Re: Optimization in load_generic_interfaces()

[Andrew Benson]

Hi Thomas,

Thanks for the review and approval (and for reminding me to CC gcc-patches). 

I'm still working on getting my sourceware account for svn access set up, so I 
can't commit the patch myself yet. If you (or anyone else) wants to go ahead 
an commit it that would be good - otherwise I'll do so as soon as I have write 
access.

Thanks,
Andrew

On Wednesday, August 22, 2018 5:43:30 PM PDT Thomas Koenig wrote:
> Hi Andrew,
> 
> [please also copy in gcc-patches for patches]
> 
> > I'm continuing to look for optimizations to improve compile times for
> > files
> > which USE large numbers of modules containing large numbers of symbols.
> > 
> > When the number of symbols becomes very large, find_symbol() becomes a
> > slow- point, because it can't use the structure of the balanced binary
> > tree to rapidly search the symtree, so just has to go through the whole
> > tree until it finds (or doesn't find) the symbol.
> > 
> > I don't see a simple way to improve the speed of this function, but there
> > seems to be a simple change in load_generic_interfaces() which gives
> > significant speed up:
> > 
> > Index: gcc/fortran/module.c
> > ===================================================================
> > --- gcc/fortran/module.c        (revision 263667)
> > +++ gcc/fortran/module.c        (working copy)
> > @@ -4559,9 +4559,6 @@ load_generic_interfaces (void)
> > 
> >            /* Decide if we need to load this one or not.  */
> >            p = find_use_name_n (name, &i, false);
> > 
> > -         st = find_symbol (gfc_current_ns->sym_root,
> > -                           name, module_name, 1);
> > -
> > 
> >            if (!p || gfc_find_symbol (p, NULL, 0, &sym))
> >            
> >              {
> >              
> >                /* Skip the specific names for these cases.  */
> > 
> > @@ -4570,6 +4567,9 @@ load_generic_interfaces (void)
> > 
> >                continue;
> >              
> >              }
> > 
> > +         st = find_symbol (gfc_current_ns->sym_root,
> > +                           name, module_name, 1);
> > +
> > 
> >            /* If the symbol exists already and is being USEd without being
> >            
> >               in an ONLY clause, do not load a new symtree(11.3.2).  */
> >            
> >            if (!only_flag && st)
> > 
> > This just delays the call to find_symbol() until after the first test of
> > whether the symbol needs to be loaded  - if that test fails then
> > find_symbol() is never called.
> > 
> > This has no significant effect on compile time for files which import
> > small
> > numbers of symbols. But for cases where the number is large I find that
> > the
> > compile time can be reduced by up to 40% in the cases I've tried.
> > 
> > The change passes all regression tests cleanly.
> 
> The patch is OK for trunk.
> 
> Thanks!
> 
> Regards
> 
> 	Thomas


-- 

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

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

Re: Optimization in load_generic_interfaces()

[Andrew Benson]

Hi Thomas,

I have my sourceware account active now, so I should be able to commit this 
myself. I'll do so right away.

Thanks,
Andrew

On Wednesday, August 22, 2018 5:43:30 PM PDT Thomas Koenig wrote:
> Hi Andrew,
> 
> [please also copy in gcc-patches for patches]
> 
> > I'm continuing to look for optimizations to improve compile times for
> > files
> > which USE large numbers of modules containing large numbers of symbols.
> > 
> > When the number of symbols becomes very large, find_symbol() becomes a
> > slow- point, because it can't use the structure of the balanced binary
> > tree to rapidly search the symtree, so just has to go through the whole
> > tree until it finds (or doesn't find) the symbol.
> > 
> > I don't see a simple way to improve the speed of this function, but there
> > seems to be a simple change in load_generic_interfaces() which gives
> > significant speed up:
> > 
> > Index: gcc/fortran/module.c
> > ===================================================================
> > --- gcc/fortran/module.c        (revision 263667)
> > +++ gcc/fortran/module.c        (working copy)
> > @@ -4559,9 +4559,6 @@ load_generic_interfaces (void)
> > 
> >            /* Decide if we need to load this one or not.  */
> >            p = find_use_name_n (name, &i, false);
> > 
> > -         st = find_symbol (gfc_current_ns->sym_root,
> > -                           name, module_name, 1);
> > -
> > 
> >            if (!p || gfc_find_symbol (p, NULL, 0, &sym))
> >            
> >              {
> >              
> >                /* Skip the specific names for these cases.  */
> > 
> > @@ -4570,6 +4567,9 @@ load_generic_interfaces (void)
> > 
> >                continue;
> >              
> >              }
> > 
> > +         st = find_symbol (gfc_current_ns->sym_root,
> > +                           name, module_name, 1);
> > +
> > 
> >            /* If the symbol exists already and is being USEd without being
> >            
> >               in an ONLY clause, do not load a new symtree(11.3.2).  */
> >            
> >            if (!only_flag && st)
> > 
> > This just delays the call to find_symbol() until after the first test of
> > whether the symbol needs to be loaded  - if that test fails then
> > find_symbol() is never called.
> > 
> > This has no significant effect on compile time for files which import
> > small
> > numbers of symbols. But for cases where the number is large I find that
> > the
> > compile time can be reduced by up to 40% in the cases I've tried.
> > 
> > The change passes all regression tests cleanly.
> 
> The patch is OK for trunk.
> 
> Thanks!
> 
> Regards
> 
> 	Thomas


-- 

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

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

Re: Optimization in load_generic_interfaces()

[Andrew Benson]

Committed as r263784.

Thanks,
Andrew

On Wednesday, August 22, 2018 5:43:30 PM PDT Thomas Koenig wrote:
> Hi Andrew,
> 
> [please also copy in gcc-patches for patches]
> 
> > I'm continuing to look for optimizations to improve compile times for
> > files
> > which USE large numbers of modules containing large numbers of symbols.
> > 
> > When the number of symbols becomes very large, find_symbol() becomes a
> > slow- point, because it can't use the structure of the balanced binary
> > tree to rapidly search the symtree, so just has to go through the whole
> > tree until it finds (or doesn't find) the symbol.
> > 
> > I don't see a simple way to improve the speed of this function, but there
> > seems to be a simple change in load_generic_interfaces() which gives
> > significant speed up:
> > 
> > Index: gcc/fortran/module.c
> > ===================================================================
> > --- gcc/fortran/module.c        (revision 263667)
> > +++ gcc/fortran/module.c        (working copy)
> > @@ -4559,9 +4559,6 @@ load_generic_interfaces (void)
> > 
> >            /* Decide if we need to load this one or not.  */
> >            p = find_use_name_n (name, &i, false);
> > 
> > -         st = find_symbol (gfc_current_ns->sym_root,
> > -                           name, module_name, 1);
> > -
> > 
> >            if (!p || gfc_find_symbol (p, NULL, 0, &sym))
> >            
> >              {
> >              
> >                /* Skip the specific names for these cases.  */
> > 
> > @@ -4570,6 +4567,9 @@ load_generic_interfaces (void)
> > 
> >                continue;
> >              
> >              }
> > 
> > +         st = find_symbol (gfc_current_ns->sym_root,
> > +                           name, module_name, 1);
> > +
> > 
> >            /* If the symbol exists already and is being USEd without being
> >            
> >               in an ONLY clause, do not load a new symtree(11.3.2).  */
> >            
> >            if (!only_flag && st)
> > 
> > This just delays the call to find_symbol() until after the first test of
> > whether the symbol needs to be loaded  - if that test fails then
> > find_symbol() is never called.
> > 
> > This has no significant effect on compile time for files which import
> > small
> > numbers of symbols. But for cases where the number is large I find that
> > the
> > compile time can be reduced by up to 40% in the cases I've tried.
> > 
> > The change passes all regression tests cleanly.
> 
> The patch is OK for trunk.
> 
> Thanks!
> 
> Regards
> 
> 	Thomas


-- 

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

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