Denis Koroskin wrote:

> On Sat, 25 Oct 2008 18:36:27 +0400, Lars Ivar Igesund <larsivar@igesund.net> wrote:
> 
>> Bill Baxter wrote:
>>
>>> On Sat, Oct 25, 2008 at 5:24 PM, Jason House <jason.james.house@gmail.com> wrote:
>>>> bearophile Wrote:
>>>>
>>>>> Jason House:
>>>>> > The following spends 90% of its time in _d_alloc_memory
>>>>> > void bar(lazy int i){}
>>>>> > void foo(int i){ bar(i); }
>>>>> > void main(){ foreach(int i; 1..1000000) foo(i); }
>>>>> > Compiling with -O -release reduces it to 88% :)
>>>>>
>>>>> I see. So I presume it becomes quite difficult for D2 to compute up to
>>>>> the 25th term of this sequence (the D code is in the middle of the
>>>>> page)
>>>>> (it takes just few seconds to run on D1):
>>>>> http://en.wikipedia.org/wiki/Man_or_boy_test
>>>>>
>>>>> What syntax can we use to avoid heap allocation? Few ideas:
>>>>>
>>>>> void bar(lazy int i){} // like D1
>>>>> void bar(scope lazy int i){} // like D1
>>>>> void bar(closure int i){} // like current D2
>>>
>>> This makes no sense because the writer of bar has no idea whether the caller will need a heap allocation or not.
>>>
>>>> I would assume a fix would be to add scope to input delegates and to require some kind of declaration on the caller's side when the compiler can't prove safety. It's best for ambiguous cases to be a warning (error). It also makes the code easier for readers to follow.
>>>
>>> I think for a language like D,  hidden, hard to find memory allocations like the one Andrei didn't know he was doing should be eliminated.  By that I mean stack allocation (D1 behavior) should be the default.  Then for places where you really want a closure, some other syntax should be chosen.  The other reason I say that is that so far in D I've only very seldom really wanted an allocated closure.  So I think I will have to use the funky no-closure-please syntax way more than I would have to use a make-me-a-closure-please syntax.
>>
>> I agree that D1 behaviour should be the default, since otherwise it'll be
>> yet another breaking change. However, I do understand that the D1
>> behaviour
>> is the unsafe one, and as such the heap allocated version has merit as
>> the
>> default.
>>
> 
> I believe the default should be the one that is most frequently used, even if it is less safe. Otherwise you may end up with a lot of code duplication.
> 
> I also think that scope and heap-allocated delegates should have different types so that no imlicit casting from scope delegate to heap one would be possible. In this case callee function that recieves the delegate might demand the delegate to be heap-allocated (because it stores it, for example).

I definately agree with this.

-- 
Lars Ivar Igesund
blog at http://larsivi.net
DSource, #d.tango & #D: larsivi
Dancing the Tango

On Sat, Oct 25, 2008 at 10:44 AM, Denis Koroskin <2korden@gmail.com> wrote:
> I also think that scope and heap-allocated delegates should have different types so that no imlicit casting from scope delegate to heap one would be possible. In this case callee function that recieves the delegate might demand the delegate to be heap-allocated (because it stores it, for example).

Fantastic.  That also neatly solves the "returning a delegate" problem; it simply becomes illegal to return a scope delegate.

> On Sat, Oct 25, 2008 at 10:44 AM, Denis Koroskin <2korden@gmail.com> wrote:
>> I also think that scope and heap-allocated delegates should have different
>> types so that no imlicit casting from scope delegate to heap one would be
>> possible. In this case callee function that recieves the delegate might
>> demand the delegate to be heap-allocated (because it stores it, for
>> example).

How would this work? For example:
-----
struct Struct {
    // fields...

    void foo() {
        // body
    }
}

