I have a fundamental language design talking point for you. It's not specific to D. I claim that, most of the time, a programmer cannot, and shouldn't have to, make the decision of whether to allocate on stack or heap. For example:

void func(T)()
{
    auto t = <allocate T from heap or stack?>
    ...
}

The question of whether variable t should lay in heap or stack, depends not only on the sizeof(T), but also on the context in which func is called at. If func is called at a context in which allocating T on stack would cause a stack overflow, then t should be allocated from the heap. On the other hand, if func is called at a context where T still fits nicely on the stack, it would probably be better and faster to allocate t on stack.

So, the question of whether to allocate that variable t on stack or heap is something that only the compiler (or runtime) can answer. Is there any language where you have the ability to say "allocate T from wherever it's best"?

I wonder if it would be possible in D to let the compiler allocate dynamic arrays on stack when it can statically guarantee that it's safe to do so (no dangling references, never increasing the size of the array, etc).

On 11/4/12 12:35 PM, Tommi wrote:
> I have a fundamental language design talking point for you. It's not
> specific to D. I claim that, most of the time, a programmer cannot, and
> shouldn't have to, make the decision of whether to allocate on stack or
> heap.

I don't think that claim is valid. As a simple example, polymorphism requires indirection (due to variations in size of the dynamic type compared to the static type) and indirection is strongly correlated with dynamic allocation. Also, the value vs. reference semantics of type are strongly correlated with where objects should go. So on the contrary, quite often heap vs. stack allocation is forced by the nature of what's allocated.

Andrei

On Sunday, 4 November 2012 at 17:35:09 UTC, Tommi wrote:
> I wonder if it would be possible in D to let the compiler allocate dynamic arrays on stack when it can statically guarantee that it's safe to do so (no dangling references, never increasing the size of the array, etc).

David Nadlinger was talking about how LDC does an optimization exactly like this, quite recently.

On Sunday, 4 November 2012 at 17:41:17 UTC, Andrei Alexandrescu wrote:
>
> I don't think that claim is valid. As a simple example, polymorphism requires indirection (due to variations in size of the dynamic type compared to the static type) and indirection is strongly correlated with dynamic allocation.

Sure, there are situations where heap allocation is always needed. But couldn't the question of "whether to heap or stack allocate" be considered just an implementation detail of the language. And hide that implementation detail so that the programmer doesn't even need to know what the words heap and stack mean.

