Dynamic Closure + Lazy Arguments = Performance Killer?

[Steven Schveighoffer]

"Denis Koroskin" wrote
> On Sat, 25 Oct 2008 18:36:27 +0400, Lars Ivar Igesund 
> <larsivar at igesund.net> wrote:
>
>> Bill Baxter wrote:
>>
>>> On Sat, Oct 25, 2008 at 5:24 PM, Jason House
>>> <jason.james.house at 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