void bar(Struct* p) {
    auto dg = &p.foo;	// stack-based or heap-based delegate?
    // do stuff with dg
}
-----
?
(There's no way to know if *p is a heap-based or stack-based struct)

Jarrett Billingsley wrote:
> Fantastic.  That also neatly solves the "returning a delegate"
> problem; it simply becomes illegal to return a scope delegate.

Even if "scope delegate" becomes a different type, sometimes such a "scope delegate"s is perfectly safe to return:
-----
alias scope void delegate() dg;
Dg foo(Dg dg) {
    return dg;	// Why would this be illegal?
}
-----

On Sat, 25 Oct 2008 21:17:34 +0400, Frits van Bommel <fvbommel@remwovexcapss.nl> wrote:

>> On Sat, Oct 25, 2008 at 10:44 AM, Denis Koroskin <2korden@gmail.com> wrote:
>>> I also think that scope and heap-allocated delegates should have different
>>> types so that no imlicit casting from scope delegate to heap one would be
>>> possible. In this case callee function that recieves the delegate might
>>> demand the delegate to be heap-allocated (because it stores it, for
>>> example).
>
> How would this work? For example:
> -----
> struct Struct {
>      // fields...
>
>      void foo() {
>          // body
>      }
> }
>
> void bar(Struct* p) {
>      auto dg = &p.foo;	// stack-based or heap-based delegate?
>      // do stuff with dg
> }
> -----
> ?

Good question! First, let's expand the code:

void bar(Struct* p) {

    void delegate() dg;

    dg.ptr = p;
    dg.funcptr = &Struct.foo;

    // do stuff with dg
}

So, here is the question: is this a "stack-based or heap-based delegate?" I.e. may we return it from function and pass it to those functions that need heap-base delegate or not?

Yes, we may return it, obviously, and call outside of the function, so from this point of view it is indeed "heap-allocated delegate" even if nothing is actually allocated. But someone might say that it is unsafe to call this dg because at some point object may become inexistant. To respond this, let's rewrite the code to make it trully heap-allocated and compare if it got any safer:

void bar(Struct* p)
{
    void foo()
    {
        p.foo();
    }

    auto dg = &foo;
}

Now dg is heap-allocated (in the sense that place for its local variable are allocated on heap). May we return this delegate from function? Yes. Is it any safer? No. They are absolutely the same.

>      auto dg = &p.foo;	// stack-based or heap-based delegate?

Heap-based one, even if no actual allocation took place.

On Sat, Oct 25, 2008 at 1:17 PM, Frits van Bommel <fvbommel@remwovexcapss.nl> wrote:
>> Fantastic.  That also neatly solves the "returning a delegate" problem; it simply becomes illegal to return a scope delegate.
>
> Even if "scope delegate" becomes a different type, sometimes such a "scope delegate"s is perfectly safe to return:
> -----
> alias scope void delegate() dg;
> Dg foo(Dg dg) {
>    return dg;  // Why would this be illegal?
> }
> -----
>

Clarification - it would be an error to return a scope delegate from the scope in which it was declared.

Currently the behavior you mention (passing a scope delegate into a function then returning it) doesn't even exist for scope classes - parameters cannot be "scope".  I would imagine, though, that if a parameter were scope, a function would be able to return that parameter, and in fact that would be the only way to return a scope reference (delegate or class) from a function.

"Denis Koroskin" wrote
> On Sat, 25 Oct 2008 18:36:27 +0400, Lars Ivar Igesund <larsivar@igesund.net> wrote:
>
>> Bill Baxter wrote:
>>
>>> On Sat, Oct 25, 2008 at 5:24 PM, Jason House <jason.james.house@gmail.com> wrote:
>>>> bearophile Wrote:
>>>>
>>>>> Jason House:
>>>>> > The following spends 90% of its time in _d_alloc_memory
>>>>> > void bar(lazy int i){}
>>>>> > void foo(int i){ bar(i); }
>>>>> > void main(){ foreach(int i; 1..1000000) foo(i); }
>>>>> > Compiling with -O -release reduces it to 88% :)
>>>>>
>>>>> I see. So I presume it becomes quite difficult for D2 to compute up to
>>>>> the 25th term of this sequence (the D code is in the middle of the
>>>>> page)
>>>>> (it takes just few seconds to run on D1):
>>>>> http://en.wikipedia.org/wiki/Man_or_boy_test
>>>>>
>>>>> What syntax can we use to avoid heap allocation? Few ideas:
>>>>>
>>>>> void bar(lazy int i){} // like D1
>>>>> void bar(scope lazy int i){} // like D1
>>>>> void bar(closure int i){} // like current D2
>>>
>>> This makes no sense because the writer of bar has no idea whether the caller will need a heap allocation or not.
>>>
>>>> I would assume a fix would be to add scope to input delegates and to require some kind of declaration on the caller's side when the compiler can't prove safety. It's best for ambiguous cases to be a warning (error). It also makes the code easier for readers to follow.
>>>
>>> I think for a language like D,  hidden, hard to find memory allocations like the one Andrei didn't know he was doing should be eliminated.  By that I mean stack allocation (D1 behavior) should be the default.  Then for places where you really want a closure, some other syntax should be chosen.  The other reason I say that is that so far in D I've only very seldom really wanted an allocated closure.  So I think I will have to use the funky no-closure-please syntax way more than I would have to use a make-me-a-closure-please syntax.
>>
>> I agree that D1 behaviour should be the default, since otherwise it'll be
>> yet another breaking change. However, I do understand that the D1
>> behaviour
>> is the unsafe one, and as such the heap allocated version has merit as
>> the
>> default.
>>
>
> I believe the default should be the one that is most frequently used, even if it is less safe. Otherwise you may end up with a lot of code duplication.
>
> I also think that scope and heap-allocated delegates should have different types so that no imlicit casting from scope delegate to heap one would be possible. In this case callee function that recieves the delegate might demand the delegate to be heap-allocated (because it stores it, for example).

