Hi,

While working on a D project which heavily uses the lazy algorithms for ranges I noticed a sudden huge increase in the compilation time and the produced binary size.

I chased down the offending change to just a small change in one line of the code which made the resulting binary to jump from 18MB to over 400MB.

The code that produces the large binary actually failed to link using DMD on osx (works on linux). The link command just consumes all the CPU and never completes. Using LDC on osx just failed to compile. ldc was using all the CPU and never completing.

There is also a very big difference between passing -unittest and not passing it.

I was able to shrink the code down to the following:

import std.range.primitives;
import std.range : chain, choose, repeat, chooseAmong, takeOne;
import std.algorithm.iteration : joiner , map;
import std.range.interfaces : InputRange, inputRangeObject;
import std.conv : text;

struct AType {
   string id;
   Annotation[] annotations;
   TypeArgument[] typeArguments;

}

struct Annotation {
   string type;
}

struct TypeArgument {
   AType refType;
}

struct PrimaryValue {
   int type;
}

struct FieldDecl {
   AType type;
   string id;
   PrimaryValue[] values;
}

struct MethodDecl {
   string name;
   AType returnType;
   FieldDecl[] params;
}

auto toCharsArray(R)(R r, string sep = "\n", string tail = "\n")
         if (isInputRange!R) {
    return choose(r.empty, "", chain(r.joiner(sep), tail));
}


auto toChars(Annotation uda) {
   return chain("@", uda.type);
}

InputRange!(ElementType!string) toChars(TypeArgument ta) {
   auto r = chain("", ta.refType.id);
   with (ta.refType) {
      auto tArgs = choose(typeArguments.empty, "",
                          chain("!(", typeArguments.map!(toChars).joiner(", "), ")"));

      return chain(id, tArgs).inputRangeObject();
   }
}

auto toChars(AType t) {
   auto udas = t.annotations.map!(toChars).toCharsArray();
   auto tArgs = choose(t.typeArguments.empty, "",
                       chain("!(", t.typeArguments.map!(toChars).joiner(", "), ")"));

   return chain(udas, t.id, tArgs);
}

/// PrimaryValue
auto toChars(PrimaryValue pv) {
   return chooseAmong(pv.type, "val", "val");
}

auto toCharsSingleOrArray(R)(R r) if (isInputRange!R) {
   return choose(r.length == 1,
                 r.takeOne.map!(toChars).joiner(),
                 chain("[", r.map!(toChars).joiner(", "), "]")
                 );
}

auto toCharsBare(FieldDecl f) {
   auto def = chain(f.type.toChars, " ", f.id);

   return choose(f.values.empty,
                 def,
                 chain(def, " = ", toCharsSingleOrArray(f.values)));
}

auto toChars(FieldDecl f) {
   return chain("", f.toCharsBare());
}

auto toChars(MethodDecl m) {
   //Just changing the line bellow to have map!(toChars) reduces the binary size
   //to 18MB from 403MB
   auto prms = chain("(", m.params.map!(toCharsBare).toCharsArray(", ", ""), ")");
   return chain(" ", m.name, prms, ";");
}

unittest {
   AType t1 = {id : "Foo"};
   FieldDecl f1 = {type : t1, id : "f1"};

   MethodDecl m1 = {name : "m", returnType : t1 };
   assert(!m1.toChars().text().empty); // removing this line drops the size by half
}

void main() { }

I am compiling this with:

# dmd -g -debug -unittest


I have marked the line that needs to be changed for the code size to drop significantly. What is interesting is that the using toChars should be more complex than using toCharsBare since the former calls the latter but the binary size just explodes when using toCharsBare.

I apologize for the long code segment.

On 05/17/2016 05:44 PM, Georgi D wrote:
> Hi,
>
> While working on a D project which heavily uses the lazy algorithms for
> ranges I noticed a sudden huge increase in the compilation time and the
> produced binary size.
[snip]

Thanks. That's definitely deserving of a bug report. -- Andrei

On Tuesday, 17 May 2016 at 21:58:06 UTC, Andrei Alexandrescu wrote:
> On 05/17/2016 05:44 PM, Georgi D wrote:
>> Hi,
>>
>> While working on a D project which heavily uses the lazy algorithms for
>> ranges I noticed a sudden huge increase in the compilation time and the
>> produced binary size.
> [snip]
>
> Thanks. That's definitely deserving of a bug report. -- Andrei

I'm guessing that is highly related to this one: https://issues.dlang.org/show_bug.cgi?id=15831

On Tuesday, 17 May 2016 at 21:58:06 UTC, Andrei Alexandrescu wrote:
> On 05/17/2016 05:44 PM, Georgi D wrote:
>> Hi,
>>
>> While working on a D project which heavily uses the lazy algorithms for
>> ranges I noticed a sudden huge increase in the compilation time and the
>> produced binary size.
> [snip]
>
> Thanks. That's definitely deserving of a bug report. -- Andrei

