Bug 67565 - [concepts] Very slow compile time and high memory usage with complex concept definitions, even if unused
Summary: [concepts] Very slow compile time and high memory usage with complex concept ...
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 6.0
: P3 normal
Target Milestone: 6.2
Assignee: Not yet assigned to anyone
URL:
Keywords: compile-time-hog, memory-hog
Depends on:
Blocks: concepts
  Show dependency treegraph
 
Reported: 2015-09-13 15:15 UTC by Adrian Wielgosik
Modified: 2016-07-21 14:27 UTC (History)
7 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2015-09-13 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Adrian Wielgosik 2015-09-13 15:15:43 UTC
Example:

template <class T>
concept bool Constructible() {
	return false ||
		requires (T t) {
			{ t.~T() } noexcept;
		};
}

template <class T>
concept bool Semiregular() {
	return
		Constructible<T>() &&
		Constructible<T>() &&
		Constructible<T>() &&
		Constructible<T>() &&
		Constructible<T>() &&
		Constructible<T>() &&
		Constructible<T>();
}

template <class T, class I>
concept bool Sentinel() {
	return Semiregular<T>() && Semiregular<I>();
}

template<Semiregular I, Sentinel<I> S>
void func(I first, S last) { }

int main(){}


time ./g++trunk -std=c++1z main.cpp

real	0m8.855s
user	0m7.887s
sys	0m0.896s

It also consumed over 2GB of RAM at peak. Note that the function which checks for concepts wasn't even called, so no actual concept checks were done.

Simplifying this case any more, like removing "false ||", fixes the problem.

A big chain of "Constructible<T>() &&" may look strange, but it's just a simplified case - originally I tried to rewrite concepts from Eric Niebler's Ranges proposal, which could check the same concept multiple times.
Comment 1 Markus Trippelsdorf 2015-09-13 15:44:32 UTC
Overhead  Command   Shared Object      Symbol
  19.16%  cc1plus   libc-2.20.so       [.] free
  16.21%  cc1plus   libc-2.20.so       [.] malloc
  14.55%  cc1plus   cc1plus            [.] cp_tree_equal
  13.80%  cc1plus   libc-2.20.so       [.] malloc_consolidate
  10.52%  cc1plus   libc-2.20.so       [.] _int_malloc
   5.34%  cc1plus   cc1plus            [.] decompose_assumptions
   3.81%  cc1plus   cc1plus            [.] ggc_set_mark
   3.56%  cc1plus   cc1plus            [.] (anonymous namespace)::term_list::insert
   2.93%  cc1plus   cc1plus            [.] dependent_name
Comment 2 Tom Honermann 2016-01-15 04:43:52 UTC
I'm also experiencing this issue and finding it to be rather catastrophic at present.  I'm currently using gcc trunk (r232017).

