D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 10242 - Conservative escape analysis for dynamic array allocation
Summary: Conservative escape analysis for dynamic array allocation
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: dmd (show other issues)
Version: D2
Hardware: All All
: P2 enhancement
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-06-02 06:07 UTC by bearophile_hugs
Modified: 2020-05-15 03:25 UTC (History)
1 user (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description bearophile_hugs 2013-06-02 06:07:39 UTC
Time ago I have suggested to support a syntax like:


void main(string[] args) {
    scope int[] data0 = new int[5 + args.length];
}


That syntax must give a compile-time error if you escape data0 in some way.

But an alternative idea, potentially able to improve the performance of lost D code, is to perform escape analysis on dynamic array allocations. If a dynamic array is allocated and it doesn't get out of the scope, then if it's small it can be allocated with an alloca by the D front-end.

In code like this data1 escapes the scope of foo through the pointer p, so it's allocated on the heap. data2 escapes trough a global variable. But data3 doesn't escape:

int[] data;
int foo(in uint n, ref int* p) nothrow {
    int[] data1 = new int[1 + n];
    p = &data1[1]; // Local pointer escape.
    int[] data2 = new int[2 + n];
    data = data2[1 .. 2]; // Global slice escape.
    int[] data3 = new int[3 + n]; // DFoesn't escape.
    foreach (i, ref d; data3)
        d = i;
    int total = 0;
    foreach (d; data3)
        total += d;
    return total;
}
void main() {}


So this part of foo:

...
    int[] data3 = new int[3 + n];
    foreach (i, ref d; data3)
        d = i;
    int total = 0;
    foreach (d; data3)
        total += d;
    return total;
}


Can be rewritten by the D front-end with a usually run-time length test of the amount of memory to allocate (here 3+n integers). If it's a large amount of memory then data3 should be allocated on the heap and a call to gc.free should be added by the front-end at the end of foo. If the amount of memory to allocate is small, then maybe the front-end can allocate it on the stack with an alloca().

The advantage of using "scope" is that it's a two-way contract between compiler and programmer, and it avoids some mistakes of unwanted escaping. Another advantage of "scope" is that it gives more control to the programmer, and this is useful to avoid some of the stack overflows in recursive functions caused by an unavoidable automatic usage of alloca() from the front-end.
Comment 1 Mathias LANG 2020-05-15 03:25:53 UTC
Closing because:
- LDC does this nowadays;
- There are various issues in the tracker for `scope x = new array[]`;

So while the exact suggestion here is not implemented, one can use LDC to eliminate heap allocations.