www.digitalmars.com         C & C++   DMDScript  

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

reply d-bugmail puremagic.com writes:
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: -------
Dec 22 2011
next sibling parent d-bugmail puremagic.com writes:
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: -------
Dec 22 2011
prev sibling parent d-bugmail puremagic.com writes:
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: -------
Dec 23 2011