www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Delegate Literals + Immutability, pure and closures

reply dsimcha <dsimcha yahoo.com> writes:
Immutability and type propagation are two of D's greatest assets.  Below is an
example of where they would be difficult to take advantage of:

int foo;
if( bar < 3) {
    try {
        foo = doStuff(someOtherStackVariables);
    } catch(SomeException) {
        foo = 666;
    }
} else {
    foo = 4;
}

I've recently discovered this pattern to allow use of type propagation and
immutability in these situations with no extra boilerplate:

immutable foo = {
    if( bar < 3) {
        try {
            return doStuff(someOtherStackVariables);
        } catch(SomeException) {
            return 666;
        }
    } else {
        return 4;
    }
}();

This allows me to make foo immutable and have its type inferred while avoiding
any boilerplate code, but has four problems:

1.  It allocates a closure.  Therefore, it can't be used in
performance-critical code.  We really need to optimize away closure allocation
in trivial cases where the function pointer obviously can't escape, to make
delegate literals more useful in performance-critical code.

2.  Delegate literals can't be inlined in even the most trivial cases.  This
is less severe than (1), and probably would almost never have a non-negligible
impact in practice, though.

3.  A function that uses a delegate literal can't be pure because purity is
not inferred for delegate literals:

void main() {
    foo();
}

void foo() pure {
    int z;
    int i = {return z + 1;}();
}

Error: pure function 'foo' cannot call impure delegate '__dgliteral1'

4.  Auto return type inference is limited to cases where all return statements
return the exact type.  Is there any reason I'm missing why, if multiple
return statements with different types are present, an auto return function
couldn't just return a common type?
Sep 29 2011
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 29 Sep 2011 16:32:45 -0400, dsimcha <dsimcha yahoo.com> wrote:

 Immutability and type propagation are two of D's greatest assets.  Below  
 is an
 example of where they would be difficult to take advantage of:

 int foo;
 if( bar < 3) {
     try {
         foo = doStuff(someOtherStackVariables);
     } catch(SomeException) {
         foo = 666;
     }
 } else {
     foo = 4;
 }

 I've recently discovered this pattern to allow use of type propagation  
 and
 immutability in these situations with no extra boilerplate:

 immutable foo = {
     if( bar < 3) {
         try {
             return doStuff(someOtherStackVariables);
         } catch(SomeException) {
             return 666;
         }
     } else {
         return 4;
     }
 }();

 This allows me to make foo immutable and have its type inferred while  
 avoiding
 any boilerplate code, but has four problems:

 1.  It allocates a closure.  Therefore, it can't be used in
 performance-critical code.  We really need to optimize away closure  
 allocation
 in trivial cases where the function pointer obviously can't escape, to  
 make
 delegate literals more useful in performance-critical code.

 2.  Delegate literals can't be inlined in even the most trivial cases.   
 This
 is less severe than (1), and probably would almost never have a  
 non-negligible
 impact in practice, though.

 3.  A function that uses a delegate literal can't be pure because purity  
 is
 not inferred for delegate literals:

 void main() {
     foo();
 }

 void foo() pure {
     int z;
     int i = {return z + 1;}();
 }

 Error: pure function 'foo' cannot call impure delegate '__dgliteral1'

 4.  Auto return type inference is limited to cases where all return  
 statements
 return the exact type.  Is there any reason I'm missing why, if multiple
 return statements with different types are present, an auto return  
 function
 couldn't just return a common type?

+1 on all 4 issues. Note that there is a workaround for 1: DT noclosure(DT)(scope DT d) if(is(DT == delegate)) { return d; } Also note that next to memory allocation, lack of inlining is the biggest performance problem. It's not negligible (in case that is what you were saying, hard to tell from all the negatives ;) -Steve
Sep 29 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article
 Note that there is a workaround for 1:
 DT noclosure(DT)(scope DT d) if(is(DT == delegate))
 {
    return d;
 }

I know, but this defeats the nice zero-boilerplate solution to getting type inference and immutability when you want to conditionally assign one of several values to a variable.
 Also note that next to memory allocation, lack of inlining is the biggest
 performance problem.  It's not negligible (in case that is what you were
 saying, hard to tell from all the negatives ;)

Clarification: I didn't mean lack of inlining is negligible in general, only for this use case. If you have a bunch of complicated conditions and whatnot in the function body then the extra 5 clock cycles or so for a function call probably don't mean much
Sep 29 2011
parent David Nadlinger <see klickverbot.at> writes:
On 9/29/11 11:03 PM, dsimcha wrote:
 == Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article
 Note that there is a workaround for 1:
 DT noclosure(DT)(scope DT d) if(is(DT == delegate))
 {
     return d;
 }