I have file bug: https://issues.dlang.org/show_bug.cgi?id=16039

On 5/17/16 6:04 PM, ZombineDev wrote:
> On Tuesday, 17 May 2016 at 21:58:06 UTC, Andrei Alexandrescu wrote:
>> On 05/17/2016 05:44 PM, Georgi D wrote:
>>> Hi,
>>>
>>> While working on a D project which heavily uses the lazy algorithms for
>>> ranges I noticed a sudden huge increase in the compilation time and the
>>> produced binary size.
>> [snip]
>>
>> Thanks. That's definitely deserving of a bug report. -- Andrei
>
> I'm guessing that is highly related to this one:
> https://issues.dlang.org/show_bug.cgi?id=15831

Yep. chain uses voldemort type, map does not.

Georgi: try copying chain implementation into your local file, but instead of having a static internal struct, move it to a module-level struct (you probably have to repeat the template parameters, but not the constraints). See if it produces a similar slimming effect.

-Steve

On 05/19/2016 08:38 AM, Steven Schveighoffer wrote:
> Yep. chain uses voldemort type, map does not.

We definitely need to fix Voldemort types. Walter and I bounced a few ideas during DConf.

1. Do the cleartext/compress/hash troika everywhere (currently we do it on Windows). That should help in several places.

2. For Voldemort types, simply generate a GUID-style random string of e.g. 64 bytes. Currently the name of the type is composed out of its full scope, with some exponentially-increasing repetition of substrings. That would compress well, but it's just a lot of work to produce and then compress the name. A random string is cheap to produce and adequate for Voldemort types (you don't care for their name anyway... Voldemort... get it?).

I very much advocate slapping a 64-long random string for all Voldermort returns and calling it a day. I bet Liran's code will get a lot quicker to build and smaller to boot.


Andrei

On 5/19/16 9:45 AM, Andrei Alexandrescu wrote:
> On 05/19/2016 08:38 AM, Steven Schveighoffer wrote:
>> Yep. chain uses voldemort type, map does not.
>
> We definitely need to fix Voldemort types. Walter and I bounced a few
> ideas during DConf.
>
> 1. Do the cleartext/compress/hash troika everywhere (currently we do it
> on Windows). That should help in several places.
>
> 2. For Voldemort types, simply generate a GUID-style random string of
> e.g. 64 bytes. Currently the name of the type is composed out of its
> full scope, with some exponentially-increasing repetition of substrings.
> That would compress well, but it's just a lot of work to produce and
> then compress the name. A random string is cheap to produce and adequate
> for Voldemort types (you don't care for their name anyway...
> Voldemort... get it?).
>
> I very much advocate slapping a 64-long random string for all Voldermort
> returns and calling it a day. I bet Liran's code will get a lot quicker
> to build and smaller to boot.

This may be crazy, but I solved this problem by simply moving the struct outside the function. What about a lowering that does this for you?

Example:

auto foo(T)(T t) if (someConstraints)
{
   static struct Result
   {
      T t;
   }
   return Result(t);
}

Changes to:

private struct foo_Result(T) if (someConstraints)
{
   T t;
}

auto foo(T)(T t) if (someConstraints)
{
   alias Result = foo_Result!T // inserted by compiler
   return Result(t);
}

Or even better:

template(T) foo if (someConstraints)
{
   struct Result
   {
      T t;
   }

   auto foo(T t)
   {
      return Result(t);
   }
}

What this does is lower the number of times the template parameters (and function arguments) appears in the type name to 1. This gets rid of the exponential nature of the symbol name.

This doesn't work for voldemorts with closures, but maybe it can somehow be reconstructed so the context is included in the generated struct.

-Steve

On 05/19/2016 10:43 AM, Steven Schveighoffer wrote:
> This may be crazy, but I solved this problem by simply moving the struct
> outside the function. What about a lowering that does this for you?

That's also a possibility, but likely a more complicated one. -- Andrei

On 20/05/2016 12:44 AM, Andrei Alexandrescu wrote:
> On 05/19/2016 10:43 AM, Steven Schveighoffer wrote:
>> This may be crazy, but I solved this problem by simply moving the struct
>> outside the function. What about a lowering that does this for you?
>
> That's also a possibility, but likely a more complicated one. -- Andrei

We don't actually need to lower it, just mangle it as if it was lowered.

On 5/19/16 10:56 AM, Daniel Murphy wrote:
> On 20/05/2016 12:44 AM, Andrei Alexandrescu wrote:
>> On 05/19/2016 10:43 AM, Steven Schveighoffer wrote:
>>> This may be crazy, but I solved this problem by simply moving the struct
>>> outside the function. What about a lowering that does this for you?
>>
>> That's also a possibility, but likely a more complicated one. -- Andrei
>
> We don't actually need to lower it, just mangle it as if it was lowered.

Noice! -- Andrei