Bug 10866 – Regression (2.064 git-head) Massive compiler slowdown

What's up with the slowdown of the compiler in git-head? Here is the average time to build this simple test-file: ----- module test; import std.stdio; void main() { } ----- 2.063.2: 392 msecs Git-head (1a6da16ef112e03607574758b722698f2950b0de): 1_251 msecs The timings are pretty stable from my end. In another one of my projects the timings are: 3_500 ms in 2.063 4_800 ms in 2.064 The codebase is around 10K. However in other projects I get a speedup. Here's WindowsAPI being built: 2.063: 19_903 msecs. 2.064: 9_782 msecs. I guess Walter's recent speedups made the compiler faster. But there must have been acommit which seems to have slowed some other things down. According to Don it may have been this pull: https://github.com/D-Programming-Language/dmd/pull/2421#issuecomment-22688675 And I can confirm it from my side. In the 10K project I've tried running a full build with these two DMD commits: commit A: 805dd761dd85c98d60b3957bd5679cdbbf23c7f2 commit B: 52cc28752a6fd01446fd09a7ab9bd9f94ea601d2 commit A is the one introduced by Pull request #2421, commit B is one commit before it. Measurements: commit A: 4_795 msecs commit B: 3_900 msecs

(In reply to comment #0) > What's up with the slowdown of the compiler in git-head? Here is the > average time to build this simple test-file: Forget this line, I copy-pasted it from the NG post I made. It must have just been an oversight.

Maybe related: http://d.puremagic.com/issues/show_bug.cgi?id=10864 ? Although that's actually a run-time slowdown. Appender is also widely used with CTFE, so that could be it? Does your code base depend on Phobos?

Commits pushed to master at https://github.com/D-Programming-Language/dmd https://github.com/D-Programming-Language/dmd/commit/751353c8217596726ab219b7d3a690e8950e409e fix Issue 10866 - Regression (2.064 git-head) Massive compiler slowdown Revert part of the change in commit 805dd761dd85c98d60b3957bd5679cdbbf23c7f2. Read the detailed comment in code. https://github.com/D-Programming-Language/dmd/commit/1399b1f7b94ef1c1b24f2ce842b6f247e2e1fc52 Merge pull request #2496 from 9rnsr/fix10866 Issue 10866 - Regression (2.064 git-head) Massive compiler slowdown

Well the timings are better now, but they're still more than twice as slow: 2.063.2: 390 msecs Git-head: 970 msecs Unless std.stdio has started importing a lot more modules, I wouldn't consider this issue to be fixed.

(In reply to comment #5) > Well the timings are better now, but they're still more than twice as slow: > > 2.063.2: > 390 msecs > > Git-head: > 970 msecs > > Unless std.stdio has started importing a lot more modules, I wouldn't consider > this issue to be fixed. This is a significant issue, so if you think the problem is not yet fully solved, then I suggest you to reopen this issue. What are the timings for your two other cases (your project and the WindowsAPI)?

(In reply to comment #0) > However in other projects I get a speedup. Here's WindowsAPI being built: > > 2.063: 19_903 msecs. > 2.064: 9_782 msecs. This is now 12_000 msecs in git-head, so it's gotten worse.

Reopened because Andrej Mitrovic says the problem is not yet solved. (Close down again if I am wrong.)

(In reply to comment #8) > Reopened because Andrej Mitrovic says the problem is not yet solved. (Close > down again if I am wrong.) I will try and produce some reliable test-cases in the coming days.

I've pasted some fresh tests off of git-head when testing Pull 2550: https://github.com/D-Programming-Language/dmd/pull/2550#issuecomment-24319121 In many of these tests using 2.064 git-head is twice as slow as compiling with 2.063.2. However WindowsAPI itself seems to build much faster (those recent compiler optimizations might have hit a sweet spot for this library).

As I've commented in https://github.com/D-Programming-Language/dmd/pull/2550#issuecomment-24353784, this is a Phobos issue, not a compiler one. I'm copying that comment here verbatim: I've reduced it to a Phobos commit: --- 9a053d97c26d763718b23d14af8ef1d10d594507 is the first bad commit commit 9a053d97c26d763718b23d14af8ef1d10d594507 Author: Dmitry Olshansky <[email protected]> Date: Sat Jul 20 22:30:10 2013 +0400 new std.uni module --- If you check out the following commits for DMD+Druntime+Phobos: --- DMD: 4e9a7b1 Druntime: f6692fe Phobos: 9a053d9 --- Then compiling the following: --- import std.stdio; void main() { } --- Takes ~1270 msecs. If you checkout one Phobos commit earlier (which is `1bd22b2`), it takes ~500 msecs to compile it. Btw I can also reproduce this commit is the offending one with other libraries, like DCollections. I'm pretty sure most libraries import std.stdio at one point or another, so they will all suffer from this slowdown.

(In reply to comment #11) > As I've commented in > https://github.com/D-Programming-Language/dmd/pull/2550#issuecomment-24353784, > this is a Phobos issue, not a compiler one. I'm copying that comment here > verbatim: > > I've reduced it to a Phobos commit: > > --- > 9a053d97c26d763718b23d14af8ef1d10d594507 is the first bad commit > commit 9a053d97c26d763718b23d14af8ef1d10d594507 > Author: Dmitry Olshansky <[email protected]> > Date: Sat Jul 20 22:30:10 2013 +0400 > > new std.uni module Perhaps it's only part of the std.uni module that causes such compilation slowdown. So someone should try to find such parts, and then perhaps change the Phobos code to speed up the compilation, or introduce some front-end optimizations to deal more efficiently with those parts.

(In reply to comment #12) > (In reply to comment #11) > > As I've commented in > > https://github.com/D-Programming-Language/dmd/pull/2550#issuecomment-24353784, > > this is a Phobos issue, not a compiler one. I'm copying that comment here > > verbatim: > > > > I've reduced it to a Phobos commit: > > > > --- > > 9a053d97c26d763718b23d14af8ef1d10d594507 is the first bad commit > > commit 9a053d97c26d763718b23d14af8ef1d10d594507 > > Author: Dmitry Olshansky <[email protected]> > > Date: Sat Jul 20 22:30:10 2013 +0400 > > > > new std.uni module > > Perhaps it's only part of the std.uni module There was more than that module which was introduced, there is also std/internal/unicode_tables.d, which is 1.3 MB large.

(In reply to comment #13) > (In reply to comment #12) > > (In reply to comment #11) > > > As I've commented in > > > https://github.com/D-Programming-Language/dmd/pull/2550#issuecomment-24353784, > > > this is a Phobos issue, not a compiler one. I'm copying that comment here > > > verbatim: > > > > > > I've reduced it to a Phobos commit: > > > > > > --- > > > 9a053d97c26d763718b23d14af8ef1d10d594507 is the first bad commit > > > commit 9a053d97c26d763718b23d14af8ef1d10d594507 > > > Author: Dmitry Olshansky <[email protected]> > > > Date: Sat Jul 20 22:30:10 2013 +0400 > > > > > > new std.uni module > > > > Perhaps it's only part of the std.uni module > > There was more than that module which was introduced, there is also > std/internal/unicode_tables.d, which is 1.3 MB large. Perfect but .. we really need these tables.

(In reply to comment #14) > Perfect but .. we really need these tables. Yeah I assume we do. Maybe we can get rid of some spurious imports in std.stdio or some other module. Or, if there's no fix maybe we'll just have to live with it. But it's going to look real bad after Walter posted to Reddit about how the compiler is ~40% faster, and yet people's code is going to build slower on average in 2.064 due to Phobos bloating up.

> > > > 9a053d97c26d763718b23d14af8ef1d10d594507 is the first bad commit > > > > commit 9a053d97c26d763718b23d14af8ef1d10d594507 > > > > Author: Dmitry Olshansky <[email protected]> > > > > Date: Sat Jul 20 22:30:10 2013 +0400 > > > > > > > > new std.uni module > > > > > > Perhaps it's only part of the std.uni module > > > > There was more than that module which was introduced, there is also > > std/internal/unicode_tables.d, which is 1.3 MB large. > > Perfect but .. we really need these tables. I think that it's not the tables but rather the subtle thing is that a lot of tempalted code runs std.format and then we have this: private void formatChar(Writer)(Writer w, in dchar c, in char quote) { import std.uni : isGraphical; if (std.uni.isGraphical(c)) { if (c == quote || c == '\\') put(w, '\\'), put(w, c); else put(w, c); } That bounces as at CTFE to this: bool isGraphical(dchar c) { static immutable graphicalTrie = asTrie(graphicalTrieEntries); return graphicalTrie[c]; } And that hurts as there is no longer ASCII only case in place and said trie look up is only fast at R-T with proper inlining.

(In reply to comment #16) > I think that it's not the tables but rather the subtle thing is that > a lot of tempalted code runs std.format and then we have this: > > private void formatChar(Writer)(Writer w, in dchar c, in char quote) > { > import std.uni : isGraphical; > > if (std.uni.isGraphical(c)) > { > if (c == quote || c == '\\') > put(w, '\\'), put(w, c); > else > put(w, c); > } > > That bounces as at CTFE to this: > > bool isGraphical(dchar c) > { > static immutable graphicalTrie = asTrie(graphicalTrieEntries); > return graphicalTrie[c]; > } > > And that hurts as there is no longer ASCII only case in place > and said trie look up is only fast at R-T with proper inlining. Well that's not the case with simple import std.stdio + empty main. I think our only way out is to isolate the unicode_tables is separate compilation + ~ .di file so that compiler doesn't have to re-tokenize 1.3M file.

(In reply to comment #17) > I think our only way out is to isolate the unicode_tables is separate > compilation + ~ .di file so that compiler doesn't have to re-tokenize 1.3M > file. Please do so!

(In reply to comment #18) > (In reply to comment #17) > > I think our only way out is to isolate the unicode_tables is separate > > compilation + ~ .di file so that compiler doesn't have to re-tokenize 1.3M > > file. > > Please do so! I stand corrected as I just tested it. This is not a fix, it would be just another huge regression: everything in std.uni would stop being CTFE-able at all. This cascades to things such as toLower, isGraphical and such that are being used everywhere. It would also destroy my effort to free std.regex from reinventing its own unicode stuff internally. I'm going to investigate what exactly takes that much time e.g. dmd -c std\internal\unicode_tables.d Takes around 110 ms for me, quite a lot but not a showstopper. That means both tokenization and compilation was performed and yet even half a second is not seen.

I observed a 6x slow down when compiling a simple vibe.d server. Perf tells me that >80% of the time is spend in dtnzeros, presumably running into O(N^2) behavior for the list append. The trigger for this was huge array initializers, i.e. ubyte[64*1024] buffer;. The fix is to void initialize those. While the trigger might be some huge array initializer the problem is an unsuited data structure in dmd. In FreeBSD parlance we should switch from an SLIST to STAILQ. http://www.freebsd.org/cgi/man.cgi?query=queue Also a zero initialized array shouldn't need on dt entry per element.

(In reply to comment #19) > (In reply to comment #18) > > (In reply to comment #17) [snip] > I'm going to investigate what exactly takes that much time > > e.g. > dmd -c std\internal\unicode_tables.d > > Takes around 110 ms for me, quite a lot but not a showstopper. That means both > tokenization and compilation was performed and yet even half a second is not > seen. This gets it down to ~90 ms. https://github.com/D-Programming-Language/phobos/pull/1632

(In reply to comment #22) > This gets it down to ~90 ms. > https://github.com/D-Programming-Language/phobos/pull/1632 Merged, but the table usage is still flawed. You put one instance of simpleCaseTable into every template instantiation of std.uni.sicmp (same for fullCaseTable and fullCasedCmp). So you have redundancy in the object files and compile overhead when instantiating sicmp/icmp. https://github.com/D-Programming-Language/phobos/pull/1636

What happened to making internal_tables.di ?

(In reply to comment #24) > What happened to making internal_tables.di ? Kills CTFE like I said and hence not an option.

Commit pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/5b5b5bbb68163a42e22cdb55e4f6dcc74a92609b Merge pull request #1636 from dawgfoto/issue10866 make case tables immutable

Commit pushed to 2.064 at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/5ee489620f82fbef10b0c9346283c74e28ac2c67 Merge pull request #1636 from dawgfoto/issue10866 make case tables immutable

This should be fixed now. Andrej could you please retest your projects and see if the latest beta has good timings?

(In reply to comment #28) > This should be fixed now. > Andrej could you please retest your projects and see if the latest beta has > good timings? Yeah, it's down to ~600 msecs now. I'm consistently getting a 200 msec increase from 2.063.2 (~400 msecs) to latest git-head, but I think it's safe to mark this as fixed. The slight increase of the hello world build time is barely noticeable now. Thanks for the hard work.