I mean, wouldn't it be theoretically possible to sometimes even let the compiler allocate class objects in D from the stack, if the compiler can see that it's safe to do so (if that variable's exact type is known at compile time and never changes).

11/4/2012 9:35 PM, Tommi пишет:
> I have a fundamental language design talking point for you. It's not
> specific to D. I claim that, most of the time, a programmer cannot, and
> shouldn't have to, make the decision of whether to allocate on stack or
> heap.

Actually it can and most definitely should. It's scoped lifetime vs infinite lifetime, reference and value semantics. And e.g. RAII structs have to be on stack to have their effect applied usefully. Storing the reference to 't' elsewhere implies heap allocation (be it GC heap or manually managed one).

Going further allocation strategy is a deep topic with a lot of considerations and in the end it goes far beyond stack vs GC heap.

> For example:
>
> void func(T)()
> {
>      auto t = <allocate T from heap or stack?>
>      ...
> }
>
> The question of whether variable t should lay in heap or stack, depends
> not only on the sizeof(T), but also on the context in which func is
> called at. If func is called at a context in which allocating T on stack
> would cause a stack overflow, then t should be allocated from the heap.

In fact placing big object on stack just because it fits could introduce stack overflow few hundred calls later.
In general compiler can't know beforehand how big stack space you'll need and thusly the portion of it to use safely.

> On the other hand, if func is called at a context where T still fits
> nicely on the stack, it would probably be better and faster to allocate
> t on stack.

Unless you escape references. Compiler could detect it but will stay on the conservative side. In the end it may end up with unexpected heap allocations.

>
> So, the question of whether to allocate that variable t on stack or heap
> is something that only the compiler (or runtime) can answer.

God no. It may as well depend on the code compiler knows nothing about (nor run-time for this matter).

extern(C):
int blah(void* ptr);

void func(T)()
{
      auto t = <allocate T from heap or stack?>
      blah(&t); //now what?
      ...
}

If blah doesn't store pointer somewhere inside you are fine with stack. If it does then not even GC heap will help you.

> Is there
> any language where you have the ability to say "allocate T from wherever
> it's best"?

In simplest case I'd consider ability to bypass allocation on heap as an optimization.

> I wonder if it would be possible in D to let the compiler allocate
> dynamic arrays on stack when it can statically guarantee that it's safe
> to do so (no dangling references, never increasing the size of the
> array, etc).


-- 
Dmitry Olshansky

Am 04.11.2012 18:41, schrieb Andrei Alexandrescu:
> On 11/4/12 12:35 PM, Tommi wrote:
>> I have a fundamental language design talking point for you. It's not
>> specific to D. I claim that, most of the time, a programmer cannot, and
>> shouldn't have to, make the decision of whether to allocate on stack or
>> heap.
>
> I don't think that claim is valid. As a simple example, polymorphism
> requires indirection (due to variations in size of the dynamic type
> compared to the static type) and indirection is strongly correlated with
> dynamic allocation. Also, the value vs. reference semantics of type are
> strongly correlated with where objects should go. So on the contrary,
> quite often heap vs. stack allocation is forced by the nature of what's
> allocated.
>
> Andrei
>

Java and Go work around this issue using escape analysis, in opposite directions though.

In Java most JITs can allocate objects in the stack if they see the object does not escape the local scope.

Go goes the other way, by allocating in the heap local objects that are usually allocated on the stack but are returned the caller.

--
Paulo

On Sunday, 4 November 2012 at 18:14:36 UTC, Dmitry Olshansky wrote:
>
> extern(C):
> int blah(void* ptr);
>
> void func(T)()
> {
>       auto t = <allocate T from heap or stack?>
>       blah(&t); //now what?
>       ...
> }
>
> If blah doesn't store pointer somewhere inside you are fine with stack. If it does then not even GC heap will help you.


In a perfect world, I think, the compiler would see that blah stores ptr and therefore would (implicitly) allocate t on the heap. The deallocation of the memory for t would be handled either by garbage collector or by some kind of implicit reference counting.

I guess with extern C functions none of the above is doable.

On Sunday, 4 November 2012 at 18:14:36 UTC, Dmitry Olshansky wrote:
> In fact placing big object on stack just because it fits could introduce stack overflow few hundred calls later.

But that's kind of my point also. For example:

void func(T)(int n)
{
    if (n <= 0)
        return;

    auto t = <create variable t of type T>
    ...
    func!(T)(n - 1);
}

If func is called with a runtime argument n, then the programmer cannot determine the most sensible way to allocate for variable t. What I'd like to happen is that, at runtime, every time a variable t is created, the program would determine the best way to allocate the memory for it, based on the available stack size (prefer stack if there's room there).

On Sunday, 4 November 2012 at 18:14:36 UTC, Dmitry Olshansky wrote:
> In general compiler can't know beforehand how big stack space you'll need and thusly the portion of it to use safely.

Yeah, I just realized it can't be done at compile-time. Making the decision between stack or heap allocation should happen at run-time.

On Sunday, 4 November 2012 at 19:42:29 UTC, Tommi wrote:
> void func(T)(int n)
> {
>     if (n <= 0)
>         return;
>
>     auto t = <create variable t of type T>
>     ...
>     func!(T)(n - 1);
> }
>
> If func is called with a runtime argument n, then the programmer cannot determine the most sensible way to allocate for variable t.

The reason for that being that if n is large enough and t gets always allocated on stack, then there's going to be a stack overflow. And if n is small enough so that all those t's could be allocated on stack, then allocating them on heap would just make the code slower.

On Sunday, 4 November 2012 at 17:41:19 UTC, Jakob Ovrum wrote:
> On Sunday, 4 November 2012 at 17:35:09 UTC, Tommi wrote:
>> I wonder if it would be possible in D to let the compiler allocate dynamic arrays on stack when it can statically guarantee that it's safe to do so (no dangling references, never increasing the size of the array, etc).
>
> David Nadlinger was talking about how LDC does an optimization exactly like this, quite recently.

Yes, LDC has an optimization pass like this indeed. However, it is currently disabled because its implementation causes a seemingly unrelated, hard-to-diagnose test suite failure. If anyone is interested in doing a little compiler debugging, here is the current state: https://github.com/ldc-developers/ldc/pull/206. I unfortunately won't be able to work on it in the next few days…

David