[Bug c++/65848] New: [c++-concepts] High memory usage and compilation times for subsuming concept chains; regression from r211824

[Bug c++/65848] New: [c++-concepts] High memory usage and compilation times for subsuming concept chains; regression from r211824

[tom at honermann dot net]

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

            Bug ID: 65848
           Summary: [c++-concepts] High memory usage and compilation times
                    for subsuming concept chains; regression from r211824
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tom at honermann dot net

The following test case demonstrates high CPU and memory utilization during
compilation when compiled with gcc r222238.  I have an old gcc build (r211824)
that compiles this test case quickly with low memory usage.  Details are below
the test case.

The performance issue depends on use of the type trait templates.  Replacing
references to them with 'true' suffices to enable the code to be quickly
compiled (though possibly with still higher resource usage then with an r211824
build, I didn't measure).  Likewise, reducing the length of the CN<T> concept
chain or the number of types for which concepts are asserted has an exponential
effect on resource usage.  Increasing the length of the concept chain much
further results in compilations that will not complete successfully on my
modest hardware (Lenovo T420 laptop with 8GB ram).

I attempted to remove the dependency on the type_traits header, but the number
of entities I would have needed to add to the test case below would have made
the test case much longer.  Simplifying their implementation to keep the test
case small greatly reduced resource usage.  It seems their implementation is
relevant to the issue.

$ cat t.cpp
#include <type_traits>

template<typename T>
concept bool Destructible() {
    return std::is_destructible<T>::value;
}
template<typename T, typename... Args>
concept bool Constructible() {
    return Destructible<T>() && std::is_constructible<T, Args...>::value;
}
template<typename T>
concept bool Move_constructible() {
    return Constructible<T, T&&>();
}
template<typename T>
concept bool Copy_constructible() {
    return Move_constructible<T>() && Constructible<T, const T&>();
}
template<typename T, typename U>
concept bool Assignable() {
    return std::is_assignable<T, U>::value;
}
template<typename T>
concept bool Move_assignable() {
    return Assignable<T&, T&&>();
}
template<typename T>
concept bool Copy_assignable() {
    return Move_assignable<T>() && Assignable<T&, const T&>();
}
template<typename T>
concept bool Copyable() {
    return Copy_constructible<T>() && Copy_assignable<T>();
}

template<typename T>
concept bool C1() { return Copyable<T>(); }
template<typename T>
concept bool C2() { return C1<T>(); }
template<typename T>
concept bool C3() { return C2<T>(); }
template<typename T>
concept bool C4() { return C3<T>(); }
template<typename T>
concept bool C5() { return C4<T>(); }
template<typename T>
concept bool C6() { return C5<T>(); }
template<typename T>
concept bool C7() { return C6<T>(); }
template<typename T>
concept bool C8() { return C7<T>(); }
template<typename T>
concept bool C9() { return C8<T>(); }
template<typename T>
concept bool C10() { return C9<T>(); }
template<typename T>
concept bool C11() { return C10<T>(); }

struct S1 {};
struct S2 {};
struct S3 {};
struct S4 {};
struct S5 {};
struct S6 {};

static_assert(C11<S1>(), "");
static_assert(C11<S2>(), "");
static_assert(C11<S3>(), "");
static_assert(C11<S4>(), "");
static_assert(C11<S5>(), "");
static_assert(C11<S6>(), "");

$ svn info   # From my local svn gcc repo.
Path: .
URL: svn://gcc.gnu.org/svn/gcc/branches/c++-concepts
Repository Root: svn://gcc.gnu.org/svn/gcc
Repository UUID: 138bc75d-0d04-0410-961f-82ee72b054a4
Revision: 222238
Node Kind: directory
Schedule: normal
Last Changed Author: asutton
Last Changed Rev: 222236
Last Changed Date: 2015-04-20 09:43:31 -0400 (Mon, 20 Apr 2015)

Timing details for both the r222238 gcc build above and an old r211824 based
build follow.  The timing data was produced by /usr/bin/time on an Ubuntu 12.04
system.  The data below was produced with a hot cache in each case.

# Using gcc r222238, compilation time and memory usage is significant:
$ /usr/bin/time -v g++ -c -std=c++1z t.cpp
        Command being timed: "g++ -c -std=c++1z t.cpp"
        User time (seconds): 17.73
        System time (seconds): 0.88
        Percent of CPU this job got: 99%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:18.67
        ...
        Maximum resident set size (kbytes): 8409216
        ...
        Minor (reclaiming a frame) page faults: 527712
        ...

# Using an old gcc r211824, compilation completes quickly (note
# that this old build required -std=c++1y to enable support for concepts).
$ /usr/bin/time -v g++ -c -std=c++1y t.cpp
        Command being timed: "g++ -c -std=c++1y t.cpp"
        User time (seconds): 0.05
        System time (seconds): 0.00
        Percent of CPU this job got: 88%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.06
        ...
        Maximum resident set size (kbytes): 63936
        ...
        Minor (reclaiming a frame) page faults: 6107
        ...

[Bug c++/65848] [c++-concepts] High memory usage and compilation times for subsuming concept chains; regression from r211824

[andrew.n.sutton at gmail dot com]

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

--- Comment #1 from Andrew Sutton <andrew.n.sutton at gmail dot com> ---
This is caused by the use of a concept outside of a requires clause -- it's
still a bug though. The TS doesn't actually include wording that would allow
this program to be valid.

Unfortunately, the first thing people do when they have concepts it to write
tests that statically assert them, so I've been extending the proposal to make
that valid.

The performance regression is related to that. When you call C11<S6>(), we
normalize that expression as a constraint and check it. Unfortunately, that
same logic applies for *every single concept check* that appears in an
expression formed while normalizing that constraint. Basically, you're invoking
a giant recursive yo-yo in order to evaluate the constraint.

Like I said... still a bug. I hope to have this resolved in the next half hour.

[Bug c++/65848] [c++-concepts] High memory usage and compilation times for subsuming concept chains; regression from r211824

[andrew.n.sutton at gmail dot com]

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

--- Comment #2 from Andrew Sutton <andrew.n.sutton at gmail dot com> ---
Here's the result of the latest commit (r222332) on my system. test.cpp is the
program in the bug report.

        Command being timed: "~/opt/bin/g++ -std=c++1z -c test.cpp"
        User time (seconds): 0.04
        System time (seconds): 0.01
        Percent of CPU this job got: 91%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.07
        ...
        Maximum resident set size (kbytes): 49344
        ...
        Minor (reclaiming a frame) page faults: 4465

[Bug c++/65848] [c++-concepts] High memory usage and compilation times for subsuming concept chains; regression from r211824

[andrew.n.sutton at gmail dot com]

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

--- Comment #4 from Andrew Sutton <andrew.n.sutton at gmail dot com> ---

> I think that is actually not so unfortunate.  Statically asserting 
> concept models has helped me find numerous issues in my own code.  
> I'm glad to hear the proposal is being extended to cover this.

Unfortunate in the sense that we missed the features that would allow that
usage. But to be fair, it wasn't exactly a primary use case when we were
considering the design.