https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127894
Bug ID: 127894
Summary: constexpr evaluation of array scans: time and memory
dominated by evaluator overhead
Product: gcc
Version: 17.0
URL: https://github.com/XRay3D/gcc/tree/constexpr-perf
Status: UNCONFIRMED
Keywords: compile-time-hog, memory-hog
Severity: normal
Priority: P3
Component: c++
Assignee: unassigned at gcc dot gnu.org
Reporter: bakiev at elemer dot ru
Target Milestone: ---
Host: x86_64-pc-linux-gnu
Target: x86_64-pc-linux-gnu
Build: x86_64-pc-linux-gnu
Created attachment 65843
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65843&action=edit
Testcase: constexpr scans of an #embed-ed file, VARIANT 1-4
Scanning a large array during constant evaluation, e.g. #embed-ed data with
indices, std::string_view or pointers, is slow and, more importantly, needs
memory proportional to the number of evaluated operations: the evaluator
builds new trees for most intermediate results, and no garbage is collected
before the outermost evaluation ends. Pointers into arrays are the worst
case: advancing, dereferencing and comparing them go through the folder,
which builds new trees each time.
Testcase: the attached constexpr-scan.cc. Any large text file can serve as
the input; below it is gcc/cp/pt.cc (1.08 MB) from the GCC source tree, so
the test needs no other files:
g++ -std=c++26 -fsyntax-only -ftime-report -DVARIANT=N \
-DINPUT='"gcc/cp/pt.cc"' \
-fconstexpr-loop-limit=100000000 -fconstexpr-ops-limit=4000000000 \
constexpr-scan.cc
| VARIANT | what the testcase does |
|---------|---------------------------------------------------------|
| 1 | index loop over the array |
| 2 | std::string_view::find |
| 3 | pointer loop, for (p = b; p != e; ++p) |
| 4 | tokenizer: identifiers compared against a keyword table |
Trunk: gcc version 17.0.0 20261012 (experimental) (GCC), 0a3124969d7,
bootstrapped (configured with --disable-multilib only), best of 3 runs:
| VARIANT | wall time, s | peak RSS, MB | GC allocated, MB |
|---------|-------------:|-------------:|-----------------:|
| 1 | 1.52 | 193 | 221 |
| 2 | 3.09 | 405 | 472 |
| 3 | 2.58 | 518 | 569 |
| 4 | 18.18 | 3207 | 3954 |
-ftime-report of trunk (one run; time, GC memory allocated):
| VARIANT | constant expression evaluation | garbage collection | TOTAL
|
|---------|--------------------------------|--------------------|----------------|
| 3 | 3.04 s (87%), 505M (89%) | 0.16 s (4%) | 3.51 s, 569M
|
| 4 | 18.90 s (80%), 3889M (98%) | 4.31 s (18%) | 23.51 s,
3954M |
For comparison, clang 21.1 on a similar test (variants 1-3 over a 1.16 MB
#embed-ed file of unsigned char, -fsyntax-only; not this exact testcase).
GCC 16 behaves like trunk.
| VARIANT | clang 21.1 | clang 21.1, bytecode (*) |
|---------|----------------|--------------------------|
| 1 | 0.78 s, 160 MB | 0.37 s, 223 MB |
| 2 | 1.82 s, 167 MB | 0.55 s, 223 MB |
| 3 | 0.87 s, 160 MB | 0.47 s, 223 MB |
(*) -fexperimental-new-constant-interpreter
Where the time goes (callgrind, GCC 16, a constexpr parser of a 1 MB
#embed-ed file):
| cost | effect
|
|---------------------------------------------------------------|------------------|
| INTEGER_CST arithmetic, comparisons via fold_binary_loc (1) | ~11% instr.
|
| array_type_nelts_top folding a PLUS_EXPR per bounds check (2) | ~4% instr.
|
| setup of cxx_eval_constant_expression for constants (3) | ~4% instr.
|
| same_type_ignoring_tlq_and_bounds_p, unqualified variants | ~3% instr.
|
| reduced_constant_expression_p for INTEGER_CSTs (FIXME there) | ~2% instr.
|
| pointer comparisons: MEM_REF + ADDR_EXPR per operand | VARIANT 3
memory |
| *P: an ARRAY_REF per dereference, kept until the end | memory
|
| const T & to *(P + I): POINTER_PLUS_EXPR rebuilt | memory
|
(1) fold_binary_loc -> const_binop -> int_const_binop -> poly_int_binop ->
force_fit_type -> wide_int_to_tree
(2) and is_really_empty_class doing the same
(3) iloc_sentinel, the operation count and the dispatch, paid for operands
that are constants already
Possible fixes
--------------
A series addressing these is on the branch constexpr-perf of a fork:
https://github.com/XRay3D/gcc/tree/constexpr-perf
https://github.com/XRay3D/gcc/compare/0a3124969d7...constexpr-perf
| # | change | commit
|
|---|--------------------------------|-----------------------------------------------|
| 1 | reduced_constant_expression_p |
https://github.com/XRay3D/gcc/commit/0a0f3c84 |
| 2 | array_type_nelts_constant_p |
https://github.com/XRay3D/gcc/commit/9a2929bd |
| 3 | constants returned right away |
https://github.com/XRay3D/gcc/commit/11cfe946 |
| 4 | integer ops without the folder |
https://github.com/XRay3D/gcc/commit/6f5410b1 |
| 5 | cache of type comparisons |
https://github.com/XRay3D/gcc/commit/060e7b53 |
| 6 | pointers compared by offsets |
https://github.com/XRay3D/gcc/commit/a74d8c11 |
| 7 | ARRAY_REF of *P freed |
https://github.com/XRay3D/gcc/commit/260a0796 |
| 8 | references bound with one NOP |
https://github.com/XRay3D/gcc/commit/e90245e8 |
Before and after (both bootstrapped from 0a3124969d7, same options, best of
3 runs; trunk -> with the branch):
| VARIANT | wall time, s | peak RSS, MB | GC allocated, MB |
|---------|-----------------------|---------------------|---------------------|
| 1 | 1.52 -> 1.28 (-16%) | 193 -> 194 (+1%) | 221 -> 221 (0%) |
| 2 | 3.09 -> 2.55 (-17%) | 405 -> 302 (-25%) | 472 -> 431 (-9%) |
| 3 | 2.58 -> 1.45 (-44%) | 518 -> 179 (-65%) | 569 -> 297 (-48%) |
| 4 | 18.18 -> 15.84 (-13%) | 3207 -> 2577 (-20%) | 3954 -> 3535 (-11%) |
-ftime-report, trunk and the branch (one run; time, GC memory allocated):
| VARIANT | compiler | constant expression evaluation | GC time | TOTAL
|
|---------|----------|--------------------------------|---------|----------------|
| 3 | trunk | 3.04 s, 505M | 0.16 s | 3.51 s, 569M
|
| 3 | branch | 1.54 s, 232M | 0.10 s | 1.93 s, 297M
|
| 4 | trunk | 18.90 s, 3889M | 4.31 s | 23.51 s,
3954M |
| 4 | branch | 16.34 s, 3471M | 4.18 s | 20.81 s,
3535M |
Regression testing of the branch on x86_64-pc-linux-gnu, bootstrapped,
make -k check and make -C gcc check-c++-all, against 0a3124969d7:
| testsuite | PASS trunk | PASS branch | FAIL trunk | FAIL branch |
XPASS |
|---------------------|-----------:|------------:|-----------:|------------:|------:|
| gcc | 229627 | 229627 | 77 | 77 |
24 |
| g++ (check-c++-all) | 621922 | 621934 | 19 | 19 |
1 |
| gfortran | 77628 | 77628 | 0 | 0 |
0 |
| objc | 2843 | 2843 | 0 | 0 |
0 |
| libstdc++ | 20897 | 20897 | 0 | 0 |
0 |
| libgomp | 17965 | 17965 | 0 | 0 |
0 |
| libatomic | 54 | 54 | 0 | 0 |
0 |
| libitm | 44 | 44 | 0 | 0 |
0 |
No regressions. The 12 new g++ PASSes are the added test
g++.dg/cpp1y/constexpr-ptr-array1.C; module-cmi results of modules tests
vary between parallel runs and were checked to pass when run alone.
The branch was written with the assistance of an LLM, and each commit carries
an Assisted-by: tag. Given the GCC policy on LLM-generated contributions,
the branch is offered here as an analysis and a reference for what a fix can
gain, not as a patch submission.
