[Coroutines] The cross suspend point analysis is not scaling

[dyzsr]

The compilation time problem of C++20 coroutine still exists in Clang 16.0.2, after the fix to #58650.

Here shows the comparison of 2 scenarios (a2.cpp and a3.app).

• a2.cpp is like:

#include <cstdio>
#include <vector>
#include "task.h"
task t() {
std::vector<int> v(100000);
int val = 0;
if (v[1]) val++;
if (v[2]) val++;
if (v[3]) val++;
if (v[4]) val++;
...
if (v[99999]) val++;
if (v[100000]) val++;
printf("%d\n", val);
co_return;
}

• a3.cpp is like:

#include <cstdio>
#include <vector>
#include "task.h"
task t() {
std::vector<int> v(100000);
int val = 0;
auto foo = [&](int i) { if (v[i]) val++; };
foo(1);
foo(2);
foo(3);
...
foo(99999);
foo(100000);
printf("%d\n", val);
co_return;
}

Generation and test scripts:

• gen2.cpp generates use cases that possibly enable bounds checking.

#include <cassert>
#include <cstdio>
#include <cstdlib>

int main(int argc, char **argv) {
  assert(argc == 2);
  int n = atoi(argv[1]);
  printf("#include <cstdio>\n");
  printf("#include <vector>\n");
  printf("#include \"task.h\"\n");
  printf("task t() {\n");
  printf("std::vector<int> v(%d);\n", n);
  printf("int val = 0;\n");
  for (int i = 1; i <= n; i++) printf("if (v[%d]) val++;\n", i);
  printf("printf(\"%%d\\n\", val);\n");
  printf("co_return;\n");
  printf("}\n");
  return 0;
}

• gen3.cpp generates use cases that try to avoid bounds checking.

#include <cassert>
#include <cstdio>
#include <cstdlib>

int main(int argc, char **argv) {
  assert(argc == 2);
  int n = atoi(argv[1]);
  printf("#include <cstdio>\n");
  printf("#include <vector>\n");
  printf("#include \"task.h\"\n");
  printf("task t() {\n");
  printf("std::vector<int> v(%d);\n", n);
  printf("int val = 0;\n");
  printf("auto foo = [&](int i) { if (v[i]) val++; };\n");
  for (int i = 1; i <= n; i++) printf("foo(%d);\n", i);
  printf("printf(\"%%d\\n\", val);\n");
  printf("co_return;\n");
  printf("}\n");
  return 0;
}

• test2.sh

#!/bin/sh

clang++ -o gen2 gen2.cpp
for i in 20000 40000 60000 80000 100000
do
  printf "n: %d\n" $i
  ./gen2 $i > a2.cpp
  time clang++ -c a2.cpp -std=c++20 -stdlib=libc++
  printf "\n"
done

• test3.sh

#!/bin/sh

clang++ -o gen3 gen3.cpp
for i in 20000 40000 60000 80000 100000
do
  printf "n: %d\n" $i
  ./gen3 $i > a3.cpp
  time clang++ -c a3.cpp -std=c++20 -stdlib=libc++
  printf "\n"
done

Compilation time:

• test2

n: 20000

real    0m7.986s
user    0m7.537s
sys     0m0.430s

n: 40000

real    0m24.699s
user    0m23.221s
sys     0m1.420s

n: 60000

real    1m2.934s
user    0m57.135s
sys     0m5.651s

n: 80000

real    1m46.364s
user    1m36.321s
sys     0m9.787s

n: 100000

real    2m51.611s
user    2m40.468s
sys     0m10.736s

• test3

n: 20000

real    0m2.319s
user    0m2.194s
sys     0m0.120s

n: 40000

real    0m5.908s
user    0m5.227s
sys     0m0.667s

n: 60000

real    0m10.007s
user    0m9.271s
sys     0m0.712s

n: 80000

real    0m13.532s
user    0m11.979s
sys     0m1.522s

n: 100000

real    0m26.432s
user    0m23.669s
sys     0m2.697s

[llvmbot]

@llvm/issue-subscribers-coroutines

[ChuanqiXu9]

The root cause problem is that coroutines uses a textbook style data flow analysis for the lifetime analysis, which is powerful but not scaling. I feel it is not easy to refactor this fundamentally given it runs almost good for 5 years, we don't touch it frequently. So I can possibly only add some pruning techniques.

[ChuanqiXu9]

I tried to mitigate the issue. Now the numbers are:

Before:

n: 20000

real	0m11.081s
user	0m10.597s
sys	0m0.320s

n: 40000

real	0m32.927s
user	0m31.403s
sys	0m1.043s

n: 60000

real	1m2.145s
user	0m58.903s
sys	0m2.268s

n: 80000

real	1m47.143s
user	1m41.630s
sys	0m3.857s

n: 100000

real	2m34.758s
user	2m26.587s
sys	0m5.922s

After:

n: 20000

real	0m10.418s
user	0m9.945s
sys	0m0.311s

n: 40000

real	0m27.884s
user	0m26.430s
sys	0m1.036s

n: 60000

real	0m52.420s
user	0m49.321s
sys	0m2.267s

n: 80000

real	1m25.389s
user	1m20.247s
sys	0m3.856s

n: 100000

real	2m4.275s
user	1m56.405s
sys	0m5.975s

It is slightly better now. But I don't have an idea to fix the true issue really.

[witstorm95]

@ChuanqiXu9 I add a patch for this issue, please help to review it.

https://reviews.llvm.org/D154695