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

ag0aep6g@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |performance
                 CC|                            |ag0aep6g@gmail.com
           Hardware|x86_64                      |All
                 OS|Windows                     |All

--- Comment #1 from ag0aep6g@gmail.com ---
A little shell script with a reduced test case:
----
> times
for i in `seq 2 2 60`
do
cat > test.d << code
struct InputPoint
{
    double position;
}
struct GrowableArray
{
    InputPoint[$i*1024] data;
}
code
(echo -n "$i "; time -f %U dmd -c test.d 2>&1) | tee -a times
done
gnuplot -e 'set terminal dumb; plot "times"'
----

Output:
----
2 0.01
4 0.04
6 0.08
8 0.13
10 0.22
12 0.30
14 0.40
16 0.53
18 0.70
20 0.87
22 1.04
24 1.32
26 1.50
28 1.82
30 2.15
32 2.62
34 3.22
36 4.05
38 5.19
40 6.23
42 7.68
44 10.13
46 10.97
48 11.97
50 14.07
52 22.59
54 24.41
56 26.22
58 33.27
60 33.24



  35 ++----------+----------+-----------+-----------+----------+----------++
     +           +          +           +           +       "times"   A  A A
     |                                                                     |
  30 ++                                                                   ++
     |                                                                     |
  25 ++                                                               A   ++
     |                                                              A      |
     |                                                            A        |
  20 ++                                                                   ++
     |                                                                     |
     |                                                                     |
  15 ++                                                        A          ++
     |                                                                     |
     |                                                     A A             |
  10 ++                                                 A                 ++
     |                                                A                    |
   5 ++                                          A  A                     ++
     |                                       A A                           |
     +           +          +  A A A  A A A         +          +           +
   0 ++A--A-A-A--A-A-A--A-A-A-----------+-----------+----------+----------++
     0           10         20          30          40         50          60
----

That looks quadratic. Eww.

--

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

--- Comment #2 from Manu <turkeyman@gmail.com> ---
More amazing that a quadratic increase in compile time as a result of linear
increase in array size, is that script you just produced... that is truly
astonishing!
Seriously, I'm speechless. O_O

--

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

Vladimir Panteleev <thecybershadow@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |thecybershadow@gmail.com
            Summary|Large static arraus seem to |[REG2.064] Large static
                   |lock up DMD                 |arrays seem to lock up DMD
           Severity|normal                      |regression

--- Comment #3 from Vladimir Panteleev <thecybershadow@gmail.com> ---
This is a regression.

Introduced in https://github.com/D-Programming-Language/dmd/pull/2605

--

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

--- Comment #4 from Kenji Hara <k.hara.pg@gmail.com> ---
(In reply to Vladimir Panteleev from comment #3)
> This is a regression.
> 
> Introduced in https://github.com/D-Programming-Language/dmd/pull/2605

The root issue is the inefficiency of 'dt' structure in dmd backend.

Reduced test case:

struct S(T, size_t dim)
{
    T[dim] data;
}
version(OK) alias X = S!(  uint, 128*1024);
version(NG) alias X = S!(double, 128*1024);

If the static array element is zero value (e.g. uint.init), it's handled as "N
zero bytes". If the element value is non-zero (e.g. double.init), it's handled
as 131072 repetition of RealExp.

Therefore, following code also hits the performance issue.

struct S(T, size_t dim)
{
    T[dim] data = 1;  // non-zero elemnet
}
alias X = S!(uint, 128*1024);

--

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

--- Comment #5 from ag0aep6g@gmail.com ---
(In reply to Kenji Hara from comment #4)
> Reduced test case:
> 
> struct S(T, size_t dim)
> {
>     T[dim] data;
> }
> version(OK) alias X = S!(  uint, 128*1024);
> version(NG) alias X = S!(double, 128*1024);

This compiles quickly for me. Only when I wrap T in another struct does it grind to a halt:

----
struct D(T) {T m;}
struct S(T, size_t dim)
{
    D!T[dim] data;
}
version(OK) alias X = S!(  uint, 128*1024);
version(NG) alias X = S!(double, 128*1024);
----

[...]
> Therefore, following code also hits the performance issue.
> 
> struct S(T, size_t dim)
> {
>     T[dim] data = 1;  // non-zero elemnet
> }
> alias X = S!(uint, 128*1024);

Same here. I only see the issue with another struct:

----
struct D(T) {T m = 1; /* non-zero element */}
struct S(T, size_t dim)
{
    D!T[dim] data;
}
alias X = S!(uint, 128*1024);
----

--

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

Walter Bright <bugzilla@digitalmars.com> changed:

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

--- Comment #6 from Walter Bright <bugzilla@digitalmars.com> ---
I'll fix this, but you should know that this necessarily creates large sections in the executable file of repeated data. For such large arrays, it is better to allocate and initialize them on program startup.

The way globals work on modern CPUs is you are not saving any execution time by using static data. Large static arrays is an artifact of FORTRAN.

--

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

--- Comment #7 from Vladimir Panteleev <thecybershadow@gmail.com> ---
(In reply to Walter Bright from comment #6)
> I'll fix this, but you should know that this necessarily creates large sections in the executable file of repeated data. For such large arrays, it is better to allocate and initialize them on program startup.
> 
> The way globals work on modern CPUs is you are not saving any execution time by using static data. Large static arrays is an artifact of FORTRAN.

There are no global variables in the problematic programs given here.

The problem is entirely with .init.

Additionally, dynamic arrays cannot always be used as a drop-in replacement for static arrays. They add one level of indirection and cannot easily be aligned together with other types (as with static arrays in a struct).

(In reply to ag0aep6g from comment #1)
> struct InputPoint
> {
>     double position;
> }

The problem should be avoided if you change the declaration to "double position = 0;"

--

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

--- Comment #8 from Walter Bright <bugzilla@digitalmars.com> ---
https://github.com/D-Programming-Language/dmd/pull/4673

--

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

--- Comment #9 from Walter Bright <bugzilla@digitalmars.com> ---
(In reply to Vladimir Panteleev from comment #7)
> The problem is entirely with .init.

Which is a global variable, and has all the downsides of them. My advice still applies.

> Additionally, dynamic arrays cannot always be used as a drop-in replacement for static arrays. They add one level of indirection and cannot easily be aligned together with other types (as with static arrays in a struct).

Global arrays already have that extra indirection. I'm also hard pressed to see how a large struct is going to suffer from an extra indirection to the array, when it surely is going to suffer much worse from cache invalidation.

> The problem should be avoided if you change the declaration to "double position = 0;"

True, then it goes into the BSS segment, but the other issues still apply that are not fixable by changing the compiler (i.e. executable bloat).

--

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

--- Comment #10 from Walter Bright <bugzilla@digitalmars.com> ---
Essentially, I think you'll find that speed improvements from using very large static arrays are illusory.

I'll still fix the compiler problem, though, just be aware there is no fix for the giant object files and exe files you'll also get.

--