public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug c++/101163] New: slow compilation for huge classes (>20k members) @ 2021-06-22 9:19 rbuergel at web dot de 2021-06-22 9:27 ` [Bug c++/101163] " rbuergel at web dot de ` (5 more replies) 0 siblings, 6 replies; 7+ messages in thread From: rbuergel at web dot de @ 2021-06-22 9:19 UTC (permalink / raw) To: gcc-bugs 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug c++/101163] slow compilation for huge classes (>20k members) 2021-06-22 9:19 [Bug c++/101163] New: slow compilation for huge classes (>20k members) rbuergel at web dot de @ 2021-06-22 9:27 ` rbuergel at web dot de 2021-06-22 10:05 ` rguenth at gcc dot gnu.org ` (4 subsequent siblings) 5 siblings, 0 replies; 7+ messages in thread From: rbuergel at web dot de @ 2021-06-22 9:27 UTC (permalink / raw) To: gcc-bugs 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... ^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug c++/101163] slow compilation for huge classes (>20k members) 2021-06-22 9:19 [Bug c++/101163] New: slow compilation for huge classes (>20k members) rbuergel at web dot de 2021-06-22 9:27 ` [Bug c++/101163] " rbuergel at web dot de @ 2021-06-22 10:05 ` rguenth at gcc dot gnu.org 2021-06-22 10:11 ` jakub at gcc dot gnu.org ` (3 subsequent siblings) 5 siblings, 0 replies; 7+ messages in thread From: rguenth at gcc dot gnu.org @ 2021-06-22 10:05 UTC (permalink / raw) To: gcc-bugs 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 ... ^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug c++/101163] slow compilation for huge classes (>20k members) 2021-06-22 9:19 [Bug c++/101163] New: slow compilation for huge classes (>20k members) rbuergel at web dot de 2021-06-22 9:27 ` [Bug c++/101163] " rbuergel at web dot de 2021-06-22 10:05 ` rguenth at gcc dot gnu.org @ 2021-06-22 10:11 ` jakub at gcc dot gnu.org 2021-06-22 11:07 ` [Bug c++/101163] slow compilation for huge classes (>20k members functions) rguenth at gcc dot gnu.org ` (2 subsequent siblings) 5 siblings, 0 replies; 7+ messages in thread From: jakub at gcc dot gnu.org @ 2021-06-22 10:11 UTC (permalink / raw) To: gcc-bugs 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. ^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug c++/101163] slow compilation for huge classes (>20k members functions) 2021-06-22 9:19 [Bug c++/101163] New: slow compilation for huge classes (>20k members) rbuergel at web dot de ` (2 preceding siblings ...) 2021-06-22 10:11 ` jakub at gcc dot gnu.org @ 2021-06-22 11:07 ` rguenth at gcc dot gnu.org 2021-06-24 10:09 ` rbuergel at web dot de 2021-06-24 11:12 ` jakub at gcc dot gnu.org 5 siblings, 0 replies; 7+ messages in thread From: rguenth at gcc dot gnu.org @ 2021-06-22 11:07 UTC (permalink / raw) To: gcc-bugs 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. ^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug c++/101163] slow compilation for huge classes (>20k members functions) 2021-06-22 9:19 [Bug c++/101163] New: slow compilation for huge classes (>20k members) rbuergel at web dot de ` (3 preceding siblings ...) 2021-06-22 11:07 ` [Bug c++/101163] slow compilation for huge classes (>20k members functions) rguenth at gcc dot gnu.org @ 2021-06-24 10:09 ` rbuergel at web dot de 2021-06-24 11:12 ` jakub at gcc dot gnu.org 5 siblings, 0 replies; 7+ messages in thread From: rbuergel at web dot de @ 2021-06-24 10:09 UTC (permalink / raw) To: gcc-bugs 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... ^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug c++/101163] slow compilation for huge classes (>20k members functions) 2021-06-22 9:19 [Bug c++/101163] New: slow compilation for huge classes (>20k members) rbuergel at web dot de ` (4 preceding siblings ...) 2021-06-24 10:09 ` rbuergel at web dot de @ 2021-06-24 11:12 ` jakub at gcc dot gnu.org 5 siblings, 0 replies; 7+ messages in thread From: jakub at gcc dot gnu.org @ 2021-06-24 11:12 UTC (permalink / raw) To: gcc-bugs 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-06-24 11:12 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-06-22 9:19 [Bug c++/101163] New: slow compilation for huge classes (>20k members) rbuergel at web dot de 2021-06-22 9:27 ` [Bug c++/101163] " rbuergel at web dot de 2021-06-22 10:05 ` rguenth at gcc dot gnu.org 2021-06-22 10:11 ` jakub at gcc dot gnu.org 2021-06-22 11:07 ` [Bug c++/101163] slow compilation for huge classes (>20k members functions) rguenth at gcc dot gnu.org 2021-06-24 10:09 ` rbuergel at web dot de 2021-06-24 11:12 ` jakub at gcc dot gnu.org
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).