More on C++ stack arrays

[bearophile]

Walter Bright:

> If your optimizing compiler is that good, it can optimize "new 
> T[n]" to be on the stack as well.

That's escape analysis, and it returns a failure as soon as you 
return the array, unless you also analyze the caller, and 
allocate in the caller stack frame, but this can't be done if the 
length of the array is computed in the middle of the called 
function.

 From what I've seen escape analysis is not bringing Java close to 
D performance when you use 3D vectors implemented as small class 
instances. We need something that guarantees stack allocation if 
there's enough space on the stack.


> I'm not particularly enamored with the compiler inserting 
> silent copying to the heap - D programmers tend to not like 
> such things.

An alternative solution is to statically require a ".dup" if you 
want to return one of such arrays (so it becomes a normal dynamic 
array). This makes the heap allocation visible.

An alternative solution is to copy the data to the stack frame of 
the caller. But if you do this there are some cases where one of 
such arrays can't be put (as in the C++ proposals), but this is 
not too much bad.


> Rust is barely used at all,

Right, there is only an experimental compiler written in it, and 
little more, like most of the compiler.

On the other hand Ada is around since a lot of time. And in the 
Ada 2005 standard library they have added bounded containers, so 
you can even allocate max-sized associative arrays on the stack 
:-) This shows how they care to not use heap. I think that 
generally Ada code allocates much less often on the heap compared 
to the D code.


> Allocating a few extra bytes on the stack generally costs 
> nothing unless you're in a recursive function.

If you over-allocate you are using more stack space than 
necessary, this means you are moving away from cache-warm parts 
of the stack to parts that are outside the L1 or L2 cache. This 
costs you time. Saving stack saves some run-time.

Another problem is that D newbies and normal usage of D tends to 
stick to the simplest coding patterns. Your coding pattern is 
bug-prone even for you and it's not what programmers will use in 
casual D code. Stack allocation of (variable sized) arrays should 
become much simpler, otherwise most people in most cases will use 
heap allocation. Such allocation is not silent, but it's not 
better than the "silent heap allocations" discussed above.


> Of course, if you're in a recursive function, stack allocated 
> dynamic arrays can have unpredictable stack overflow issues.

Unless you are using a segmented stack as Go or Rust.


> The technique I showed is also generally faster than dynamic 
> stack allocation.

Do you have links to benchmarks?

Bye,
bearophile