[Bug c/52640] New: performance bottleneck: gcc/tree.c;value_member

[Bug c/52640] New: performance bottleneck: gcc/tree.c;value_member

[ncahill_alt at yahoo dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

             Bug #: 52640
           Summary: performance bottleneck: gcc/tree.c;value_member
    Classification: Unclassified
           Product: gcc
           Version: 4.6.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: ncahill_alt@yahoo.com


Created attachment 26935
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26935
source, output, profiling data indicating problem

It was made known to me that the code provided takes a long time to compile. 
Looking into it, the culprit seems to be the value_member function of
gcc/tree.c.  Here is that code (preprocessed):

####
tree value_member (tree elem, tree list)
{
    while (list) 
    {
        if (elem == ((list)->list.value))
            return list;
        list = ((list)->common.chain);
    }
    return (tree) ((void *)0);
}
####

A sample of profiling data, from OProfile and using gcc 4.6.2:

####
samples  %        image name               symbol name
19955    43.1814  cc1                      value_member
1179      2.5513  cc1                      record_reference
1122      2.4279  cc1                      insert_aux

####

With a table of 10000 rows, it takes ~40% of the execution time, and with
200000 rows, ~90%.  The former takes 5 seconds, the later is not finished in 20
minutes.

Provided is a sample source file with output from cc1 and profiling data as
above.

Thank you.
Neil.

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[jan.smets@alcatel-lucent.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #1 from Jan Smets <jan.smets@alcatel-lucent.com> 2012-03-20 23:45:27 UTC ---
I'd like to note that this code compiles in a few seconds in GCC 3.4.
Thanks Neil for making this profile.

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-03-21
         AssignedTo|unassigned at gcc dot       |steven at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #2 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-21 00:37:18 UTC ---
I'll have a stab at this.

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #4 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-21 13:01:07 UTC ---
Created attachment 26941
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26941
Needs an ASM_OUTPUT_EXTERNAL platform for testing

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |WAITING

--- Comment #3 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-21 13:00:33 UTC ---
Can you please add the output of "gcc --version" and add "-v" to your compiler
invocation and report the output?

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #5 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-21 13:03:57 UTC ---
Ah, and obviously there should be a pointer_set_insert before VEC_safe_push...

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[jan.smets@alcatel-lucent.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #6 from Jan Smets <jan.smets@alcatel-lucent.com> 2012-03-21 15:51:22 UTC ---
Comment on attachment 26941
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26941
Needs an ASM_OUTPUT_EXTERNAL platform for testing

Where does  deferred_global_decls come from? Can this be modified to apply to
4.6.3 ?

Target is i686-wrs-vxworks / mips-wrs-vxworks

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #26941|0                           |1
        is obsolete|                            |

--- Comment #7 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-21 16:17:24 UTC ---
Created attachment 26942
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26942
Fixed patch

Previous patch was obviously not yet tested, this one at least compiles.

[Bug c/52640] performance bottleneck: gcc/tree.c;value_member

[ncahill_alt at yahoo dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #8 from ncahill_alt at yahoo dot com 2012-03-21 17:47:21 UTC ---
Created attachment 26945
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26945
gcc -version && output with -v added

[Bug middle-end/52640] [4.5/4.6/4.7/4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
             Status|WAITING                     |ASSIGNED
          Component|c                           |middle-end
            Summary|performance bottleneck:     |[4.5/4.6/4.7/4.8
                   |gcc/tree.c;value_member     |Regression] performance
                   |                            |bottleneck:
                   |                            |gcc/tree.c;value_member

--- Comment #9 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-21 18:35:10 UTC ---
Regression w.r.t. GCC3 on all active release branches.

[Bug middle-end/52640] [4.5/4.6/4.7/4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[jan.smets@alcatel-lucent.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #10 from Jan Smets <jan.smets@alcatel-lucent.com> 2012-03-21 19:46:31 UTC ---
Works. ~13 sec for 243k entries. Still slower than GCC 3.4 but at least better
than 80+ seconds.

[Bug middle-end/52640] [4.5/4.6/4.7/4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #11 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-24 13:46:42 UTC ---
Author: steven
Date: Sat Mar 24 13:46:33 2012
New Revision: 185757

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=185757
Log:
gcc/
    PR middle-end/52640
    * varasm.c: Include pointer-set.h.
    (pending_assemble_externals_set): New pointer set.
    (process_pending_assemble_externals): Destroy the pointer set.
    (assemble_external): See if decl is in pending_assemble_externals_set,
    and add it to pending_assemble_externals if necessary.
    (init_varasm_once): Allocate pending_assemble_externals_set.

testsuite/
    PR middle-end/52640
    * gcc.c-torture/compile/limits-externdecl.c: New test.

Added:
   
branches/gcc-4_5-branch/gcc/testsuite/gcc.c-torture/compile/limits-externdecl.c
Modified:
    branches/gcc-4_5-branch/gcc/varasm.c

[Bug middle-end/52640] [4.5/4.6/4.7/4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #12 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-24 13:47:51 UTC ---
Author: steven
Date: Sat Mar 24 13:47:46 2012
New Revision: 185758

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=185758
Log:
gcc/
    PR middle-end/52640
    * varasm.c: Include pointer-set.h.
    (pending_assemble_externals_set): New pointer set.
    (process_pending_assemble_externals): Destroy the pointer set.
    (assemble_external): See if decl is in pending_assemble_externals_set,
    and add it to pending_assemble_externals if necessary.
    (init_varasm_once): Allocate pending_assemble_externals_set.

testsuite/
    PR middle-end/52640
    * gcc.c-torture/compile/limits-externdecl.c: New test.

Added:
   
branches/gcc-4_6-branch/gcc/testsuite/gcc.c-torture/compile/limits-externdecl.c
Modified:
    branches/gcc-4_6-branch/gcc/varasm.c

[Bug middle-end/52640] [4.5/4.6/4.7/4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #13 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-24 13:48:51 UTC ---
Author: steven
Date: Sat Mar 24 13:48:35 2012
New Revision: 185759

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=185759
Log:
gcc/
    PR middle-end/52640
    * varasm.c: Include pointer-set.h.
    (pending_assemble_externals_set): New pointer set.
    (process_pending_assemble_externals): Destroy the pointer set.
    (assemble_external): See if decl is in pending_assemble_externals_set,
    and add it to pending_assemble_externals if necessary.
    (init_varasm_once): Allocate pending_assemble_externals_set.

testsuite/
    PR middle-end/52640
    * gcc.c-torture/compile/limits-externdecl.c: New test.

Added:
   
branches/gcc-4_7-branch/gcc/testsuite/gcc.c-torture/compile/limits-externdecl.c
Modified:
    branches/gcc-4_7-branch/gcc/varasm.c

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.5.5, 4.6.4, 4.7.1
   Target Milestone|---                         |4.5.4
            Summary|[4.5/4.6/4.7/4.8            |[4.8 Regression]
                   |Regression] performance     |performance bottleneck:
                   |bottleneck:                 |gcc/tree.c;value_member
                   |gcc/tree.c;value_member     |
      Known to fail|                            |4.8.0

--- Comment #14 from Steven Bosscher <steven at gcc dot gnu.org> 2012-03-24 13:52:21 UTC ---
Fixed on release branches.

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.4                       |4.8.0

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

--- Comment #15 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-07 11:10:57 UTC ---
Any progress on the "real" solution?  If not, can you install the branch fix on
trunk?  Thx.

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[stevenb.gcc at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #16 from stevenb.gcc at gmail dot com <stevenb.gcc at gmail dot com> 2012-09-07 19:07:27 UTC ---
> Any progress on the "real" solution?  If not, can you install the branch fix on
> trunk?  Thx.

I think I already mentioned before that the branch fix is the only
real fix I can think of. The problem has been aggravated by the
visibility machinery, it depends on having a pending-externs list.

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #17 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-11 08:03:44 UTC ---
Any progress on this?  Does the branch patch not work on the trunk?

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #18 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-11 09:59:13 UTC ---
(In reply to comment #17)
> Any progress on this?  Does the branch patch not work on the trunk?

Simply task of forward-porting and testing.

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[jan.smets@alcatel-lucent.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #19 from Jan Smets <jan.smets@alcatel-lucent.com> 2012-12-11 16:55:30 UTC ---
Steven's example only contains 10 000 entries. I need to recompile a symbol
table of 270.000 entries a dozen times each day. (and so do a lot of other
people)
With the 'fix' it still takes 12+ seconds to compile it on a state of the art
machine and then another 4+ seconds to assemble. CLANG2.8 spends 15.5 sec and
CLANG3.1 16.5 sec.

I'm already happy with the work around but I'd really like to see a more
structural solution, whichever that may be.  Thanks

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #20 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-11 17:05:33 UTC ---
Created attachment 28927
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28927
gcc48-pr52640.patch

Patch I'm going to bootstrap/regtest on the trunk.  No point to #include
pointer-set.h when it is already included (it is included twice in 4.7
varams.c), and the var should be IMHO defined only if ASM_OUTPUT_EXTERNAL is
defined, otherwise it is unused local var.

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

--- Comment #21 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-12 09:43:39 UTC ---
Author: jakub
Date: Wed Dec 12 09:43:33 2012
New Revision: 194441

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194441
Log:
    PR middle-end/52640
    * varasm.c (pending_assemble_externals_set): New pointer set.
    (process_pending_assemble_externals): Destroy the pointer set.
    (assemble_external): See if decl is in pending_assemble_externals_set,
    and add it to pending_assemble_externals if necessary.
    (init_varasm_once): Allocate pending_assemble_externals_set.

    * gcc.c-torture/compile/limits-externdecl.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/compile/limits-externdecl.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/varasm.c

[Bug middle-end/52640] [4.8 Regression] performance bottleneck: gcc/tree.c;value_member

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #22 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-12 09:44:42 UTC ---
Fixed.