* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
@ 2020-07-15 6:29 ` rguenth at gcc dot gnu.org
2020-07-15 8:47 ` hyena at hyena dot net.ee
` (10 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2020-07-15 6:29 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
2020-07-15 6:29 ` [Bug c++/96197] " rguenth at gcc dot gnu.org
@ 2020-07-15 8:47 ` hyena at hyena dot net.ee
2020-07-15 9:10 ` rguenther at suse dot de
` (9 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: hyena at hyena dot net.ee @ 2020-07-15 8:47 UTC (permalink / raw)
To: gcc-bugs
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));
}
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
2020-07-15 6:29 ` [Bug c++/96197] " rguenth at gcc dot gnu.org
2020-07-15 8:47 ` hyena at hyena dot net.ee
@ 2020-07-15 9:10 ` rguenther at suse dot de
2020-07-15 9:42 ` hyena at hyena dot net.ee
` (8 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenther at suse dot de @ 2020-07-15 9:10 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (2 preceding siblings ...)
2020-07-15 9:10 ` rguenther at suse dot de
@ 2020-07-15 9:42 ` hyena at hyena dot net.ee
2020-07-21 16:17 ` ppalka at gcc dot gnu.org
` (7 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: hyena at hyena dot net.ee @ 2020-07-15 9:42 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (3 preceding siblings ...)
2020-07-15 9:42 ` hyena at hyena dot net.ee
@ 2020-07-21 16:17 ` ppalka at gcc dot gnu.org
2020-07-21 19:49 ` tridacnid at gmail dot com
` (6 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: ppalka at gcc dot gnu.org @ 2020-07-21 16:17 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (4 preceding siblings ...)
2020-07-21 16:17 ` ppalka at gcc dot gnu.org
@ 2020-07-21 19:49 ` tridacnid at gmail dot com
2020-07-31 2:29 ` cvs-commit at gcc dot gnu.org
` (5 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: tridacnid at gmail dot com @ 2020-07-21 19:49 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (5 preceding siblings ...)
2020-07-21 19:49 ` tridacnid at gmail dot com
@ 2020-07-31 2:29 ` cvs-commit at gcc dot gnu.org
2020-07-31 13:51 ` ppalka at gcc dot gnu.org
` (4 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2020-07-31 2:29 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (6 preceding siblings ...)
2020-07-31 2:29 ` cvs-commit at gcc dot gnu.org
@ 2020-07-31 13:51 ` ppalka at gcc dot gnu.org
2021-01-09 3:52 ` cvs-commit at gcc dot gnu.org
` (3 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: ppalka at gcc dot gnu.org @ 2020-07-31 13:51 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (7 preceding siblings ...)
2020-07-31 13:51 ` ppalka at gcc dot gnu.org
@ 2021-01-09 3:52 ` cvs-commit at gcc dot gnu.org
2021-01-09 3:54 ` ppalka at gcc dot gnu.org
` (2 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-01-09 3:52 UTC (permalink / raw)
To: gcc-bugs
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)
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (8 preceding siblings ...)
2021-01-09 3:52 ` cvs-commit at gcc dot gnu.org
@ 2021-01-09 3:54 ` ppalka at gcc dot gnu.org
2021-01-09 3:58 ` ppalka at gcc dot gnu.org
2021-01-18 15:39 ` ppalka at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: ppalka at gcc dot gnu.org @ 2021-01-09 3:54 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (9 preceding siblings ...)
2021-01-09 3:54 ` ppalka at gcc dot gnu.org
@ 2021-01-09 3:58 ` ppalka at gcc dot gnu.org
2021-01-18 15:39 ` ppalka at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: ppalka at gcc dot gnu.org @ 2021-01-09 3:58 UTC (permalink / raw)
To: gcc-bugs
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. ***
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug c++/96197] Excess memory consumption, positive correlation with the size of a constexpr array
2020-07-14 15:30 [Bug c++/96197] New: Excess memory consumption, positive correlation with the size of a constexpr array hyena at hyena dot net.ee
` (10 preceding siblings ...)
2021-01-09 3:58 ` ppalka at gcc dot gnu.org
@ 2021-01-18 15:39 ` ppalka at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: ppalka at gcc dot gnu.org @ 2021-01-18 15:39 UTC (permalink / raw)
To: gcc-bugs
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. ***
^ permalink raw reply [flat|nested] 13+ messages in thread