Our template emission strategy is broken

[Martin Nowak via Digitalmars-d]

On Wednesday, 11 November 2015 at 17:19:31 UTC, David Nadlinger 
wrote:
> Yes, there is a single cyclic inter-package dependency hidden
> somewhere deep inside the dependency graph, but getting rid
> of it after the fact would  have either required re-structuring
> large parts of a ˜10^5 LOC code base, or would have again
> involved creating logical

Understood. FWIW it'd be more of a help to dig down and fix that 
particular bug sooner rather than going back to come up with a 
new template emission design.

Cross-Posting my Bugzilla comment here.
https://issues.dlang.org/show_bug.cgi?id=15318#c1

This seems to be a case where the second rule of this issue 14431 
fix doesn't work.
http://forum.dlang.org/post/mailman.697.1440962414.13986.digitalmars-d-bugs@puremagic.com

> If a template is instantiated in non-root module, compiler 
> usually does not have to put it in object file. But if a 
> template is instantiated in both of root and non-root modules 
> which mutually import each other, it needs to placed in objfile.

===

In both of the compilations there is a root and a non-root module 
instantiating bar!5. Now unfortunately the compiler decides both 
times that the non-root module should do it.
This problem would be solved by my proposal to define a global 
order for who is responsible to instantiate a template, by 
choosing the module with the lexicographically smaller module 
name.
https://github.com/D-Programming-Language/dmd/pull/4384#discussion_r29910422
https://issues.dlang.org/show_bug.cgi?id=14431#c12

This would establish a stable order between B and C, and no 
matter how you compile them, B gets to instantiate the template.

===

An intermediate workaround for your problem is to use the 
-allinst switch, even though it slows down compilation a lot. You 
can also compile each module separately in which case both B and 
C get the instance (in general this is even slower than -allinst).

===

> packages so large that the memory inefficiencies (CTFE is the 
> biggest problem here) and run-time scaling issues (e.g. O(n^2) 
> behavior in the overall number of templates) in the front-end 
> become a problem again.

There shouldn't be anything quadratic left for template 
instantiation in the frontend.