https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87663
Bug ID: 87663
Summary: Exorbitant compile times
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c++
Assignee: unassigned at gcc dot gnu.org
Reporter: lumosimann at gmail dot com
Target Milestone: ---
Created attachment 44864
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=44864&action=edit
Comparison
Let's try to calculate fiboncacchi numbers at compile time in exponential time.
This is a bad implementation of course, but I use that as a placeholder for any
other algorithm with much recursion.
Consider this code:
```
#include <iostream>
#include <type_traits>
template <int X, int A, int Z>
struct C : std::integral_constant<int, //
C<X + (1 << A), A - 1, Z + (1 << A)>::value -
C<X + (1 << A), A - 2, Z>::value> {};
template <int X, int A, int Z>
struct D : std::integral_constant<int, //
D<X + (1 << A), A - 1, Z + (1 << A)>::value -
D<X + (1 << A), A - 1, Z>::value> {};
template <int X, int Z>
struct C<X, 0, Z> : std::integral_constant<int, X> {};
template <int X, int Z>
struct C<X, 1, Z> : std::integral_constant<int, X + 1> {};
template <int X, int Z>
struct D<X, 0, Z> : std::integral_constant<int, X> {};
template <int X, int Z>
struct D<X, 1, Z> : std::integral_constant<int, X + 1> {};
int main() {
std::cout << C_OR_D<0, N, 0>::value << std::endl;
return 0;
}
```
Let's think about compile time complexity with respect to `N` when compiling
this code (`C_OR_D` stands for either `C` or `D`).
`C` calculates kind of a fibonacchi number with some non-important
modification to avoid overflows (`f_n = f_{n-1} - f_{n-2}`). I would expect
compile times to behave like `t_n = t_{n-1} + t_{n-2} = O(1.6^n)`.
`D` is a slightly modified version and we calculate `f_n = f_{n-1} - f_{n-1}`,
which is much more expensive of course. I would expect compile times to behave
like `t_n = t_{n-1} + t_{n-1} = O(2^n)`.
Let's first look at `D`, where I expect compile times of O(2^n):
* Compile times with Clang 7.0.0 for `D`:
> 495 ms ± 5.17 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 679 ms ± 4.92 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 1.07 s ± 10.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 1.85 s ± 39.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 3.4 s ± 20 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 6.48 s ± 79 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 12.9 s ± 227 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Note that I dropped compile times for low `n`, as long as the constant
dominates, and my stop condition is that compile-time is larger than 10 s. For
comparison, I refer to the attachment.
We see that after a while, compile times double when incrementing `n`, which is
prefect.
* Compile times with GCC 8.2.1 for `D`:
> ...
> 620 ms ± 26.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 973 ms ± 21.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 1.69 s ± 15.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 3.38 s ± 39.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 6.6 s ± 102 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 13.5 s ± 446 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Also here, we observe that compile times double when incrementing `n`.
In absolute numbers, gcc is slightly faster for low numbers, and worse for
large `n`. See attachment (left, "Power of Two").
Let's now look at `C` (Fibonacchi):
* Compile times with Clang 7.0.0 for `C`:
> ...
> 1.41 s ± 13.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 2.06 s ± 17.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 3.18 s ± 51.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 5.16 s ± 273 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 8.01 s ± 219 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 13.1 s ± 385 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Isn't this nice? This is a fibonacchi sequence! Let's continue with GCC.
* Compile times with GCC 8.2.1 for `C`:
> ...
> 964 ms ± 14.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 1.8 s ± 38 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 4.95 s ± 252 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
> 17.8 s ± 822 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
What is that? Compile times explode! It turns out that compile times for this
example are around O(3^n), much worse than `D` for almost any `n`.
In absolute numbers, gcc becomes soon terribly slow. See attachment (right,
"Fibonacchi").
Questions:
* Why does this behavior occur?
* Could this behavior have any impact on real-life code? I would assume yes.
