[Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array

[Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array

[hyena at hyena dot net.ee]

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

            Bug ID: 96197
           Summary: Excess memory consumption, positive correlation with
                    the size of a constexpr array
           Product: gcc
           Version: 9.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hyena at hyena dot net.ee
  Target Milestone: ---

Created attachment 48876
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=48876&action=edit
Contains the problematic constant expression array.

The memory consumption of the compiler seems to have an exponential dependency
on one of the constant expression arrays that I have set up in the header. I
have attached the header file. With an array of just 500 elements the memory
consumption of GCC goes above 5 GiB.

I have tested even with the latest 10.x version and the problem is still there.
Tested also with -O1, -O2 and -O3 and none of these made any difference.

If anyone is aware of any workarounds then I would much appreciate learning
more about them because I need to keep developing the project I have at hand
but because of this bug it has become impossible to continue without changing
the architecture a lot.

This only becomes noticeable at larger array sizes (several hundred elements in
my case).

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-07-15
      Known to fail|                            |10.1.0, 11.0
           Keywords|                            |memory-hog

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Does it help if you replace your simplistic O(n) algorithms with O(log n) ones?
That is, 

constexpr const struct word_type &WORD_LOOKUP(WORD index, const struct
word_type *table_row =word_table) {
    for (;;) {
        if (table_row->index == index) return *table_row;

        if (table_row->index == WORD::NONE) return word_lookup(WORD::NONE);

        ++table_row;
    }

//    return table_row->index == index ? *table_row : (table_row->index ==
WORD::NONE ? word_lookup(WORD::NONE) : WORD_LOOKUP(index, ++table_row));
}

replace the for (;;) loop with table_row[index] (OK, that's maybe too much
guessing into your data structure) or with a binary search over the table
which you keep sorted?

It's probably simply garbage that accumulates during constexpr evaluation.
-ftime-report shows

 constant expression evaluation     :  28.45 ( 92%)   1.57 ( 96%)  32.97 ( 92%)
5127882 kB (100%)

that is 5GB of GC memory from constexpr evaluation.

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[hyena at hyena dot net.ee]

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

--- Comment #2 from Erich Erstu <hyena at hyena dot net.ee> ---
Richard Biener, you were right. I optimized the implementation of all the
problematic constant expression functions similarly to the one seen below, and
the compilation time went down to practically zero with unnoticeable memory
consumption. This is simple enough workaround that I can actually put into use
for real.

// I added this proxy struct for faster lookups:
constexpr const struct NOUN_INDEX_TYPE {
    constexpr NOUN_INDEX_TYPE() : indices() {
        for (const noun_type &noun : noun_table) {
            indices[static_cast<size_t>(noun.index)] = &noun;
        }
    }
    const noun_type *indices[1024];
} NOUN_INDEX_TABLE;

constexpr const struct noun_type &NOUN(WORD index, const struct noun_type
*table_row =noun_table) {
    return *NOUN_INDEX_TABLE.indices[static_cast<size_t>(index)];
    /*
    for (;;) {
        if (table_row->index == index) return *table_row;

        if (table_row->index == WORD::NONE) return noun_lookup(WORD::NONE);

        ++table_row;
    }
    */

    //return table_row->index == index ? *table_row : (table_row->index ==
WORD::NONE ? noun_lookup(WORD::NONE) : NOUN(index, ++table_row));
}

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[rguenther at suse dot de]

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

--- Comment #3 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 15 Jul 2020, hyena at hyena dot net.ee wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96197
> 
> --- Comment #2 from Erich Erstu <hyena at hyena dot net.ee> ---
> Richard Biener, you were right. I optimized the implementation of all the
> problematic constant expression functions similarly to the one seen below, and
> the compilation time went down to practically zero with unnoticeable memory
> consumption. This is simple enough workaround that I can actually put into use
> for real.

constexpr shouldn't be an excuse for using slow algorithms - the compiler
after all doesn't have magic ability just because you write 'constexpr' ;)
In fact it's a lot slower in practice (and as you can see memory hungry
though that's arguably a bug) - I guess at some point C++ compilers will
have JITs just to make constexpr compile-times bearable because people
are getting lazy with their algorithms... :/

I'm leaving the bug open for the memory consumption issue.

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[hyena at hyena dot net.ee]

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

--- Comment #4 from Erich Erstu <hyena at hyena dot net.ee> ---
Intuitive logic says that even for a slow algorithm it should not be THAT slow
and memory heavy. And for a constant expression, the slowness of an algorithm
should not be that much of a concern in the first place, because if the
compiler was optimal it would only run that "slow algorithm" once per
compilation. Also, it is not intuitive to assume that a slow algorithm would
cause high memory consumption. In fact, typically you get speed at the cost of
memory.

Bottom line is, it is not a matter of people being lazy, it's a matter of
people making fair assumptions of what the compiler should reasonably be
capable of doing. And in this case, the assumptions were wrong.

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |ppalka at gcc dot gnu.org
             Status|NEW                         |ASSIGNED
                 CC|                            |ppalka at gcc dot gnu.org

--- Comment #5 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Looking into it.

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[tridacnid at gmail dot com]

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

Joe Burzinski <tridacnid at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tridacnid at gmail dot com

--- Comment #6 from Joe Burzinski <tridacnid at gmail dot com> ---
gcc 8.3.1

I just ran into almost this exact scenario. We use constexpr for catching
inconsistencies at compile time and a recent conversion of 50ish arrays of 100
elements takes an unknown amount of time to compile (I killed the build as I
ate into my last GB of swap) and used ~46GB of RAM + ~16GB of swap. I'm unable
to test on a later version of gcc but plugging the test case into godbolt
compiles on clang but runs out of memory when using gcc 10.1 and trunk.