I know, but this defeats the nice zero-boilerplate solution to getting type inference and immutability when you want to conditionally assign one of several values to a variable.

Does this actually work with DMD? Last time I tested (some weeks ago), this worked as intended with LDC, but DMD still allocated a heap copy of the stack frame. I don't remember the details, and unfortunately, I didn't keep a copy of the test case, but it was something like »int foo(scope int delegate() dg) { return dg(); } int main() { int a = 42; return foo({ return a; }); }«. David
Sep 29 2011
prev sibling next sibling parent reply David Nadlinger <see klickverbot.at> writes:
On 9/29/11 10:32 PM, dsimcha wrote:
 I've recently discovered this pattern to allow use of type propagation and
 immutability in these situations with no extra boilerplate:

Yes, this pattern is very useful indeed, I also often use a similar solution for generating code for string mixins on the fly. Do we already have a name for it, by the way? I like to call it »IEDL for »Immediately Executed/Evaluated Delegate Literal«, but that's probably just me.
 1.  It allocates a closure.  Therefore, it can't be used in
 performance-critical code.  We really need to optimize away closure allocation
 in trivial cases where the function pointer obviously can't escape, to make
 delegate literals more useful in performance-critical code.

Definitely +1 for this, function/delegate literals are so useful in D that I think making them as efficient as possible should be high on our list. »Demoting« delegate literals that don't need to access the scope to function literals (as described by TDPL, don't have the issue number handy right now) would be a first step, and avoiding to unnecessarily copy frames to the heap as second, but this could turn out to be quite tricky.
 2.  Delegate literals can't be inlined in even the most trivial cases.  This
 is less severe than (1), and probably would almost never have a non-negligible
 impact in practice, though.

I'd also very much like to see improvements on this front – contrary to what you said (if I got all that negations right), it does have a prohibitively large performance impact in some of my applications. However, I'm not quite sure how hard it would be to implement a solution, since inlining happens nowhere near constant folding, afaik.
 3.  A function that uses a delegate literal can't be pure because purity is
 not inferred for delegate literals:
 […]
 4.  Auto return type inference is limited to cases where all return statements
 return the exact type.  Is there any reason I'm missing why, if multiple
 return statements with different types are present, an auto return function
 couldn't just return a common type?

+1 for these as well, should be fairly easy to pull off. David
Sep 29 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/29/2011 5:06 PM, David Nadlinger wrote:
 Yes, this pattern is very useful indeed, I also often use a similar
 solution for generating code for string mixins on the fly. Do we already
 have a name for it, by the way? I like to call it »IEDL for »Immediately
 Executed/Evaluated Delegate Literal«, but that's probably just me.

No previously chosen name that I know of, but I like your name. Anyhow, I'm impressed/pleasantly surprised. I didn't realize an IEDL could be executed at compile time to produce a mixin string. If IEDLs are that universally useful, then they definitely deserve some special case performance optimizations, i.e. inlining and avoiding heap allocations. Does anyone else have any interesting use cases for them?
Sep 29 2011
parent reply Don <nospam nospam.com> writes:
On 30.09.2011 02:32, dsimcha wrote:
 On 9/29/2011 5:06 PM, David Nadlinger wrote:
 Yes, this pattern is very useful indeed, I also often use a similar
 solution for generating code for string mixins on the fly. Do we already
 have a name for it, by the way? I like to call it »IEDL for »Immediately
 Executed/Evaluated Delegate Literal«, but that's probably just me.

No previously chosen name that I know of, but I like your name. Anyhow, I'm impressed/pleasantly surprised. I didn't realize an IEDL could be executed at compile time to produce a mixin string. If IEDLs are that universally useful, then they definitely deserve some special case performance optimizations, i.e. inlining and avoiding heap allocations. Does anyone else have any interesting use cases for them?

