[Issue 7157] New: Optimiser is O(n^2) w.r.t. function length

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=7157

           Summary: Optimiser is O(n^2) w.r.t. function length
           Product: D
           Version: D2
          Platform: x86
        OS/Version: Mac OS X
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody at puremagic.com
        ReportedBy: peter.alexander.au at gmail.com


--- Comment #0 from Peter Alexander <peter.alexander.au at gmail.com> 2011-12-22 15:12:18 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------