www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8487] New: Semantic analysis of templates is insanely slow

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487

           Summary: Semantic analysis of templates is insanely slow
           Product: D
           Version: unspecified
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: major
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: jmdavisProg gmx.com


--- Comment #0 from Jonathan M Davis <jmdavisProg gmx.com> 2012-07-31 19:57:58
PDT ---
Created an attachment (id=1129)
Module with named entities which takes 6+ minutes to compile

The attached program is a slightly altered version of what I currenly have in
the D lexer that I'm putting together. It uses some TypeTuples, a template, and
some mixins to fill an AA with all of the named HTML entities and their values.
It has a second template and associated mixins to test that the names and
values match dmd. It takes over _6 minutes_ to build on my Phenom II. This is
_insanely_ slow and is a serious impediment for the lexer that I'm working on.

Based on the results of using googleperftools on the compiler, it appears that
the vast majority of the time is spent on the semantic analysis of templates.
I'll attach the full results shortly, but this is the top

   10042  30.4%  30.4%    32889  99.6% TemplateInstance::semantic
    8391  25.4%  55.8%    22394  67.8% arrayObjectMatch
    8240  25.0%  80.8%    14045  42.5% match
    3153   9.6%  90.4%     3153   9.6% StringExp::compare
    1656   5.0%  95.4%     5075  15.4% StringExp::equals
     654   2.0%  97.3%      654   2.0% Expression::dyncast
     247   0.7%  98.1%      247   0.7% __GI_memcmp
      76   0.2%  98.3%       81   0.2% _int_malloc
      63   0.2%  98.5%       63   0.2% __GI_memcpy
      52   0.2%  98.7%       52   0.2% Tuple::dyncast
      35   0.1%  98.8%      107   0.3% __libc_malloc
      31   0.1%  98.9%       31   0.1% touchfunc
      25   0.1%  99.0%       56   0.2% ecom
      12   0.0%  99.0%       80   0.2% VarDeclaration::syntaxCopy
      10   0.0%  99.0%       15   0.0% _IO_vfprintf

To quote the googleperftools' docs (
http://google-perftools.googlecode.com/svn/trunk/doc/cpuprofile.html ):

------------
Text mode has lines of output that look like this:
       14   2.1%  17.2%       58   8.7% std::_Rb_tree::find

Here is how to interpret the columns:
1. Number of profiling samples in this function 
2. Percentage of profiling samples in this function 
3. Percentage of profiling samples in the functions printed so far 
4. Number of profiling samples in this function and its callees 
5. Percentage of profiling samples in this function and its callees 
6. Function name
------------

which should explain the format of the above results.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 31 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487



--- Comment #1 from Jonathan M Davis <jmdavisProg gmx.com> 2012-07-31 20:00:40
PDT ---
Created an attachment (id=1130)
The results of profiling dmd with googleperftools when compiling the previously
attached file

Here's the full results from googleperftools.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487


timon.gehr gmx.ch changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |timon.gehr gmx.ch


--- Comment #2 from timon.gehr gmx.ch 2012-07-31 20:36:37 PDT ---
Well, the performance can probably be improved, but I'd advise rewriting that
snippet to use CTFE instead. Templates aren't meant for computation.
Also, std.metastrings should be rewritten to wrap a few CTFE-routines or be
deprecated.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487



--- Comment #3 from Jonathan M Davis <jmdavisProg gmx.com> 2012-07-31 20:45:16
PDT ---

 Well, the performance can probably be improved, but I'd advise rewriting that


snippet to use CTFE instead.

I'm trying to figure out how to do that, and I'll probably manage it, but that
means using an array instead of TypeTuple, and arrays don't have the benefit of
forcing CTFE, making it much harder (and the need to have the literals treated
as literals at the right time and not before also complicates things). It's
quite clean with TypeTuples (aside from the fact that I'm forced to split it
across multiple type tuples so that the template instantiations don't choke at
100, thinking that they're recursing infinitely), and I'd much prefer to use
them, but with this poor performance, it's not really reasonable.


 Templates aren't meant for computation.


I don't buy that. D's templates are specifically designed in a way to make that
sort of thing possible, and in this particular case, using templates is
definitely easier than CTFE.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487



--- Comment #4 from timon.gehr gmx.ch 2012-07-31 21:39:19 PDT ---
Created an attachment (id=1131)
Shorter and simpler module with named entities which takes 0.2+ seconds to
compile

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487



--- Comment #5 from timon.gehr gmx.ch 2012-07-31 21:42:23 PDT ---
(In reply to comment #3)

 Well, the performance can probably be improved, but I'd advise rewriting that


 snippet to use CTFE instead.
 
 I'm trying to figure out how to do that, and I'll probably manage it, but that
 means using an array instead of TypeTuple, and arrays don't have the benefit of
 forcing CTFE, making it much harder (and the need to have the literals treated
 as literals at the right time and not before also complicates things). It's
 quite clean with TypeTuples (aside from the fact that I'm forced to split it
 across multiple type tuples so that the template instantiations don't choke at
 100, thinking that they're recursing infinitely), and I'd much prefer to use
 them, but with this poor performance, it's not really reasonable.
 


See the attachment I created for a possible solution.


 Templates aren't meant for computation.


 
 I don't buy that. D's templates are specifically designed in a way to make that
 sort of thing possible, and in this particular case, using templates is
 definitely easier than CTFE.


I disagree.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487



--- Comment #6 from Jonathan M Davis <jmdavisProg gmx.com> 2012-07-31 22:13:26
PDT ---
Thanks for your solution, though I did figure one out just a little bit ago.

Regardless, I think that the original solution should compile in a reasonably
short period of time (as in seconds) rather than 6+ minutes. And given how
template-heavy D code generally is (especially Phobos), templates really need
to be optimized, or compilation times will suffer.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugzilla digitalmars.com


--- Comment #7 from Walter Bright <bugzilla digitalmars.com> 2012-08-01
02:08:47 PDT ---
My initial impression is that the slowdown is caused by looking for a match
with a previous instantiation by using a linear search.

This can be fixed by using a hash table instead.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 01 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8487


Jacob Carlborg <doob me.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |doob me.com


--- Comment #8 from Jacob Carlborg <doob me.com> 2012-08-01 02:14:12 PDT ---
The problem is with "Format". I replaced it with manual string concatenations
and it compiles in just above one second. With "Format" it takes almost four
minutes on my computer.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 01 2012