I use them everywhere in the test suite. They behave a lot like comma expressions (in that they allow you to put multiple expressions in a place where you'd normally only be able to have one) but they allow statements and declarations as well as expressions. This makes them extremely useful in metaprogramming.
Sep 29 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/30/2011 08:06 AM, Don wrote:
 On 30.09.2011 02:32, dsimcha wrote:
 On 9/29/2011 5:06 PM, David Nadlinger wrote:
 Yes, this pattern is very useful indeed, I also often use a similar
 solution for generating code for string mixins on the fly. Do we already
 have a name for it, by the way? I like to call it »IEDL for »Immediately
 Executed/Evaluated Delegate Literal«, but that's probably just me.

No previously chosen name that I know of, but I like your name. Anyhow, I'm impressed/pleasantly surprised. I didn't realize an IEDL could be executed at compile time to produce a mixin string. If IEDLs are that universally useful, then they definitely deserve some special case performance optimizations, i.e. inlining and avoiding heap allocations. Does anyone else have any interesting use cases for them?

I use them everywhere in the test suite. They behave a lot like comma expressions (in that they allow you to put multiple expressions in a place where you'd normally only be able to have one) but they allow statements and declarations as well as expressions. This makes them extremely useful in metaprogramming.

They will be if they are inlined. How about not only allow the compiler to inline the immediately executed delegate literals, but to even _enforce_ that every single one of them is inlined?
Oct 01 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 29 Sep 2011 17:03:26 -0400, dsimcha <dsimcha yahoo.com> wrote:

 == Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article

 Also note that next to memory allocation, lack of inlining is the  
 biggest
 performance problem.  It's not negligible (in case that is what you were
 saying, hard to tell from all the negatives ;)

Clarification: I didn't mean lack of inlining is negligible in general, only for this use case. If you have a bunch of complicated conditions and whatnot in the function body then the extra 5 clock cycles or so for a function call probably don't mean much

It's more of a gut feeling/anecdotal evidence that I have about inlining. I've seen inlining cut the runtime of a function significantly. A good example, for my std.stdio rewrite, there's one point where I'm converting char/wchar to dchar, then to the appropriate width. At first, I just copied the current std.stdio's policy of: foreach(dchar d; str) Which is never inlined since it calls an opApply-style runtime function. but then I added an option to do this inline. Probably cut the execution time by 40% or more. -Steve
Sep 29 2011
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2011-09-29 22:32, dsimcha wrote:
 Immutability and type propagation are two of D's greatest assets.  Below is an
 example of where they would be difficult to take advantage of:

 int foo;
 if( bar<  3) {
      try {
          foo = doStuff(someOtherStackVariables);
      } catch(SomeException) {
          foo = 666;
      }
 } else {
      foo = 4;
 }

 I've recently discovered this pattern to allow use of type propagation and
 immutability in these situations with no extra boilerplate:

 immutable foo = {
      if( bar<  3) {
          try {
              return doStuff(someOtherStackVariables);
          } catch(SomeException) {
              return 666;
          }
      } else {
          return 4;
      }
 }();

First, that looks like JavaScript. Second, yet another reason to have a short lambda syntax with auto return. -- /Jacob Carlborg
Sep 29 2011
prev sibling parent reply travert phare.normalesup.org (Christophe) writes:
dsimcha , dans le message (digitalmars.D:145792), a écrit :
 4.  Auto return type inference is limited to cases where all return statements
 return the exact type.  Is there any reason I'm missing why, if multiple
 return statements with different types are present, an auto return function
 couldn't just return a common type?

If the common type is obvious, the programmer can just type it. If not, I do not want to rely on the compiler to perform implicit casting to a type that I don't even know, and where I might loose informations, unless there is an unambiguous and error-free way to determine the comon type. I prefer the compiler to complain about an ill-defined return type than a compiler making uncontrolled casting to a type I don't even know. If auto return type has to be improved, it must be using a very safe and clearly defined behavior. About other points, of course, the compiler should optimize out all heap allocation when it knows the data do not escape the scope (there is delegate, but I think also initializer lists), and it should also be able to inline obvious delegates. I guess that will come in time. On that matter, I regret that the scope attribute is meant to disappear. It could be a way for the compiler to enforce that the data do not escape the scope, so the programer can be sure the compiler will be able to perform this kind of optimization (and not only for delegates) - just like pure and immutable enforce behaviors than enable more optimizations. -- Christophe
Sep 30 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/30/2011 9:01 AM, Christophe wrote:
 If the common type is obvious, the programmer can just type it.

What if it's ridiculously long and verbose?
 If not,
 I do not want to rely on the compiler to perform implicit casting to a
 type that I don't even know, and where I might loose informations,
 unless there is an unambiguous and error-free way to determine the comon
 type. I prefer the compiler to complain about an ill-defined return type
 than a compiler making uncontrolled casting to a type I don't even know.
 If auto return type has to be improved, it must be using a very safe and
 clearly defined behavior.

I was thinking it would work the same way as the ?: operator does.
Sep 30 2011
parent travert phare.normalesup.org (Christophe) writes:
dsimcha , dans le message (digitalmars.D:145820), a écrit :
 I was thinking it would work the same way as the ?: operator does.

I can believe that the way ?: work is appropriate to infer types of function with multiple return, but the documentation of ?: is not clear about what it does... http://www.d-programming-language.org/expression.html#ConditionalExpression
Sep 30 2011