Slow code, slow

[H. S. Teoh]

On Fri, Feb 23, 2018 at 08:41:17PM +0000, bauss via Digitalmars-d wrote:
[...]
> It actually matters a lot for big projects with lots of templates,
> especially nested templates. Gets a whole lot worse when it's
> templates within mixin templates with templates.

The situation has actually improved somewhat after Rainer's symbol
backreferencing PR was merged late last year. Before that, deeply nested
templates were spending most of their time generating, scanning, and
writing out 20MB-long symbols. :-D

Now that superlong symbols are no longer the bottleneck, though, other
issues with the implementation of templates are coming to the surface.
Like this one, where it takes *3 seconds* to compile a program
containing a *single* (trivial) regex:

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


> It's not just a "0.3" second difference, but can be half a minute or
> even more.

In the old days, when yours truly submitted a naïve implementation of
cartesianProduct to Phobos, compiling Phobos unittests would cause the
autotester to freeze for a long time and then die with an OOM, because
using cartesianProduct with multiple arguments caused an exponential
number of templates to get instantiated. :-D

Over the years there have also been a number of PRs that try to mitigate
the problem somewhat by, e.g., replacing a linearly-recursive template
(usually tail-recursive -- but the compiler currently does not take
advantage of that) with a divide-and-conquer scheme instead. A lot of
stuff that iterates over AliasSeq suffers from this problem, actually.
AIUI, due to the way templates are currently implemented, a
linearly-recursive template causes quadratic slowdown in compilation
time.  Clearly, the quality of implementation needs improvement here.


T

-- 
Once bitten, twice cry...