Optimization in load_generic_interfaces()

[Andrew Benson]

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

[Thomas Koenig]

Hi Andrew,

[please also copy in gcc-patches for patches]

Post by Andrew Benson
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
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]

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

Post by Thomas Koenig
Hi Andrew,
[please also copy in gcc-patches for patches]

Post by Andrew Benson
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
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]

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

Post by Thomas Koenig
Hi Andrew,
[please also copy in gcc-patches for patches]

Post by Andrew Benson
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
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]

Committed as r263784.

Thanks,
Andrew

Post by Thomas Koenig
Hi Andrew,
[please also copy in gcc-patches for patches]

Post by Andrew Benson
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
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