[Issue 9832] New: Partially library-defined stack-allocated variable length arrays

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=9832

           Summary: Partially library-defined stack-allocated variable
                    length arrays
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2013-03-29 16:04:25 PDT ---
This ER comes from the ashes of Issue 5348  See there for more info.

C99 VLAs have some problems, so this is a rough proposal for dynamic-size
stack-allocated arrays (abbreviated to DSSAA) for D that avoid their problems.

This idea comes from a C++ proposal:

http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3532.html

Ada2012 has added stack-allocated collections. Rust allows any thing you want
to be allocated on the stack, if you want. In certain cases heap allocations
are bad for performance.

Using DSSAA it will be possible to create several other stack-allocated
collections for D, as in Ada (and in future probably Rust).


An idea from Walter (from Issue 5348 ):

> 2. I'd prefer to deal with stack allocated arrays by optimization rather than
> new syntax & semantics, i.e.:
> 
>     int[] array = new int[5];
> 
> and determining that array[] can never leave its scope, and so can be allocated
> on the stack.

I think that has problems:
1) Since some time Java has added escape analysis to stack-allocate some
objects and reduce a little the pressure on the GC. This feature is useful in
Java, but also it shows its limits, in many cases it fails, so it doesn't bring
a large improvement in Java.
2) I'd like DSSAA to be able to leave the scope (the simplest way to do this is
to "dup" on them, copying them on the heap. Below I show another way to do it).

A solution is to invent library-defined arrays that have a semantics different
from the regular dynamic arrays.


> 3. Consider that static arrays are passed by value to functions, rather
> than by reference. VLAs for static arrays mess this up.

A solution is to add a special value array to Phobos, as in that n3532, and
then let the D compiler manage it in a special way, allocating it on the stack
where possible (if you use it inside a struct its storage goes on the heap,
like a dynamic array). D compilers are supposed to be able to stack-allocate
them, and most of them will do it. But a conforming D compiler is not forced to
stack allocate them.


In the following case foo creates a DSSAA and returns it. A DSSAA keeps its
lenght beside the data, in the stack frame. At the return point inside bar()
bar allocates another DSSAA on the stack (increasing the size of the stack
frame of bar) and copies the received data:


import std.collections: ValArray;
ValArray!int foo(int n) {
    auto a = ValArray!int(n); // on the stack.
    return a;
}
void bar() {
    ValArray!int b = foo(5); // copied on the stack.
}


In this case foo() creates the DSSAA and calls bar with it. D just returns
pointer to the data on the stack frame plus length (so it's a kind of slice)
and then under the cover the data is also copied inside the stack frame of bar:

import std.collections: ValArray;
void foo(int n) {
    auto a = ValArray!int(n);
    bar(a);
}
void bar(ValArray!int b) {
}


Inside the implementation of that ValArray happens a bit of magic. And the
compiler should recognize it and manage its memory in a special way, like it
does with the special function alloca().

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------