On Thursday, 18 August 2016 at 06:29:07 UTC, Ali Çehreli wrote:
On 08/17/2016 05:59 PM, Dicebot wrote:
> On 08/18/2016 12:25 AM, Ali Çehreli wrote:
>> I'm wondering whether there is such a thing as single-use of
a type in
>> compiler technology. I think if the compiler could determine
that a type
>> is used only once, it could apply optimizations.
>>
>> A colleague of mine raised the issue of D's use of the GC
even for
>> seemingly local delegates. For example, even though
everything remains
>> local for the following lambda, countAbove() cannot be @nogc:
>>
>> auto countAbove(int[] a, int limit) {
>> return a.filter!(x => x >= limit).count();
>> }
>>
>> The reason is due to the fact that filter() returns a struct
object that
>> takes the delegate as an alias template parameter. Here is a
reduction
>> of the issue with my understanding in comments:
>
> I believe actual reason is that aliased lambda has to
allocate a closure
> because it refers to stack local variable (limit).
Right.
> This compiles just fine:
>
> auto countAbove(int[] a, int limit) @nogc {
> return a.filter!(x => x >= 1).count();
> }
However, as my test code demonstrates, even when the lambda
refers to stack local variable, closure is NOT allocated in the
case of the function call. As far as I can tell, the actual
reason for the allocation is the struct object that filter()
returns.
I am trying to understand why the struct object requires the
closure allocation. I made myself believe that this is the
reason: Being an alias template parameter, the lambda is a part
of the type (the instantiation of the struct template). Even
though the compiler could determine that the single object does
not escape, its type can be used again.
Your main mistake seems to be an expectation of complete flow
analysis in compiler while in fact it is virtually non-existent.
DMD frontend can't prove that references to stack don't escape in
all but most simple cases (where all involved code is fully
inlined and no actual function/struct has to be generated).
For example, in your struct case it can't know that you won't
eventually return that struct instance from function or do
something similar. Such analysis is simply not performed, thus it
has to generate code conservatively. The problem you mention is
likely to be present with current frontend too but that is not a
crucial technical limitation on its own because fully qualified
type of such S instantiation would include function-local context
and compiler can use it to tell that type can be optimized as
function-local unless any references escape.
From my own encounters vast majority of issues of that kind could
be solved by one of two relatively simple solutions:
1) Being able to capture context in lambda by value (Right now I
tend to use custom structs with `opCall` instead of built-in
lambdas for such cases)
2) Allowing compiler to treat `pragma(inline, true)` functions as
ones that never generate own object code and thus can be analyzed
in usage contexts separately.
