Dynamic Closure + Lazy Arguments = Performance Killer?

[Bill Baxter]

On Sun, Oct 26, 2008 at 11:38 PM, Steven Schveighoffer
<schveiguy at 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