I distilled the following test case from my project before coming across this bug report.  The test cases shares some properties with the one in comment 0; no actual instantiations of the class template (or function for Adrian's test case) are needed to trigger the issue, both conjunctions and disjunctions are present.

This test case includes some conditional compilation options intended to demonstrate that syntactic transformations that should have no semantic affect have dramatic compile time performance impact; search for GO_FAST1 and GO_FAST2.  Additionally, defining the GO_SLOWER1 macro demonstrates a means of scaling the performance impact.

$ cat t.cpp
$ cat t.cpp
template<typename T>
concept bool
C1()
{
  return sizeof(T) > 4;
}

template<typename T>
constexpr bool
f1()
{
  return C1<T>();
}

template<typename T>
constexpr bool
f2()
{
  return f1<T>()
      || f1<T>()
      || f1<T>()
      || f1<T>()
      || f1<T>();
}

template<typename T>
concept bool
C2()
{
#if GO_FAST1
  return f2<T>();
#else
  return f1<T>()
      || f1<T>()
      || f1<T>()
      || f1<T>()
#if GO_SLOWER1
      || f1<T>()
#endif
      || f1<T>();
#endif
}

template<typename T>
concept bool C3() {
    return C2<T>()
        && (C1<T>()
            || C1<T>()
            || C1<T>());
}

template<typename T>
concept bool C4() {
    return C3<typename T::type1>()
        && C3<typename T::type2>();
}

template<typename T>
concept bool C5() {
    return C4<T>();
}

template<typename T>
concept bool C6() {
    return C5<T>()
        && true;
}

#if GO_FAST2
template<typename C>
requires C4<C>()
      && C5<C>()
      && C6<C>()
#else
template<C4 C>
requires C5<C>()
      && C6<C>()
#endif
struct S {
};


$ time g++ -c -std=c++1z t.cpp
real    0m9.485s
user    0m8.672s
sys     0m0.820s

$ time g++ -c -std=c++1z t.cpp -DGO_FAST1
real    0m0.027s
user    0m0.008s
sys     0m0.008s

$ time g++ -c -std=c++1z t.cpp -DGO_FAST2
real    0m0.064s
user    0m0.056s
sys     0m0.000s

$ time g++ -c -std=c++1z t.cpp -DGO_SLOWER1
real    0m30.464s
user    0m26.100s
sys     0m2.832s

The GO_SLOWER1 test peaks at about 10G of virtual memory for me.
Comment 3 Jason Merrill 2016-07-21 06:05:58 UTC
Author: jason
Date: Thu Jul 21 06:05:24 2016
New Revision: 238558

URL: https://gcc.gnu.org/viewcvs?rev=238558&root=gcc&view=rev
Log:
	Improving concepts performance and diagnostics.

	PR c++/67565
	PR c++/67579
	PR c++/71843
gcc/
	* timevar.def (TV_CONSTRAINT_SAT, TV_CONSTRAINT_SUB): New time vars
	for constraint satisfaction and subsumption.
	* timevar.h (auto_timevar): New constructor that matches the push/pop
	pattern of usage in pt.c.
gcc/cp/
	* cp-tree.def (CHECK_CONSTR): New.
	* cp-tree.h (CHECK_CONSTR_CONCEPT): New.
	(CHECK_CONSTR_ARGS): New.
	* constraint.cc (make_predicate_constraint): Remove in favor of
	normalize_expression.
	(resolve_constraint_check): Actually return error_mark_node when
	resolution fails.
	(resolve_variable_concept_check): Perform coercion as if processing
	a template. Also return errors on resolution failure.
	(lift_*): Remove all of these functions. Don't unnecessarily inline
	concepts.
	(learn_*): Add facilities to memoize implications for subsumption
	during normalization.
	(expanding_concept): New.
	(expand_concept): New. Return the inlined and normalized definition
	of a concept when needed.
	(transform_*, xform_*): Rename to normalize_* to better reflect the
	responsibility of those functions.
	(normalize_template_id_expression): Check for non-boolean operands
	when possible. Generate check constraints instead of normal variable
	references.
	(normalize_call_expression): Report errors when resolution fails.
	(check_for_logical_overloads): Rewrite this check to more accurately
	report the error.
	(normalize_atom): Check for overloaded calls and invalid types before
	determining if the expression refers to a concept.
	(build_constraints): Don't cache normalized constraints or decmposed
	assumptions.
	(finish_shorthand_constraint): Return a normalized expression instead
	of a predicate constraint.
	(finish_template_introduction): Same.
	(placeholder_extract_concept_and_args): Rewrite this since we only
	ever get check constraints here.
	(equivalent_placeholder_constraints): Rewrite in terms of check
	constraints, and handle error_mark_nodes correctly.
	(tsubst_check_constraint, tsubst_expr_constr, tsubst_type_constr)
	(tsubst_implicit_conversion_constr)
	(tsubst_argument_deduction_constr, tsubst_exception_constr)
	(tsubst_parameterized_constraint, tsubst_constraint): New.
	(tsbust_conjunection): Replace with tsubst_logical_operator and
	actually generate the right kind of constraint.
	(tsubst_requirement_body): Reverse the order of substituted arguments
	so that they appear in the order written (helps diagnostics).
	(satisfy_check_constraint): New.
	(satisfy_conjunction): Simplify.
	(satisfy_disjunction): Same.
	(satisfy_constraint_1): Handle check constraints.
	(eval_constr): New (private) global state.
	(evaluating_constraints_sentinel): New. Manages eval_constr.
	(satisfy_constraint): Add timing variables.
	(satisfy_associated_constraints): Add hooks for memoization.
	(evaluate_function_concept): Build a check constraint instead of
	normalizing its definition.
	(evaluate_variable_concept): Same.
	(evaluate_constraint_expression): Normalize, but in the current
	declaration processing context.
	(evaluating_constraints_p): New.
	(elide_constraint_failure_p): Actually emit constraint_thresh errors.
	(diagnose_*): Remove artificial indentation. Add a new parameter to
	each that tracks the current (complete) constraint prior to any
	substitutions.
	(diagnose_expression): Removed.
	(diagnose_call_expression): Same.
	(diagnose_template_id): Same.
	(diagnose_template_id): New.
	(diagnose_logical_constraint): New.
	(diagnose_expression_constraint): Show the original expression.
	(diagnose_type_constraint): Show the original type.
	(diagnose_implicit_conversion_constraint): Be specific about
	failures, don't re-diagnose a known-to-be-failed substitutions,
	and manage elisions properly.
	(diagnose_argument_deduction_constraint): Same.
	(diagnose_exception_constraint): Same.
	(diagnose_parameterized_constraint): Same.
	(constraint_p): Allow EXPR_PACK_EXPANSION.
	* logic.cc (next_by_distance): Removed. No longer used.
	(any_p): Renamed from any_of.
	(term_entry, term_hasher): New.
	(term_list): Rewrite to include a hash table for quick lookup.
	Also, make less stateful.
	(proof_state): Extend to allow goals to be discharged once
	satisfied.
	(non_atomic_constraint_p): New.
	(any_non_atomic_constraints_p): New.
	(...rest...): Previous implementation completely replaced with an
	iterative algorithm that opportunistically prunes the search space
	before committing to using more memory.
	* parser.c: (cp_parser_type_parameter): Normalize constraints.
	(cp_parser_explicit_template_declaration): Same.
	* pt.c: (finish_template_variable): Be less redundant with this error
	message.
	(template_args_equal): No longer static.
	(tsubst_decl): Don't try to find specializations of variables that
	have already been instantiated.
	(build_non_dependent_expr): Avoid infinite recursion during concept
	expansion.
	(make_constrained_auto): Normalize constraints.
	(do_auto_deduction): When doing auto deduction from a
	partial-concept-id, be sure to include the explicit args checking
	the constraints.
	(constraint_sat_*): New. Memoize satisfied constraints.
	(concept_spec_*): New. Memoize expressions associated with a concept
	specialization.
	(constraint_memos, concept_memos): New.
	(lookup_constraint_satisfaction, memoize_constraint_satisfaction): New.
	(lookup_concept_satisfaction, memoize_concept_satisfaction): New.
	(get_concept_expansion, save_concept_expansion): New.
	(hash_subsumption_args): New.
	(comp_subsumption_args): New.
	(subsumption_*): New. Memoize parts of the subsumption relation.
	(lookup_subsumption_result, save_subsumption_result): New.
	(init_constraint_processing): Initialize memo tables.
	(get_constraints): Shortcut if !flag_concepts.
	* decl.c (grokfndecl): Normalize constraints.
	* error.c (dump_simple_decl): Print "concept" when appropriate.
	(dump_function_decl): Same.
	(dump_template_decl): Don't write requirements when we're not
	printing the header.
	(dump_expr): Handle fold expressions.
	* cxx-pretty-print.c (cxx_pretty_printer::expression): Handle
	fold expressions.
	(get_fold_operator): New.
	(pp_cxx_unary_left_fold_expression): New.
	(pp_cxx_unary_right_fold_expression): New.
	(pp_cxx_binary_fold_expression): New.
	(pp_cxx_check_constraint): New.
	(pp_cxx_*_constraint): Rewrite the grammar of internal constraints
	to make them easier to read when debugging.
	* search.c (accessible_p): Don't shortcut when evaluating constraints.
	* tree.c (cp_tree_equal): Handle CHECK_CONSTR.

Added:
    trunk/gcc/testsuite/g++.dg/concepts/req19.C
    trunk/gcc/testsuite/g++.dg/concepts/req20.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cp/ChangeLog
    trunk/gcc/cp/constraint.cc
    trunk/gcc/cp/cp-tree.def
    trunk/gcc/cp/cp-tree.h
    trunk/gcc/cp/cxx-pretty-print.c
    trunk/gcc/cp/decl.c
    trunk/gcc/cp/error.c
    trunk/gcc/cp/logic.cc
    trunk/gcc/cp/parser.c
    trunk/gcc/cp/pt.c
    trunk/gcc/cp/ptree.c
    trunk/gcc/cp/search.c
    trunk/gcc/cp/tree.c
    trunk/gcc/testsuite/g++.dg/concepts/diagnostic1.C
    trunk/gcc/testsuite/g++.dg/concepts/dr1430.C
    trunk/gcc/testsuite/g++.dg/concepts/expression2.C
    trunk/gcc/testsuite/g++.dg/concepts/req4.C
    trunk/gcc/testsuite/g++.dg/concepts/req5.C
    trunk/gcc/testsuite/g++.dg/concepts/req6.C
    trunk/gcc/testsuite/g++.dg/concepts/var-templ1.C
    trunk/gcc/testsuite/g++.dg/concepts/variadic2.C
    trunk/gcc/timevar.def
    trunk/gcc/timevar.h
Comment 4 Jason Merrill 2016-07-21 06:18:39 UTC
Author: jason
Date: Thu Jul 21 06:18:06 2016
New Revision: 238577

URL: https://gcc.gnu.org/viewcvs?rev=238577&root=gcc&view=rev
Log:
	Improving concepts performance and diagnostics.

	PR c++/67565
	PR c++/67579
	PR c++/71843
gcc/
	* timevar.def (TV_CONSTRAINT_SAT, TV_CONSTRAINT_SUB): New time vars
	for constraint satisfaction and subsumption.
	* timevar.h (auto_timevar): New constructor that matches the push/pop
	pattern of usage in pt.c.
gcc/cp/
	* cp-tree.def (CHECK_CONSTR): New.
	* cp-tree.h (CHECK_CONSTR_CONCEPT): New.
	(CHECK_CONSTR_ARGS): New.
	* constraint.cc (make_predicate_constraint): Remove in favor of
	normalize_expression.
	(resolve_constraint_check): Actually return error_mark_node when
	resolution fails.
	(resolve_variable_concept_check): Perform coercion as if processing
	a template. Also return errors on resolution failure.
	(lift_*): Remove all of these functions. Don't unnecessarily inline
	concepts.
	(learn_*): Add facilities to memoize implications for subsumption
	during normalization.
	(expanding_concept): New.
	(expand_concept): New. Return the inlined and normalized definition
	of a concept when needed.
	(transform_*, xform_*): Rename to normalize_* to better reflect the
	responsibility of those functions.
	(normalize_template_id_expression): Check for non-boolean operands
	when possible. Generate check constraints instead of normal variable
	references.
	(normalize_call_expression): Report errors when resolution fails.
	(check_for_logical_overloads): Rewrite this check to more accurately
	report the error.
	(normalize_atom): Check for overloaded calls and invalid types before
	determining if the expression refers to a concept.
	(build_constraints): Don't cache normalized constraints or decmposed
	assumptions.
	(finish_shorthand_constraint): Return a normalized expression instead
	of a predicate constraint.
	(finish_template_introduction): Same.
	(placeholder_extract_concept_and_args): Rewrite this since we only
	ever get check constraints here.
	(equivalent_placeholder_constraints): Rewrite in terms of check
	constraints, and handle error_mark_nodes correctly.
	(tsubst_check_constraint, tsubst_expr_constr, tsubst_type_constr)
	(tsubst_implicit_conversion_constr)
	(tsubst_argument_deduction_constr, tsubst_exception_constr)
	(tsubst_parameterized_constraint, tsubst_constraint): New.
	(tsbust_conjunection): Replace with tsubst_logical_operator and
	actually generate the right kind of constraint.
	(tsubst_requirement_body): Reverse the order of substituted arguments
	so that they appear in the order written (helps diagnostics).
	(satisfy_check_constraint): New.
	(satisfy_conjunction): Simplify.
	(satisfy_disjunction): Same.
	(satisfy_constraint_1): Handle check constraints.
	(eval_constr): New (private) global state.
	(evaluating_constraints_sentinel): New. Manages eval_constr.
	(satisfy_constraint): Add timing variables.
	(satisfy_associated_constraints): Add hooks for memoization.
	(evaluate_function_concept): Build a check constraint instead of
	normalizing its definition.
	(evaluate_variable_concept): Same.
	(evaluate_constraint_expression): Normalize, but in the current
	declaration processing context.
	(evaluating_constraints_p): New.
	(elide_constraint_failure_p): Actually emit constraint_thresh errors.
	(diagnose_*): Remove artificial indentation. Add a new parameter to
	each that tracks the current (complete) constraint prior to any
	substitutions.
	(diagnose_expression): Removed.
	(diagnose_call_expression): Same.
	(diagnose_template_id): Same.
	(diagnose_template_id): New.
	(diagnose_logical_constraint): New.
	(diagnose_expression_constraint): Show the original expression.
	(diagnose_type_constraint): Show the original type.
	(diagnose_implicit_conversion_constraint): Be specific about
	failures, don't re-diagnose a known-to-be-failed substitutions,
	and manage elisions properly.
	(diagnose_argument_deduction_constraint): Same.
	(diagnose_exception_constraint): Same.
	(diagnose_parameterized_constraint): Same.
	(constraint_p): Allow EXPR_PACK_EXPANSION.
	* logic.cc (next_by_distance): Removed. No longer used.
	(any_p): Renamed from any_of.
	(term_entry, term_hasher): New.
	(term_list): Rewrite to include a hash table for quick lookup.
	Also, make less stateful.
	(proof_state): Extend to allow goals to be discharged once
	satisfied.
	(non_atomic_constraint_p): New.
	(any_non_atomic_constraints_p): New.
	(...rest...): Previous implementation completely replaced with an
	iterative algorithm that opportunistically prunes the search space
	before committing to using more memory.
	* parser.c: (cp_parser_type_parameter): Normalize constraints.
	(cp_parser_explicit_template_declaration): Same.
	* pt.c: (finish_template_variable): Be less redundant with this error
	message.
	(template_args_equal): No longer static.
	(tsubst_decl): Don't try to find specializations of variables that
	have already been instantiated.
	(build_non_dependent_expr): Avoid infinite recursion during concept
	expansion.
	(make_constrained_auto): Normalize constraints.
	(do_auto_deduction): When doing auto deduction from a
	partial-concept-id, be sure to include the explicit args checking
	the constraints.
	(constraint_sat_*): New. Memoize satisfied constraints.
	(concept_spec_*): New. Memoize expressions associated with a concept
	specialization.
	(constraint_memos, concept_memos): New.
	(lookup_constraint_satisfaction, memoize_constraint_satisfaction): New.
	(lookup_concept_satisfaction, memoize_concept_satisfaction): New.
	(get_concept_expansion, save_concept_expansion): New.
	(hash_subsumption_args): New.
	(comp_subsumption_args): New.
	(subsumption_*): New. Memoize parts of the subsumption relation.
	(lookup_subsumption_result, save_subsumption_result): New.
	(init_constraint_processing): Initialize memo tables.
	(get_constraints): Shortcut if !flag_concepts.
	* decl.c (grokfndecl): Normalize constraints.
	* error.c (dump_simple_decl): Print "concept" when appropriate.
	(dump_function_decl): Same.
	(dump_template_decl): Don't write requirements when we're not
	printing the header.
	(dump_expr): Handle fold expressions.
	* cxx-pretty-print.c (cxx_pretty_printer::expression): Handle
	fold expressions.
	(get_fold_operator): New.
	(pp_cxx_unary_left_fold_expression): New.
	(pp_cxx_unary_right_fold_expression): New.
	(pp_cxx_binary_fold_expression): New.
	(pp_cxx_check_constraint): New.
	(pp_cxx_*_constraint): Rewrite the grammar of internal constraints
	to make them easier to read when debugging.
	* search.c (accessible_p): Don't shortcut when evaluating constraints.
	* tree.c (cp_tree_equal): Handle CHECK_CONSTR.

Added:
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req19.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req20.C
Modified:
    branches/gcc-6-branch/gcc/ChangeLog
    branches/gcc-6-branch/gcc/cp/ChangeLog
    branches/gcc-6-branch/gcc/cp/constraint.cc
    branches/gcc-6-branch/gcc/cp/cp-tree.def
    branches/gcc-6-branch/gcc/cp/cp-tree.h
    branches/gcc-6-branch/gcc/cp/cxx-pretty-print.c
    branches/gcc-6-branch/gcc/cp/decl.c
    branches/gcc-6-branch/gcc/cp/error.c
    branches/gcc-6-branch/gcc/cp/logic.cc
    branches/gcc-6-branch/gcc/cp/parser.c
    branches/gcc-6-branch/gcc/cp/pt.c
    branches/gcc-6-branch/gcc/cp/ptree.c
    branches/gcc-6-branch/gcc/cp/search.c
    branches/gcc-6-branch/gcc/cp/tree.c
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/diagnostic1.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/dr1430.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/expression2.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req4.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req5.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req6.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/var-templ1.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/variadic2.C
    branches/gcc-6-branch/gcc/timevar.def
    branches/gcc-6-branch/gcc/timevar.h
Comment 5 Tom Honermann 2016-07-21 13:49:48 UTC
Nice, thanks!

Using gcc r238587, I get the times below for the examples in this report.  All cases are dramatically improved.  Unless there is some other known issue not captured in the discussion here, it looks to me like this issue can be resolved.

For the example in comment 0:

$ time g++ -std=c++1z -fconcepts main.cpp
real    0m0.051s
user    0m0.040s
sys     0m0.008s

For the example in comment 2:

$ time g++ -c -std=c++1z -fconcepts t.cpp
real    0m0.009s
user    0m0.004s
sys     0m0.000s

$ time g++ -c -std=c++1z -fconcepts t.cpp -DGO_FAST1
real    0m0.009s
user    0m0.004s
sys     0m0.000s

$ time g++ -c -std=c++1z -fconcepts t.cpp -DGO_FAST2
real    0m0.009s
user    0m0.000s
sys     0m0.004s

$ time g++ -c -std=c++1z -fconcepts t.cpp -DGO_SLOWER1
real    0m0.009s
user    0m0.000s
sys     0m0.004s

Additionally, my builds of Text View [1] now complete in 0m26.140s improved from 1m35.837s.

[1]: https://github.com/tahonermann/text_view
Comment 6 Jason Merrill 2016-07-21 14:27:23 UTC
Fixed for 6.2.