https://issues.dlang.org/show_bug.cgi?id=17135

--- Comment #1 from Nick Sabalausky <cbkbbejeap@mailinator.com> ---
Forgot to include the relevent commit checkout:

$ git clone https://github.com/Abscissa/SDLang-D.git sdlang
$ cd sdlang
$ git checkout 6b2097f6944
$ dub test --build=release

--

https://issues.dlang.org/show_bug.cgi?id=17135

ag0aep6g@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ag0aep6g@gmail.com

--- Comment #2 from ag0aep6g@gmail.com ---
1) Use dub's -v switch to get the dmd command. Then get rid of dub. From the dmd command, throw unneeded arguments away one by one; both switches and source files.

Result: dmd -c -O -unittest -Isrc src/sdlang/lexer.d

2) Remove all unittests from lexer.d. Compiles quickly now. Check unittest blocks individually.

It's the large one at line 1552.

3) Reduce that beast. Just delete from the end.

Turns out when I delete just that last `stderr.writeln` part, compilation finishes in 14 seconds on my machine. If I leave it in, it takes forever. Huh. Seems that `if (numErrors > 0) writeln();` makes the optimizer take much longer.

4) Minimize the code of the unittest by generating many identical testLex calls. Delete almost all the rest of lexer.d.

Result:

----
module sdlang.lexer;

import sdlang.symbol;
import sdlang.token;
import sdlang.util;

int numErrors = 0;
void testLex(string source, Token[] expected) {}

unittest
{
    enum n = 110;
    import std.array: replicate;
    mixin(
        `testLex("", [ Token(symbol!"Value", Location.init, Value(0)) ]);`
        .replicate(n)
    );

    import std.stdio;
    if (numErrors > 0) writeln();
}
----

That compiles in about 10 seconds on my machine. If I remove the writeln line, it compiles in under 2 seconds. Can make the ratio more extreme by increasing n.

5) Incorporate Token, Symbol, Location. Get rid of most of Phobos. Generally reduce.

Final result:

----
int numErrors = 0;
void testLex(Token expected) {}
void writeln();

void main()
{
    enum n = 110;
    import std.array: replicate;
    mixin(
        `testLex(Token(Symbol.init, Location.init));`
        .replicate(n)
    );

    if (numErrors > 0) writeln();
}

struct Token
{
    Symbol symbol;
    Location location;

    this(Symbol symbol, Location location) {}
}

struct Location { ubyte[32] data; }
    /* The size of Location.data matters:
        * 8 bytes or less - problem much less pronounced,
        * 9 through 32 bytes (didn't check every number) - very slow
optimization,
        * more than 32 bytes - problem much, much less pronounced.
    */
struct Symbol {}
----

Call that file file test.d. Delete everything else.

Compile with `dmd -c -O test.d`. Takes about 10 seconds on my machine. Remove the writeln line in main and it takes under one second. Increase n to make the ratio more extreme. At n = 200, compilation takes 1m42s for me. Seems to be quadratic.

--

https://issues.dlang.org/show_bug.cgi?id=17135

ag0aep6g@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |performance

--

https://issues.dlang.org/show_bug.cgi?id=17135

anonymous4 <dfj1esp02@sneakemail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Hardware|x86_64                      |All
            Summary|DMD hangs when compiling in |Optimization of big
                   |release mode                |functions takes a lot of
                   |                            |time
                 OS|Linux                       |All

--- Comment #3 from anonymous4 <dfj1esp02@sneakemail.com> ---
IIRC there was an issue about this - dmd backend optimization is quadratic on function size, though can't find it now.

--

https://issues.dlang.org/show_bug.cgi?id=17135

anonymous4 <dfj1esp02@sneakemail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kriptogames@gmail.com

--- Comment #4 from anonymous4 <dfj1esp02@sneakemail.com> ---
*** Issue 17410 has been marked as a duplicate of this issue. ***

--

https://issues.dlang.org/show_bug.cgi?id=17135

--- Comment #5 from ag0aep6g@gmail.com ---
(In reply to anonymous4 from comment #3)
> IIRC there was an issue about this - dmd backend optimization is quadratic on function size, though can't find it now.

I remember issue 14571, but there it was the size of a fixed-sized array.

--

https://issues.dlang.org/show_bug.cgi?id=17135

Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |21121


Referenced Issues:

https://issues.dlang.org/show_bug.cgi?id=21121
[Issue 21121] Optimizer slowdowns
--

https://issues.dlang.org/show_bug.cgi?id=17135

Iain Buclaw <ibuclaw@gdcproject.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |backend
                 CC|                            |ibuclaw@gdcproject.org

--

https://issues.dlang.org/show_bug.cgi?id=17135

Imperatorn <johan_forsberg_86@hotmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |johan_forsberg_86@hotmail.c
                   |                            |om

--- Comment #6 from Imperatorn <johan_forsberg_86@hotmail.com> ---
Is this still the case?

--

https://issues.dlang.org/show_bug.cgi?id=17135

--- Comment #7 from Iain Buclaw <ibuclaw@gdcproject.org> ---
(In reply to Imperatorn from comment #6)
> Is this still the case?

There are still a number of quadratic loops in the backend, whilst they still exist, all bugs assigned to the meta issue 21121 are valid.

--