[Bug c/100393] New: Very slow compilation of switch statement with thousands of cases

[Bug c/100393] New: Very slow compilation of switch statement with thousands of cases

[curiousdannii at gmail dot com]

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.

[Bug c/100393] Very slow compilation of switch statement with thousands of cases

[curiousdannii at gmail dot com]

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

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[rguenth at gcc dot gnu.org]

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+.

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[rguenth at gcc dot gnu.org]

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?

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[rguenth at gcc dot gnu.org]

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.

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[marxin at gcc dot gnu.org]

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.

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[rguenth at gcc dot gnu.org]

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.

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[marxin at gcc dot gnu.org]

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).

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[marxin at gcc dot gnu.org]

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.

[Bug tree-optimization/100393] [9/10/11/12 Regression] Very slow compilation of switch statement with thousands of cases

[cvs-commit at gcc dot gnu.org]

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.

[Bug tree-optimization/100393] [9/10/11 Regression] Very slow compilation of switch statement with thousands of cases

[marxin at gcc dot gnu.org]

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.

[Bug tree-optimization/100393] [9/10/11 Regression] Very slow compilation of switch statement with thousands of cases

[cvs-commit at gcc dot gnu.org]

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)

[Bug tree-optimization/100393] [9/10/11 Regression] Very slow compilation of switch statement with thousands of cases

[marxin at gcc dot gnu.org]

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.