public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases
@ 2021-05-03 11:46 curiousdannii at gmail dot com
2021-05-03 12:04 ` [Bug c/100393] " curiousdannii at gmail dot com
` (11 more replies)
0 siblings, 12 replies; 13+ messages in thread
From: curiousdannii at gmail dot com @ 2021-05-03 11:46 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
Bug ID: 100393
Summary: Very slow compilation of switch statement with
thousands of cases
Product: gcc
Version: 10.2.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c
Assignee: unassigned at gcc dot gnu.org
Reporter: curiousdannii at gmail dot com
Target Milestone: ---
I have a switch statement with almost 11,000 cases (produced by a decompiler),
which is taking almost 5 minutes to compile with GCC 10.2. Helpful people on
Stack Overflow suggested that it was a regression, that it only took 3 seconds
to compile with GCC 8.4, and for comparison, only 1.3 seconds in Clang. I
haven't been able to confirm those results yet, but I'll look into doing so.
SO discussion: https://stackoverflow.com/q/67363813/2854284
Preprocessed source:
https://gist.githubusercontent.com/curiousdannii/9476375ff3ae22c403ce2a8132e6a5dc/raw/568f519f2f1b599e98c514f3609a4968d4153eed/functions_unsafe.i
The `-ftime-report -ftime-report-details` results (full results in the SO page)
show that the slow part is in "tree switch lowering".
I also tried compiling it with `-fno-jump-tables`, which, rather than helping,
made it much worse, taking over 33 minutes to compile.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug c/100393] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
@ 2021-05-03 12:04 ` curiousdannii at gmail dot com
2021-05-03 13:37 ` [Bug tree-optimization/100393] [9/10/11/12 Regression] " rguenth at gcc dot gnu.org
` (10 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: curiousdannii at gmail dot com @ 2021-05-03 12:04 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
--- Comment #1 from Dannii Willis <curiousdannii at gmail dot com> ---
Okay, I've confirmed the regression myself, using functions_unsafe.i:
gcc-8: real 0m11.450s
gcc-10: real 4m46.472s
And for comparison
clang: real 0m0.711s
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
2021-05-03 12:04 ` [Bug c/100393] " curiousdannii at gmail dot com
@ 2021-05-03 13:37 ` rguenth at gcc dot gnu.org
2021-05-03 13:48 ` rguenth at gcc dot gnu.org
` (9 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-05-03 13:37 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Priority|P3 |P2
Last reconfirmed| |2021-05-03
Keywords| |compile-time-hog
Component|c |tree-optimization
Summary|Very slow compilation of |[9/10/11/12 Regression]
|switch statement with |Very slow compilation of
|thousands of cases |switch statement with
| |thousands of cases
Known to work| |8.4.0
Status|UNCONFIRMED |NEW
Ever confirmed|0 |1
Known to fail| |11.1.0, 9.3.1
CC| |marxin at gcc dot gnu.org,
| |rguenth at gcc dot gnu.org
Target Milestone|--- |9.4
--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed at -O0 and -O1+.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
2021-05-03 12:04 ` [Bug c/100393] " curiousdannii at gmail dot com
2021-05-03 13:37 ` [Bug tree-optimization/100393] [9/10/11/12 Regression] " rguenth at gcc dot gnu.org
@ 2021-05-03 13:48 ` rguenth at gcc dot gnu.org
2021-05-03 13:58 ` rguenth at gcc dot gnu.org
` (8 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-05-03 13:48 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Samples: 847K of event 'cycles:u', Event count (approx.): 839745061761
Overhead Samples Command Shared Object Symbol
95.05% 804298 cc1 cc1 [.]
tree_switch_conversion::jump_table_cluster::can_be_handled
1.69% 14493 cc1 cc1 [.]
tree_switch_conversion::cluster::get_range
0.86% 7291 cc1 cc1 [.]
optimize_function_for_size_p
looks like there's obvious quadraticness here when doing the summing:
bool
jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
unsigned start, unsigned end)
{
..
for (unsigned i = start; i <= end; i++)
{
simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
comparison_count += sc->m_range_p ? 2 : 1;
}
and we're almost trying all possible clusters in
jump_table_cluster::find_jump_tables
Now, there's the possibility of doing a quick guess before doing this
loop, once via using (end - start) and once via using 2 * (end - start).
Only if the first can be handled and the second not we have to compute.
Martin?
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (2 preceding siblings ...)
2021-05-03 13:48 ` rguenth at gcc dot gnu.org
@ 2021-05-03 13:58 ` rguenth at gcc dot gnu.org
2021-05-10 12:22 ` marxin at gcc dot gnu.org
` (7 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-05-03 13:58 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
I guess that's already done, so it has to be fixed in other ways, like by
keeping the partial sum when decreasing the size in
for (unsigned j = 0; j < i; j++)
{
if (min[j].m_count + 1 < min[i].m_count
&& can_be_handled (clusters, j, i - 1))
min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
}
maybe "simply" binary search j in [0, i-1] rather than doing a linear
search here.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (3 preceding siblings ...)
2021-05-03 13:58 ` rguenth at gcc dot gnu.org
@ 2021-05-10 12:22 ` marxin at gcc dot gnu.org
2021-06-01 8:20 ` rguenth at gcc dot gnu.org
` (6 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: marxin at gcc dot gnu.org @ 2021-05-10 12:22 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
Martin Liška <marxin at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Assignee|unassigned at gcc dot gnu.org |marxin at gcc dot gnu.org
Status|NEW |ASSIGNED
--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
Mine.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (4 preceding siblings ...)
2021-05-10 12:22 ` marxin at gcc dot gnu.org
@ 2021-06-01 8:20 ` rguenth at gcc dot gnu.org
2021-08-13 15:25 ` marxin at gcc dot gnu.org
` (5 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-06-01 8:20 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|9.4 |9.5
--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (5 preceding siblings ...)
2021-06-01 8:20 ` rguenth at gcc dot gnu.org
@ 2021-08-13 15:25 ` marxin at gcc dot gnu.org
2021-08-13 15:26 ` marxin at gcc dot gnu.org
` (4 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: marxin at gcc dot gnu.org @ 2021-08-13 15:25 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
--- Comment #7 from Martin Liška <marxin at gcc dot gnu.org> ---
> Now, there's the possibility of doing a quick guess before doing this
> loop, once via using (end - start) and once via using 2 * (end - start).
> Only if the first can be handled and the second not we have to compute.
Yeah, we already to that, problem with this test-case is that it's density is
very close to the max growth limit (8x).
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (6 preceding siblings ...)
2021-08-13 15:25 ` marxin at gcc dot gnu.org
@ 2021-08-13 15:26 ` marxin at gcc dot gnu.org
2021-08-16 11:38 ` cvs-commit at gcc dot gnu.org
` (3 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: marxin at gcc dot gnu.org @ 2021-08-13 15:26 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
--- Comment #8 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> I guess that's already done, so it has to be fixed in other ways, like by
> keeping the partial sum when decreasing the size in
I can confirm the decreasing works pretty well and we get to 6s with -O0. Hope
it's a reasonable fix.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (7 preceding siblings ...)
2021-08-13 15:26 ` marxin at gcc dot gnu.org
@ 2021-08-16 11:38 ` cvs-commit at gcc dot gnu.org
2021-08-16 11:38 ` [Bug tree-optimization/100393] [9/10/11 " marxin 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-08-16 11:38 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Martin Liska <marxin@gcc.gnu.org>:
https://gcc.gnu.org/g:c517cf2e685e2903b591d63c1034ff9726cb3822
commit r12-2928-gc517cf2e685e2903b591d63c1034ff9726cb3822
Author: Martin Liska <mliska@suse.cz>
Date: Fri Aug 13 17:22:35 2021 +0200
Speed up jump table switch detection.
PR tree-optimization/100393
gcc/ChangeLog:
* tree-switch-conversion.c (group_cluster::dump): Use
get_comparison_count.
(jump_table_cluster::find_jump_tables): Pre-compute number of
comparisons and then decrement it. Cache also max_ratio.
(jump_table_cluster::can_be_handled): Change signature.
* tree-switch-conversion.h (get_comparison_count): New.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (8 preceding siblings ...)
2021-08-16 11:38 ` cvs-commit at gcc dot gnu.org
@ 2021-08-16 11:38 ` marxin at gcc dot gnu.org
2021-11-05 16:09 ` cvs-commit at gcc dot gnu.org
2021-11-05 16:10 ` marxin at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: marxin at gcc dot gnu.org @ 2021-08-16 11:38 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
Martin Liška <marxin at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Known to work| |12.0
Summary|[9/10/11/12 Regression] |[9/10/11 Regression] Very
|Very slow compilation of |slow compilation of switch
|switch statement with |statement with thousands of
|thousands of cases |cases
--- Comment #10 from Martin Liška <marxin at gcc dot gnu.org> ---
Fixed on master so far.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (9 preceding siblings ...)
2021-08-16 11:38 ` [Bug tree-optimization/100393] [9/10/11 " marxin at gcc dot gnu.org
@ 2021-11-05 16:09 ` cvs-commit at gcc dot gnu.org
2021-11-05 16:10 ` marxin at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-11-05 16:09 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Martin Liska
<marxin@gcc.gnu.org>:
https://gcc.gnu.org/g:95c7ef9fbcf2c4b760c296fae597f093b6ee9aaa
commit r11-9209-g95c7ef9fbcf2c4b760c296fae597f093b6ee9aaa
Author: Martin Liska <mliska@suse.cz>
Date: Fri Aug 13 17:22:35 2021 +0200
Speed up jump table switch detection.
PR tree-optimization/100393
gcc/ChangeLog:
* tree-switch-conversion.c (group_cluster::dump): Use
get_comparison_count.
(jump_table_cluster::find_jump_tables): Pre-compute number of
comparisons and then decrement it. Cache also max_ratio.
(jump_table_cluster::can_be_handled): Change signature.
* tree-switch-conversion.h (get_comparison_count): New.
(cherry picked from commit c517cf2e685e2903b591d63c1034ff9726cb3822)
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/100393] [9/10/11 Regression] Very slow compilation of switch statement with thousands of cases
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
` (10 preceding siblings ...)
2021-11-05 16:09 ` cvs-commit at gcc dot gnu.org
@ 2021-11-05 16:10 ` marxin at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: marxin at gcc dot gnu.org @ 2021-11-05 16:10 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100393
Martin Liška <marxin at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Known to work| |11.2.0
Known to fail|11.1.0 |
Resolution|--- |FIXED
--- Comment #12 from Martin Liška <marxin at gcc dot gnu.org> ---
Fixed on GCC 11, not planning backporting more.
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2021-11-05 16:10 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-03 11:46 [Bug c/100393] New: Very slow compilation of switch statement with thousands of cases curiousdannii at gmail dot com
2021-05-03 12:04 ` [Bug c/100393] " curiousdannii at gmail dot com
2021-05-03 13:37 ` [Bug tree-optimization/100393] [9/10/11/12 Regression] " rguenth at gcc dot gnu.org
2021-05-03 13:48 ` rguenth at gcc dot gnu.org
2021-05-03 13:58 ` rguenth at gcc dot gnu.org
2021-05-10 12:22 ` marxin at gcc dot gnu.org
2021-06-01 8:20 ` rguenth at gcc dot gnu.org
2021-08-13 15:25 ` marxin at gcc dot gnu.org
2021-08-13 15:26 ` marxin at gcc dot gnu.org
2021-08-16 11:38 ` cvs-commit at gcc dot gnu.org
2021-08-16 11:38 ` [Bug tree-optimization/100393] [9/10/11 " marxin at gcc dot gnu.org
2021-11-05 16:09 ` cvs-commit at gcc dot gnu.org
2021-11-05 16:10 ` marxin at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).