[Bug c++/101163] New: slow compilation for huge classes (>20k members)

[Bug c++/101163] New: slow compilation for huge classes (>20k members)

[rbuergel at web dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101163

            Bug ID: 101163
           Summary: slow compilation for huge classes (>20k members)
           Product: gcc
           Version: 6.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rbuergel at web dot de
  Target Milestone: ---

Created attachment 51047
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51047&action=edit
clean example

Hi,

we have a real-world-use-case using a class with ~20k member functions.
Compilation speed decreases awefully when just including that header in another
file: from 2 to 60 seconds.

we're using gcc-6.3 in production, but i tested other versions on
https://godbolt.org/

clang doesn't seem to have that problem, but it seems to be present in newer
gccs, too

[Bug c++/101163] slow compilation for huge classes (>20k members)

[rbuergel at web dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101163

--- Comment #1 from René Bürgel <rbuergel at web dot de> ---
-ftime-report for trunk-gcc says:
Time variable                                   usr           sys          wall
          GGC
 phase setup                        :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
 1562k (  4%)
 phase parsing                      :   4.75 (100%)   0.11 (100%)   5.09 (100%)
   36M ( 96%)
 |name lookup                       :   4.51 ( 95%)   0.05 ( 45%)   4.76 ( 93%)
 2088k (  5%)
 garbage collection                 :   0.01 (  0%)   0.00 (  0%)   0.01 (  0%)
    0  (  0%)
 preprocessing                      :   0.04 (  1%)   0.05 ( 45%)   0.07 (  1%)
 4449k ( 12%)
 parser (global)                    :   0.02 (  0%)   0.00 (  0%)   0.04 (  1%)
 3647k (  9%)
 parser struct body                 :   4.63 ( 97%)   0.05 ( 45%)   4.91 ( 96%)
 9128k ( 24%)
 symout                             :   0.05 (  1%)   0.01 (  9%)   0.06 (  1%)
   19M ( 51%)
 TOTAL                              :   4.75          0.11          5.10       
   37M


It seems to be an issue in the name lookup, if I interpret that right...

[Bug c++/101163] slow compilation for huge classes (>20k members)

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101163

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-06-22
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
           Keywords|                            |compile-time-hog
                 CC|                            |nathan at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed on trunk.  There are linked-lists involved, so not unexpected I
guess.

The top functions in a profile of an unoptimized cc1plus are
fields_linear_search
and member_vec_linear_search called from get_class_binding[_direct] called
ultimatively from lookup_member.

Nathan did a lot of name-lookup refactoring for modules but the core data
structures stayed the same I guess.

In the linear list walk a quite big chunk of the constant overhead is the
anon aggregate check:

static tree
fields_linear_search (tree klass, tree name, bool want_type)
{
  for (tree fields = TYPE_FIELDS (klass); fields; fields = DECL_CHAIN (fields))
    {
      tree decl = fields;

      if (TREE_CODE (decl) == FIELD_DECL
          && ANON_AGGR_TYPE_P (TREE_TYPE (decl)))
        {
          if (tree temp = search_anon_aggr (TREE_TYPE (decl), name, want_type))
            return temp;
        }

      if (DECL_NAME (decl) != name)
        continue;

if there was a bit on the FIELD_DECL instead of the extra indirection that
would help this a lot (by a constant factor).

Of course a linear search should be a no-go ...

[Bug c++/101163] slow compilation for huge classes (>20k members)

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101163

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |jason at gcc dot gnu.org,
                   |                            |mpolacek at gcc dot gnu.org,
                   |                            |ppalka at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
There are binary search tables used for name-lookup later on (once the type is
completed), linear searches are used while the class is constructed.
Perhaps a way out of this would be to have a hybrid lookup during the
construction, use linear searches like now, but once more than certain number
of members is added (a few hundred?), (re)build partial binary search tables
after each such number of new members is added and if not found in the binary
search tables, do the linear search on the rest.

[Bug c++/101163] slow compilation for huge classes (>20k members functions)

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101163

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
OTOH the "binary search tables" are vectors which of course makes them hard to
build incrementally since insert is O(n).  It might be possible to use
a hash-table in the storage place of said vector storage during construction
and then compact that down to the current binary search vector when finalized.

[Bug c++/101163] slow compilation for huge classes (>20k members functions)

[rbuergel at web dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101163

--- Comment #5 from René Bürgel <rbuergel at web dot de> ---
Do I get that right, that this procedure is done for *every* member when adding
it?

So, this would make it basically quadratic...

[Bug c++/101163] slow compilation for huge classes (>20k members functions)

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101163

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Yes, the C++ FE has quadratic behavior here:

#define A(n) int f##n;
#define B(n) A(n##0) A(n##1) A(n##2) A(n##3) A(n##4) A(n##5) A(n##6) A(n##7)
A(n##8) A(n##9)
#define C(n) B(n##0) B(n##1) B(n##2) B(n##3) B(n##4) B(n##5) B(n##6) B(n##7)
B(n##8) B(n##9)
#define D(n) C(n##0) C(n##1) C(n##2) C(n##3) C(n##4) C(n##5) C(n##6) C(n##7)
C(n##8) C(n##9)
#define E(n) D(n##0) D(n##1) D(n##2) D(n##3) D(n##4) D(n##5) D(n##6) D(n##7)
D(n##8) D(n##9)
#define F(n) E(n##0) E(n##1) E(n##2) E(n##3) E(n##4) E(n##5) E(n##6) E(n##7)
E(n##8) E(n##9)
#define G(n) F(n##0) F(n##1) F(n##2) F(n##3) F(n##4) F(n##5) F(n##6) F(n##7)
F(n##8) F(n##9)
struct S {
  E(0) E(1) E(2) E(3) E(4) E(5) E(6)
};

The C FE too, but only in checking builds (
3358    #ifdef ENABLE_TREE_CHECKING
3359      {
3360        tree t2;
3361        for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
3362          gcc_assert (t2 != t1);
3363      }
3364    #endif
in chainon).
  E(0) E(1) E(2) E(3) E(4) E(5) 
time ~/src/gcc/obj88/gcc/cc1 -quiet pr101164.C

real    0m15.515s
user    0m15.430s
sys     0m0.037s
time ~/src/gcc/obj88/gcc/cc1plus -quiet pr101164.C

real    0m25.771s
user    0m25.654s
sys     0m0.036s

  E(0) E(1) E(2) E(3) E(4) E(5) E(6)
time ~/src/gcc/obj88/gcc/cc1 -quiet pr101164.C

real    0m20.994s
user    0m20.875s
sys     0m0.050s
time ~/src/gcc/obj88/gcc/cc1plus -quiet pr101164.C

real    0m35.292s
user    0m35.138s
sys     0m0.035s

In the C++ case it is
#0  fields_linear_search (klass=<record_type 0x7fffea1a3f18 S>,
name=<identifier_node 0x7fffe9649840 f22623>, want_type=true) at
../../gcc/cp/name-lookup.c:1799
#1  0x0000000000c7b400 in get_class_binding_direct (klass=<record_type
0x7fffea1a3f18 S>, name=<identifier_node 0x7fffe9649840 f22623>,
want_type=true)
    at ../../gcc/cp/name-lookup.c:1881
#2  0x0000000000c7b9be in get_class_binding (klass=<record_type 0x7fffea1a3f18
S>, name=<identifier_node 0x7fffe9649840 f22623>, want_type=true) at
../../gcc/cp/name-lookup.c:1950
#3  0x0000000000db109c in lookup_field_r (binfo=<tree_binfo 0x7fffea1a8420>,
data=0x7fffffffcb20) at ../../gcc/cp/search.c:1023
#4  0x0000000000db2324 in dfs_walk_all (binfo=<tree_binfo 0x7fffea1a8420>,
pre_fn=0xdb0f2c <lookup_field_r(tree, void*)>, post_fn=0x0,
data=0x7fffffffcb20)
    at ../../gcc/cp/search.c:1453
#5  0x0000000000db1711 in lookup_member (xbasetype=<tree 0x0>,
name=<identifier_node 0x7fffe9649840 f22623>, protect=2, want_type=true,
complain=3, afi=0x0)
    at ../../gcc/cp/search.c:1166
#6  0x0000000000c8a8be in get_class_binding (name=<identifier_node
0x7fffe9649840 f22623>, scope=0x7fffea04ce10) at
../../gcc/cp/name-lookup.c:5333
#7  0x0000000000c8b158 in push_class_level_binding_1 (name=<identifier_node
0x7fffe9649840 f22623>, x=<field_decl 0x7fffe79a2b48 f22623>) at
../../gcc/cp/name-lookup.c:5439
#8  0x0000000000c8b669 in push_class_level_binding (name=<identifier_node
0x7fffe9649840 f22623>, x=<field_decl 0x7fffe79a2b48 f22623>) at
../../gcc/cp/name-lookup.c:5545
#9  0x0000000000c8a49e in pushdecl_class_level (x=<field_decl 0x7fffe79a2b48
f22623>) at ../../gcc/cp/name-lookup.c:5280
#10 0x0000000000dc3866 in finish_member_declaration (decl=<field_decl
0x7fffe79a2b48 f22623>) at ../../gcc/cp/semantics.c:3521
#11 0x0000000000cd2d68 in cp_parser_member_declaration (parser=0x7fffea06e7b8)
at ../../gcc/cp/parser.c:26627
#12 0x0000000000cd17dc in cp_parser_member_specification_opt
(parser=0x7fffea06e7b8) at ../../gcc/cp/parser.c:25990
#13 0x0000000000ccf414 in cp_parser_class_specifier_1 (parser=0x7fffea06e7b8)
at ../../gcc/cp/parser.c:25061
#14 0x0000000000cd057a in cp_parser_class_specifier (parser=0x7fffea06e7b8) at
../../gcc/cp/parser.c:25377
#15 0x0000000000cc1a1a in cp_parser_type_specifier (parser=0x7fffea06e7b8,
flags=1, decl_specs=0x7fffffffd410, is_declaration=true,
declares_class_or_enum=0x7fffffffd37c, 
    is_cv_qualifier=0x7fffffffd37b) at ../../gcc/cp/parser.c:18609
#16 0x0000000000cbc00e in cp_parser_decl_specifier_seq (parser=0x7fffea06e7b8,
flags=1, decl_specs=0x7fffffffd410, declares_class_or_enum=0x7fffffffd40c)
    at ../../gcc/cp/parser.c:15210
#17 0x0000000000cba6ff in cp_parser_simple_declaration (parser=0x7fffea06e7b8,
function_definition_allowed_p=true, maybe_range_for_decl=0x0) at
../../gcc/cp/parser.c:14466
#18 0x0000000000cba687 in cp_parser_block_declaration (parser=0x7fffea06e7b8,
statement_p=false) at ../../gcc/cp/parser.c:14413
#19 0x0000000000cba353 in cp_parser_declaration (parser=0x7fffea06e7b8,
prefix_attrs=<tree 0x0>) at ../../gcc/cp/parser.c:14284
#20 0x0000000000cba448 in cp_parser_toplevel_declaration
(parser=0x7fffea06e7b8) at ../../gcc/cp/parser.c:14313
#21 0x0000000000ca5568 in cp_parser_translation_unit (parser=0x7fffea06e7b8) at
../../gcc/cp/parser.c:4942