digitalmars.D - Compiler analysis of single-use types? Escape analysis of types?
- =?UTF-8?Q?Ali_=c3=87ehreli?= (44/44) Aug 17 2016 I'm wondering whether there is such a thing as single-use of a type in
-
Dicebot
(18/33)
Aug 17 2016
From: Dicebot
- Yuxuan Shui (2/10) Aug 17 2016 I wish we could have something like "scoped" delegates...
- Jacob Carlborg (9/10) Aug 18 2016 You mean:
- Yuxuan Shui (7/15) Aug 18 2016 Delegates are pretty much a struct that holds references, right?
- =?UTF-8?Q?Ali_=c3=87ehreli?= (19/41) Aug 17 2016 However, as my test code demonstrates, even when the lambda refers to
- Dicebot (23/67) Aug 18 2016 Your main mistake seems to be an expectation of complete flow
- Meta (5/60) Aug 17 2016 If I understand correctly, this is exactly what linear types are
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: void foo(alias dg)() { dg(); } struct S(alias dg) { void bar() { dg(); } } void main() { int i; /* The following call can be marked as nogc because foo() does * not escape the delegate. (It can indeed appear in nogc * code today.) */ foo!(() => i)(); /* The following expression does not escape the delegate * either. (Note that object 's' is not escaped.) So, one would * expect the following code be nogc as well. However, 2.071 does * allocate from the GC. */ S!(() => i) s; /* Although one would expect that last line above to be nogc as * well, I can see one potential issue there that warrants the GC * use: Although no reference to the local 'i' is escaped, the * *type* of 's' can be obtained perhaps by typeof() to make * another object of the same type, which may be escaped. */ typeof(s) s2; /* s2 carries another alias to local 'i' through its *type*! */ } If the compiler could see that 's' is not escaped *and* it's type is used only once, then the expression with the second lambda could be nogc as well. Does that make sense? Is there such a thing? Thank you, Ali
Aug 17 2016
From: Dicebot <public dicebot.lv> Newsgroups: d,i,g,i,t,a,l,m,a,r,s,.,D Subject: Re: Compiler analysis of single-use types? Escape analysis of types? References: <np2knd$1r3k$1 digitalmars.com> In-Reply-To: <np2knd$1r3k$1 digitalmars.com> --exJMXgDSegalDuQD3tWEt3K9c6PRATIk5 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 08/18/2016 12:25 AM, Ali =C3=87ehreli 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 typ=eis used only once, it could apply optimizations. =20 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: =20 auto countAbove(int[] a, int limit) { return a.filter!(x =3D> x >=3D limit).count(); } =20 The reason is due to the fact that filter() returns a struct object tha=ttakes 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). This compiles just fin= e: auto countAbove(int[] a, int limit) nogc { return a.filter!(x =3D> x >=3D 1).count(); } --exJMXgDSegalDuQD3tWEt3K9c6PRATIk5--
Aug 17 2016
On Thursday, 18 August 2016 at 00:59:43 UTC, Dicebot wrote:On 08/18/2016 12:25 AM, Ali Çehreli wrote:I wish we could have something like "scoped" delegates...[...]I believe actual reason is that aliased lambda has to allocate a closure because it refers to stack local variable (limit). This compiles just fine: auto countAbove(int[] a, int limit) nogc { return a.filter!(x => x >= 1).count(); }
Aug 17 2016
On 2016-08-18 03:21, Yuxuan Shui wrote:I wish we could have something like "scoped" delegates...You mean: void foo(scope void delegate() dg); Or: void bar(void delegate() dg); scope void delegate() a = {}; bar(a); -- /Jacob Carlborg
Aug 18 2016
On Thursday, 18 August 2016 at 07:04:41 UTC, Jacob Carlborg wrote:On 2016-08-18 03:21, Yuxuan Shui wrote:Delegates are pretty much a struct that holds references, right? So they are kinda like pointers. I wish I can enforce scope rules (DIP1000) on them. For example, scope delegate should not be able to hold reference to variables with shorter lifetime than the delegate itself. With this we then could have delegates in nogc code.I wish we could have something like "scoped" delegates...You mean: void foo(scope void delegate() dg); Or: void bar(void delegate() dg); scope void delegate() a = {}; bar(a);
Aug 18 2016
On 08/17/2016 05:59 PM, Dicebot wrote:On 08/18/2016 12:25 AM, Ali Çehreli wrote:Right.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).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. I'm wondering whether that's the reason. If so, the compiler could prove that the type is used only once and not allocate the closure. Note that although they look the same to us, S!(() => i) and S!(() => i) are different types to the compiler because the two lambdas are different anonymous objects, effectively making the struct template instances different. Ali
Aug 17 2016
On Thursday, 18 August 2016 at 06:29:07 UTC, Ali Çehreli wrote:On 08/17/2016 05:59 PM, Dicebot wrote: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.On 08/18/2016 12:25 AM, Ali Çehreli wrote:a type inI'm wondering whether there is such a thing as single-use ofthat a typecompiler technology. I think if the compiler could determineeven foris used only once, it could apply optimizations. A colleague of mine raised the issue of D's use of the GCeverything remainsseemingly local delegates. For example, even thoughobject thatlocal 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 structreductiontakes the delegate as an alias template parameter. Here is aallocate a closureof the issue with my understanding in comments:I believe actual reason is that aliased lambda has tobecause 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.
Aug 18 2016
On Wednesday, 17 August 2016 at 21:25:00 UTC, 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: void foo(alias dg)() { dg(); } struct S(alias dg) { void bar() { dg(); } } void main() { int i; /* The following call can be marked as nogc because foo() does * not escape the delegate. (It can indeed appear in nogc * code today.) */ foo!(() => i)(); /* The following expression does not escape the delegate * either. (Note that object 's' is not escaped.) So, one would * expect the following code be nogc as well. However, 2.071 does * allocate from the GC. */ S!(() => i) s; /* Although one would expect that last line above to be nogc as * well, I can see one potential issue there that warrants the GC * use: Although no reference to the local 'i' is escaped, the * *type* of 's' can be obtained perhaps by typeof() to make * another object of the same type, which may be escaped. */ typeof(s) s2; /* s2 carries another alias to local 'i' through its *type*! */ } If the compiler could see that 's' is not escaped *and* it's type is used only once, then the expression with the second lambda could be nogc as well. Does that make sense? Is there such a thing? Thank you, AliIf I understand correctly, this is exactly what linear types are (i.e., what Rust uses... or maybe that was affine types, which are similar). D actually does have fairly primitive support for affine types with ` disable this()`, opAssign and `this (this)`.
Aug 17 2016