Escape analysis

[Steven Schveighoffer]

"Bill Baxter" wrote
> On Wed, Oct 29, 2008 at 4:56 AM, Steven Schveighoffer
> <schveiguy at yahoo.com> wrote:
>> "Bill Baxter" wrote
>>> On Tue, Oct 28, 2008 at 10:54 PM, Steven Schveighoffer
>>> <schveiguy at yahoo.com> wrote:
>>>>
>>>> What I'd prefer is allocate closure when you can prove it, allow
>>>> specification when you can't.  That is, allocate a closure
>>>> automatically
>>>> in
>>>> simple cases like this:
>>>>
>>>> int *f() {int x = 5; return &x;}
>>>>
>>>> And in cases where you can't prove it, default to not allocating a
>>>> closure,
>>>> and allow the developer to specify that a closure is necessary:
>>>
>>> So basically programmers have to memorize all the rules the compiler
>>> uses to prove when it's necessary to allocate a closure, and then run
>>> those rules in their heads to determine if the current line of code
>>> will trigger allocation or not?
>>
>> First, the compiler does not have any sound rules for this.  It currently
>> allocates a closure on a knee jerk reaction from taking the address of a
>> stack variable.  And its either this or substitute in your statement
>> "prove
>> when it's *not* necessary to allocate a closure", which is about as hard
>> and
>> probably 10x more common.
>>
>> Second, for 90% of functions that don't require you to allocate closures,
>> you don't have to think about any rules.
>
> I don't see why not.  Because the compiler might be allocating a
> closure when I don't want it to, killing  performance.  So I'll either
> be surprised later, or I need to think about it when I'm writing that
> line of code.

No, I'm proposing the compiler SHOULDN'T allocate closures unless it can
prove without a shadow of a doubt that a closure is required.  i.e. it
defaults to D1 behavior, which should cover 90% of functions today.

>> For the 9% of functions which return a pointer to local data, proven by
>> the
>> compiler, you don't have to think about rules.
>
> Except didn't you just give us some examples where the function does
> things that escape in the local sense, but can be seen not to escape
> when examining the full context?

This is what I'm thinking as proven by the compiler:

int *f()
{
   int x = 5;
   return &x;
}

There is no doubt that this will cause an escape.  A more common scenario (I
just ran into this with a newb on irc):

char[] readData(InputStream s)
{
   char[64] buf;
   auto len = s.read(buf);
   return buf[0..len];
}

> So in those 9% of the cases I may also want to think about what the
> compiler will do to avoid unnecessary hidden allocations in my code.
> And if I am getting one of these unnecessary allocations, then I will
> have to think about how to rearrange my code so that the compiler
> doesn't get tricked.  But it could be a library function that's
> causing it.

I'm starting to think that if you compile with warnings on, these 9% of
functions shouldn't compile.  Perhaps they shouldn't compile by default
since it's very easy to do this kind of stuff explicitly without closures.

>> For the last 1% of functions, the documentation should clarify how your
>> data
>> can escape, and then you have to think about how that affects your usage
>> of
>> it.  The docs could say 'best to allocate a closure unless you know what
>> you
>> are doing'.
>
>>> And when the compiler gets a little smarter, the programmers need to
>>> get smarter, too.  In lock step.
>>
>> Not really.  If the compiler can some day store the scope dependency
>> information in the object file (and get rid of reading source to
>> determine
>> function signature), then this whole manual requirement goes away.
>
> Until the compiler can do the right thing 100% of the time, I have to
> be on the lookout for spurious allocations.

I'm saying no automatic closures unless it's absolutely provable that an
escape occurs.

>
>>> That doesn't sound like a good solution to me.
>>
>> Then let's go back to D1's solution -- no closures ;)
>
> Sure.  But if you're going to do that, then at least give us an easy
> way to explicitly request a closure for those of us who know we need
> one and when we don't. :-)

Assuming the compiler does not ever allocate closures needlessly, I agree
with a way to specify when closures should occur, but not when they should
not (since there's no need).

-Steve