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@puremagic.com
        ReportedBy: peter.alexander.au@gmail.com


--- Comment #0 from Peter Alexander <peter.alexander.au@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: -------

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


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug@yahoo.com.au


--- Comment #1 from Don <clugdbug@yahoo.com.au> 2011-12-22 21:02:59 PST ---
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).

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

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



--- Comment #2 from Don <clugdbug@yahoo.com.au> 2011-12-23 00:14:59 PST ---
See bug 2396. I'd close this as a duplicate, except that the test case in this one is much better.

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