I've been thinking about this solution, and I think the decision to allocate scope or heap should be left up to the developer, and no types should be assigned.

Think about an example like this:

class DelegateCaller
{
   private delegate int _foo();
   this(int delegate() foo) { _foo = foo; }
   int callit() { return _foo();}
}

int f1()
{
    int x() { return 5; }
    scope dc = new DelegateCaller(&x); // allocate on stack
    return dc.callit() * dc.callit();
}

DelegateCaller f2()
{
   int x() { return 5;}
   return new DelegateCaller(&x); // allocate on heap
}

So what type should DelegateCaller._foo be?

I think the only real solution to this, aside from compiler analysis (which introduces all kinds of problems), is to declare all delegates are stack or heap allocated by default, and allow the developer to deviate by declaring the delegate as opposite.

As I think most function delegates are expected to be stack allocated, it makes sense to me that stack delegates should be the default.

As a suggestion for syntax, I'd say heap-allocated delegates should use the new keyword somehow:

return new DelegateCaller(new(&x));

One issue to determine is how heap-allocated delegates are done.  Should
there be only one heap allocation per function call, or one per
instantiation?  If so, what happens if you change data in the function after
instantiation? The difference is significant if you create multiple
delegates:
int delegate() foo[];

int i = 0;
int getI() { return i; }

foo ~= new(&getI);

i++;
foo ~= new(&getI);
i++;
for(int j = 0; j < foo.length; j++)
{
   writefln(foo[j]);
}

What should be the correct output?

0
1

or

0
2

or

2
2

-Steve

On Sun, Oct 26, 2008 at 11:38 PM, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>> I also think that scope and heap-allocated delegates should have different types so that no imlicit casting from scope delegate to heap one would be possible. In this case callee function that recieves the delegate might demand the delegate to be heap-allocated (because it stores it, for example).
>
> I've been thinking about this solution, and I think the decision to allocate scope or heap should be left up to the developer, and no types should be assigned.
>
> Think about an example like this:
>
> class DelegateCaller
> {
>   private delegate int _foo();
>   this(int delegate() foo) { _foo = foo; }
>   int callit() { return _foo();}
> }
>
> int f1()
> {
>    int x() { return 5; }
>    scope dc = new DelegateCaller(&x); // allocate on stack
>    return dc.callit() * dc.callit();
> }
>
> DelegateCaller f2()
> {
>   int x() { return 5;}
>   return new DelegateCaller(&x); // allocate on heap
> }
>
> So what type should DelegateCaller._foo be?

