Escape analysis

[Sergey Gromov]

Wed, 29 Oct 2008 11:52:14 -0400, Steven Schveighoffer wrote:

> "Sergey Gromov" wrote
>> Tue, 28 Oct 2008 23:33:53 -0400, Steven Schveighoffer wrote:
>>
>>> "Sergey Gromov" wrote
>>>> Steven Schveighoffer wrote:
>>>>> "Sergey Gromov" wrote
>>>>>> An argument to a virtual function call always escapes by default.  It
>>>>>> may be possible to declare an argument as non-escaping (scope?) and
>>>>>> compiler should then enforce non-escaping contract upon any overriding
>>>>>> functions.
>>>>>
>>>>> This is tricky, because most class member functions are virtual, so
>>>>> you are forced to litter all your functions with escaping/non-escaping
>>>>> syntax. To be accurate you need to define the escape graph in the
>>>>> signature, which will be a PITA.  What would be worse is to not have a
>>>>> way to express the complete graph.
>>>>
>>>> Not every call to a virtual function is itself virtual, and not every
>>>> virtual function cares whether its argument escapes.
>>>>
>>>> I'd say more: the noscope should be default for all reference types
>>>> except delegates because you usually don't care.  I agree that having
>>>> scope delegates the default is probably the right thing to do, but only
>>>> if a compiler can detect violations of this contract.
>>>
>>> A very very common technique in Tango to save using heap allocation is to
>>> declare a static array as a buffer, and then pass that buffer to be used 
>>> as
>>> scratch space in a function (which is possibly virtual).
>>>
>>> This would be my golden use case that has to not allocate anything and 
>>> has
>>> to work in order for any solution to be viable.
>>>
>>> Saying all reference types are noscope would prevent this, no?
>>
>> Allocation only happens when a stack variable reference escapes via a
>> delegate.  A static array is not a stack variable, therefore the compiler
>> doesn't care if it escapes.
> 
> A static array declared on the stack absolutely is a stack variable.
> 
> An example (from Tango's integer to text converter):
> 
> char[] toString (long i, char[] fmt = null)
> {
>         char[66] tmp = void;
>         return format (tmp, i, fmt).dup;
> }
> 
> Without the dup, toString returns a pointer to it's own stack.  With a full 
> graph analysis, it can be proven that tmp doesn't escape, but without either 
> that or some crazy scope scheme, it would either allocate a closure, or fail 
> to compile.  Neither of those options are acceptable.

There is no delegate, therefore nothing to allocate a closure for.  If
tmp escapes, it is a compile-time error.

If format() were pure it would be trivial to prove that tmp didn't
escape.  If format() is not pure, and escape graph for it is not known,
then issuing an error here would be too much of a breaking change, I
agree.

>>>>>> An argument to a function declared as a prototype always escapes by
>>>>>> default.  It may be possible for the compiler to export some meta-info
>>>>>> along with the prototype when a .di file is generated, whether an
>>>>>> argument is guaranteed to not escape, or maybe even detailed info 
>>>>>> about
>>>>>> which argument escapes where, to mimic the compile-time meta-info.
>>>>>
>>>>> No, the di file might not be auto-generated.  You also now back to a
>>>>> separate import and source file, like C has.  I think in order for this
>>>>> to
>>>>> work, the graph and object code must be stored in the same file that is
>>>>> imported.
>>>>
>>>> There are separate import files.  Actually compiler can simply put
>>>> scope/noscope for the arguments based upon the meta-data collected
>>>> during compilation.  If your .di is manually created, you either put
>>>> them manually as well, or you don't care.
>>>
>>> I think the graph has to be complete for this to be usable.  Otherwise, 
>>> it
>>> becomes an unused feature.  Using .di files is optional.  I generally 
>>> don't
>>> use them.
>>
>> For the incomplete graph to be usable, the compiler must assume the worst
>> for nodes with absent meta-info.  Therefore if you don't care to provide
>> meta-info for your modules, it'll still work, though not as efficiently.
>> On the other hand, if you supply .di files with your library and you do
>> care enough, or you generate your .di files automatically, the meta-info
>> will be present there saving some allocations for the user.
> 
> This doesn't cover virtual functions or runtime-determined delegates.  I'd 
> rather just have a separate meta file or have the meta data included in the 
> object file.  What is wrong with that?  Why must it be in the .di file?  If 
> the compiler always generates these meta files, then the graph is always 
> complete.

If you compile two files for the first time, and the first file imports
the second one, where do you get that meta-data for the second file?
What if you compile only one file, and that file imports another which
wasn't compiled yet?  Either you construct meta-data on the fly, or
require it included in the source, or assume it's not present (worst
case).

>>>>>> The expression graph analysis should be the first step towards safe
>>>>>> stack closures.
>>>>>
>>>>> I would agree with this.  But I don't think it's happening in the near
>>>>> future.  And I hope it's not done through .di files.
>>>>
>>>> You can limit analysis to a single module for now.  This will cover
>>>> local function calls, including some local method calls, and I hope
>>>> it'll also cover template function calls which means std.algorithm will
>>>> work without memory allocation again.
>>>
>>> Yes, but not class virtual methods or interface methods.  These are used
>>> quite a bit in Tango.  End result, not a lot of benefit.
>>
>> If those virtual and interface methods are often used with function-local
>> delegates as parameters then yes, the benefit wouldn't be that 
>> significant.
>> Are you sure this is the case with Tango?
> 
> Any time you use opApply (and opApply is virtual), you are doing this.

Fair enough.  opApply() is an important technique.