www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8449] New: Large array literals take a _very_ long time to compile; they do not scale at all

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

           Summary: Large array literals take a _very_ long time to
                    compile; they do not scale at all
           Product: D
           Version: unspecified
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: jmdavisProg gmx.com



PDT ---
The attached program has an array literal in it which is 193,723 elements long
- 12,108 lines with 16 elements per line. It takes over 40 minutes to compile.
With g++ (so, C++, not D) it takes a little over half a second for the same
array literal. If I reduce the number of lines, I see compilation times like
this:

100 lines
---------
real    0m0.585s
user    0m0.447s
sys     0m0.107s

500 lines
---------
real    0m2.431s
user    0m2.333s
sys     0m0.083s

1000 lines
----------
real    0m9.660s
user    0m9.553s
sys     0m0.080s

2000 lines
----------
real    0m59.291s
user    0m59.009s
sys     0m0.120s

3000 lines
----------
real    2m24.773s
user    2m24.277s
sys     0m0.133s

4000 lines
----------
real    4m36.067s
user    4m35.099s
sys     0m0.190s

5000 lines
----------
real    7m24.430s
user    7m23.104s
sys     0m0.183s

6000 lines
----------
real    10m33.774s
user    10m31.849s
sys     0m0.337s

12,108 lines
----------
real    42m38.483s
user    42m32.010s
sys     0m0.257s

At 100 lines (1600 elements), it does approximately 171 lines per second and
2735 elements per second. At 1000, it's 104 lines / 1656 elements, which is
about 60% as fast. At 2000, it's only 34 lines / 540 elements, which is 3 times
worse than 1000. At the full 12,108 lines, it's less than 5 lines / 76 elements
a second.

Clearly, whatever algorithm that dmd is using does not scale at all. It's at
least one order of magnitude worse, if not several, than what gcc manages (it's
been a while since I had to determine complexity from numbers rather than the
code, so I'm not quite sure what it comes out to - probably something like
n^2).

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




PDT ---
Created an attachment (id=1126)
File with long array literal and takes 40+ minutes to compile

It looks like the file was too large by a couple hundred K, so here it is
compressed.

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


Jonathan M Davis <jmdavisProg gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------

        is obsolete|                            |



PDT ---
Created an attachment (id=1127)
File with long array literal and takes 40+ minutes to compile

There was no reason to tar it since it's only one file, so here it is again
just compressed.

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


Leandro Lucarella <leandro.lucarella sociomantic.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |leandro.lucarella sociomant
                   |                            |ic.com



2013-08-14 04:30:19 PDT ---
Maybe you can try DMD with this applied (latest master), to see if this problem
is fixed too: https://github.com/D-Programming-Language/dmd/pull/2388

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