[Issue 23857] New: Compilation of certain recursion takes too long
d-bugmail at puremagic.com
d-bugmail at puremagic.com
Mon Apr 24 17:18:01 UTC 2023
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 at puremagic.com
Reporter: hos at 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.
--
More information about the Digitalmars-d-bugs
mailing list