I was able to trim the case down to get it to a compile time of 33s using ~24GB
of memory. The same trimmed down case compiles in less than a second and a
couple hundred MB of memory with clang10 for comparison.

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:8c00059ce058ea2aec2933319e270f5443b8b909

commit r11-2445-g8c00059ce058ea2aec2933319e270f5443b8b909
Author: Patrick Palka <ppalka@redhat.com>
Date:   Thu Jul 30 22:21:41 2020 -0400

    c++: decl_constant_value and unsharing [PR96197]

    In the testcase from the PR we're seeing excessive memory use (> 5GB)
    during constexpr evaluation, almost all of which is due to the call to
    decl_constant_value in the VAR_DECL/CONST_DECL branch of
    cxx_eval_constant_expression.  We reach here every time we evaluate an
    ARRAY_REF of a constexpr VAR_DECL, and from there decl_constant_value
    makes an unshared copy of the VAR_DECL's initializer.  But unsharing
    here is unnecessary because callers of cxx_eval_constant_expression
    already unshare its result when necessary.

    To fix this excessive unsharing, this patch adds a new defaulted
    parameter unshare_p to decl_really_constant_value and
    decl_constant_value so that callers can control whether to unshare.

    As a simplification, we can also move the call to unshare_expr in
    constant_value_1 outside of the loop, since doing unshare_expr on a
    DECL_P is a no-op.

    Now that we no longer unshare the result of decl_constant_value and
    decl_really_constant_value from cxx_eval_constant_expression, memory use
    during constexpr evaluation for the testcase from the PR falls from ~5GB
    to 15MB according to -ftime-report.

    gcc/cp/ChangeLog:

            PR c++/96197
            * constexpr.c (cxx_eval_constant_expression) <case CONST_DECL>:
            Pass false to decl_constant_value and decl_really_constant_value
            so that they don't unshare their result.
            * cp-tree.h (decl_constant_value): New declaration with an added
            bool parameter.
            (decl_really_constant_value): Add bool parameter defaulting to
            true to existing declaration.
            * init.c (constant_value_1): Add bool parameter which controls
            whether to unshare the initializer before returning.  Call
            unshare_expr at most once.
            (scalar_constant_value): Pass true to constant_value_1's new
            bool parameter.
            (decl_really_constant_value): Add bool parameter and forward it
            to constant_value_1.
            (decl_constant_value): Likewise, but instead define a new
            overload with an added bool parameter.

    gcc/testsuite/ChangeLog:

            PR c++/96197
            * g++.dg/cpp1y/constexpr-array8.C: New test.

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[ppalka at gcc dot gnu.org]

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

--- Comment #8 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed for GCC 11 so far, PR remains open to consider backporting the fix to the
10 branch after a while.

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:afe708223f0bfffe688674659f7a71c5130f01d1

commit r10-9240-gafe708223f0bfffe688674659f7a71c5130f01d1
Author: Patrick Palka <ppalka@redhat.com>
Date:   Thu Jul 30 22:21:41 2020 -0400

    c++: decl_constant_value and unsharing [PR96197]

    In the testcase from the PR we're seeing excessive memory use (> 5GB)
    during constexpr evaluation, almost all of which is due to the call to
    decl_constant_value in the VAR_DECL/CONST_DECL branch of
    cxx_eval_constant_expression.  We reach here every time we evaluate an
    ARRAY_REF of a constexpr VAR_DECL, and from there decl_constant_value
    makes an unshared copy of the VAR_DECL's initializer.  But unsharing
    here is unnecessary because callers of cxx_eval_constant_expression
    already unshare its result when necessary.

    To fix this excessive unsharing, this patch adds a new defaulted
    parameter unshare_p to decl_really_constant_value and
    decl_constant_value so that callers can control whether to unshare.

    As a simplification, we can also move the call to unshare_expr in
    constant_value_1 outside of the loop, since doing unshare_expr on a
    DECL_P is a no-op.

    Now that we no longer unshare the result of decl_constant_value and
    decl_really_constant_value from cxx_eval_constant_expression, memory use
    during constexpr evaluation for the testcase from the PR falls from ~5GB
    to 15MB according to -ftime-report.

    gcc/cp/ChangeLog:

            PR c++/96197
            * constexpr.c (cxx_eval_constant_expression) <case CONST_DECL>:
            Pass false to decl_constant_value and decl_really_constant_value
            so that they don't unshare their result.
            * cp-tree.h (decl_constant_value): New declaration with an added
            bool parameter.
            (decl_really_constant_value): Add bool parameter defaulting to
            true to existing declaration.
            * init.c (constant_value_1): Add bool parameter which controls
            whether to unshare the initializer before returning.  Call
            unshare_expr at most once.
            (scalar_constant_value): Pass true to constant_value_1's new
            bool parameter.
            (decl_really_constant_value): Add bool parameter and forward it
            to constant_value_1.
            (decl_constant_value): Likewise, but instead define a new
            overload with an added bool parameter.

    gcc/testsuite/ChangeLog:

            PR c++/96197
            * g++.dg/cpp1y/constexpr-array8.C: New test.

    (cherry picked from commit 8c00059ce058ea2aec2933319e270f5443b8b909)

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |10.3
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #10 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed for GCC 10.3 and 11

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |adamkzyzik at gmail dot com

--- Comment #11 from Patrick Palka <ppalka at gcc dot gnu.org> ---
*** Bug 98604 has been marked as a duplicate of this bug. ***

[Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gcc-bugs at oxyware dot com

--- Comment #12 from Patrick Palka <ppalka at gcc dot gnu.org> ---
*** Bug 88604 has been marked as a duplicate of this bug. ***