Ok, so that's a good example where only the caller knows that heap allocation is necessary, and we already discussed a case where only the callee knows it's necessary.

> I think the only real solution to this, aside from compiler analysis (which introduces all kinds of problems), is to declare all delegates are stack or heap allocated by default, and allow the developer to deviate by declaring the delegate as opposite.

It seems to me that from the two cases above, a good solution might be to make stack the default but to allow *either* the callee *or* the caller to request that that default be overridden.

> As I think most function delegates are expected to be stack allocated, it makes sense to me that stack delegates should be the default.

> As a suggestion for syntax, I'd say heap-allocated delegates should use the new keyword somehow:
>
> return new DelegateCaller(new(&x));
>
> One issue to determine is how heap-allocated delegates are done.  Should
> there be only one heap allocation per function call, or one per
> instantiation?  If so, what happens if you change data in the function after
> instantiation? The difference is significant if you create multiple
> delegates:
> int delegate() foo[];
>
> int i = 0;
> int getI() { return i; }
>
> foo ~= new(&getI);
>
> i++;
> foo ~= new(&getI);
> i++;
> for(int j = 0; j < foo.length; j++)
> {
>   writefln(foo[j]);
> }
>
> What should be the correct output?
>
> 0
> 1

Without thinking about implementation or the current behavior at all,
this is the output I would expect from a full closure.
It should capture the state at the time of its creation.

With the either/or proposal you'll need another rule, I think.  If you have a case like this:

    void longTermDelegateKeeper(new int delegate() dg) { ... }  //
here "new" means heap required
    ...
    int i = 0;
    int getI() { return i; }
    int delegate() foo[];
    foo ~= &getI;
    i++;
    longTermDelegateKeeper(foo[0]);  // <- what happens?

Here there are two options for the "what happens" line I think:
1) stack delegate returned by foo[0] triggers an implicit allocation
and copying of current stack variables. (so foo[0]() will return "1")
2) compiler error: "Heap delegate expected".

I think #2 is the right answer here.  Force the caller to explicitly create a heap delegate out of the stack delegate.  And by doing that force the caller to examine which state he really mean to capture in that delegate.   Did he want it to capture the i==1 state or did he want it to capture i==0?  And in a loop context it will force the developer to notice that he's triggering implicit allocations inside a loop when he may not mean to.

It also would make it possible to recognize allocations just by looking at code locally.   Aside from these D2 delegates I think it's always possible to tell looking at D code where the allocations are. Setting a .length or doing ~= are not obviously (and not necessarily) allocations, but if you see one then you can guess that allocation is involved.   I don't really want to end up with a situation where I have to guess if the code I'm looking at is doing allocation just by calling a function that itself doesn't do any allocation either.

Finally -- do stack and heap delegates really need to be distinct types?  Maybe not.  Maybe a run-time check would be good enough.  if there's some kind of isHeapDelegate(dg) check available then, library writers could use that.  The compiler wouldn't catch the error, but it might be sufficient to catch at runtime in order to avoid the pain of introducing more types.

--bb

Objective 1: Make the heap vs. stack variables explicit
Objective 2: Make it impossible to return or store a static (stack) delegate
Objective 3: Don't require decorators on lambda expressions.

Solution:
- Variables are on stack by default
- Use modifier "heap" to put a variable on the heap
- Delegates can be normal (storable) or "scope" (can't live beyond the scope of our function, and the type is inferred BASED ON WHAT VARIABLES YOU ACCESS.


EXAMPLE CODE

void foo(scope void delegate()) {...}
void bar(void delegate()) {...}

void main()
{
  int a;
  heap int b;

  foo({ a = 1; });	// legal.
  bar({ b = 2; });	// legal.  bar could store dg, but b is on heap
  foo({ b = 3; });	// legal.  ok to pass non-scope dg to
			//         scope argument
  bar({ a = 4; });	// SYNTAX ERROR
			// delegate is scope b/c a is on stack, but
			// argument to bar isn't scope.
}

END CODE


Thoughts?