Comment #0 by peter.alexander.au — 2011-12-22T15:12:18Z
The optimiser in DMD appears to operate in O(n^2) time with respect to function length, which causes programs with large functions to take quite a long time to optimise. The program below demonstrates this with repeated increments, but note that you get similar results for more typical long functions.
string rep(string s, int n)
{
return n > 1 ? s ~ rep(s, n-1) : s;
}
void main()
{
int i;
version (A) mixin(rep("++i;", 250));
version (B) mixin(rep("++i;", 500));
version (C) mixin(rep("++i;", 750));
version (D) mixin(rep("++i;", 1000));
}
dmd test.d -O -version=A 0.82s user 0.03s system 92% cpu 0.916 total
dmd test.d -O -version=B 3.01s user 0.03s system 94% cpu 3.226 total
dmd test.d -O -version=C 6.58s user 0.04s system 97% cpu 6.806 total
dmd test.d -O -version=D 11.52s user 0.05s system 97% cpu 11.882 total
Without optimisation, compilation is near-instant in all cases.
Comment #1 by clugdbug — 2011-12-22T21:02:59Z
This is most likely the O(n^^2) behaviour of the optimization of the comma operator, where n is the maximum depth of comma expressions.
Each pass through the optimizer only removes the deepest comma, and each pass involves several operations which are O(n). Even finding the deepest comma is O(n).
Comment #2 by clugdbug — 2011-12-23T00:14:59Z
See bug 2396. I'd close this as a duplicate, except that the test case in this one is much better.
Comment #3 by lomereiter — 2014-01-02T12:23:30Z
*** Issue 11859 has been marked as a duplicate of this issue. ***
Comment #4 by code — 2015-03-03T20:44:08Z
I'm getting excessive compile times for a few phobos modules in release unittests.
Most notably std.regex.internal.tests, and std.datetime.
Can we try to do the static foreach delegate trick again?
time ../dmd/src/dmd -conf= -I../druntime/import -w -dip25 -m64 -O -release -unittest -c -ofgenerated/osx/release/64/unittest/std/datetime.o -deps=generated/osx/release/64/unittest/std/datetime.deps.tmp std/datetime.d
180.96 real 132.19 user 48.76 sys
time ../dmd/src/dmd -conf= -I../druntime/import -w -dip25 -m64 -O -release -unittest -c -ofgenerated/osx/release/64/unittest/std/random.o -deps=generated/osx/release/64/unittest/std/random.deps.tmp std/random.d
21.23 real 15.68 user 5.53 sys
time ../dmd/src/dmd -conf= -I../druntime/import -w -dip25 -m64 -O -release -unittest -c -ofgenerated/osx/release/64/unittest/std/regex/internal/tests.o -deps=generated/osx/release/64/unittest/std/regex/internal/tests.deps.tmp std/regex/internal/tests.d
250.31 real 184.75 user 65.55 sys
Another case of this.
https://github.com/etcimon/botan/issues/8
It took dmd almost 13 minutes to compile botan w/ release optimizations on heroku (and about 4 minutes on my local machine).
Comment #9 by code — 2015-11-08T18:27:28Z
Could we fix this for now by letting dmd backoff from very big functions?
Or if someone understands accumaecpx well enough, maybe the optimization can be windowed to 1000 expressions/statements or so.
Comment #10 by kozzi11 — 2016-12-22T08:28:44Z
*** Issue 14939 has been marked as a duplicate of this issue. ***
Comment #11 by andrei — 2016-12-22T12:39:24Z
I just realized that a precise GC using introspection would use exactly this facility.
Comment #12 by bugzilla — 2016-12-22T13:34:12Z
There is some quadratic behavior in the function bodies of `updaterd` and `accumaecpx` (look for the loops). They can both be fixed.