• d-bugmail puremagic.com (38/38) Apr 24 2023 https://issues.dlang.org/show_bug.cgi?id=23857

d-bugmail puremagic.com writes:

https://issues.dlang.org/show_bug.cgi?id=23857

          Issue ID: 23857
           Summary: Compilation of certain recursion takes too long
           Product: D
           Version: D2
          Hardware: x86_64
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P1
         Component: dmd
          Assignee: nobody puremagic.com
          Reporter: hos hos.ac

The following program takes too long to compile with `dmd -O -inline -release`:

int f(int[] a, int u) {
  return (a[u] < 0) ? u : (a[u] = f(a, a[u]));
}
void main() {
  enum N = 10;
  auto a = new int[N << 1];
  a[] = -1;
  foreach (i; 0 .. N) {
    f(a, i << 1);
    f(a, i << 1 | 1);
  }
}

Measurements:
- It takes ~26 seconds on my PC (WSL2, DMD64 D Compiler v2.103.0).
- Removing any of -O, -inline, and -release reduces the compilation time to <1
second.
- Removing the line with "f(a, i << 1 | 1);" reduces the compilation time to ~6
seconds.

Note:
- The recursive function can appear naturally when implementing Union-Find data
structure.
- I found this issue when solving problems at https://yukicoder.me/; CentOS
Stream release 8, DMD64 2.102.2.

--