reintroduce VLAs and alloca() on auxillary stack

[shawnl]

Stacks (especially the C stack because it uses a dedicated register), are very performant data structures. Zig should not abandon full use of the C stack, with both VLAs[1] and @alloca(). For example they enable recursive-descent parsers. Not that @alloca() isn't often used incorrectly (for example the zig std libs used @alloca() where a PATH_MAX 4096 bytes buffer would have sufficed. ) There are three ways to bring them back:

1. Bring them back on the main (sp) stack, adding a version of @alloca() that has a maximum size. This maximum size can be used by the stack size determination of Builtin function to tell you the maximum stack size of a given function #157. Call graphs that are infinitely recursive or use raw @alloca() will be marked "stack overflow unsafe" and should be called on the non-main stack (via a thread or @newStackCall()) so that the stack space can de-allocated when they exit.

2. Bring them back on a built-in auxillary stack.
   This only has overhead when used.
   If that stack pointer is used (by VLAs or @alloca()) a SIGSEGV handler will allocate an auxillary stack with mmap(), along with a guard page at the end with mmap() so that subsequent overflows can be caught and the auxiliary stack further extended.

3. Bring them back on a auxiliary stack without language support.
   The auxiliary stack pointer would be passed around between successive functions, but that would be fine for a recursive descent parser.

Both 2 and 3 would benifit from #782.

[1] https://clang.llvm.org/compatibility.html#vla

[tiehuis]

Can you elaborate here? I'm not familiar with what this is and can't find any obvious information.

I'm pretty positive we aren't going to have VLA's or any direct variable-sized stack allocation in Zig. #225 (comment)

[isaachier]

I think @shawnl is describing a safe way to use alloca on a separate stack. This might be able to mitigate the problems with alloca in general.

[shawnl]

@isaachier yes. I guess I am not describing it correctly. It almost needs its own stack-pointer register, which itsn't a good idea on architectures which don't have many registers (like 32-bit x86)

[andrewrk]

What's the difference between this and allocating heap memory?

How does this fit in with @newStackCall?

How does this fit in with coroutines (async functions)?

Can you show some code examples of how this would work? Explain the alternative you would have to do if this feature was not present.

[PavelVozenilek]

Arena allocator (also called region allocator) can be used to implement such functionality. Allocation is simply bumping up a pointer (+ checks for overflow and allocating new base block if needed). Zero memory overhead, not a single byte is wasted on size/internal pointers/whatever.

Deallocation is no-op, but in debug mode, it could still overwrite the allocated memory, to catch the bugs. To support this, it is needed to know allocated block size and pass it down to the deallocation function. If one doesn't need this, then the explicit size for deallocation is not needed at all, here or with any other allocator type.

It is possible to use combination of arena allocator and normal, heap based allocator. Arena sized for expected amount of allocations, and if application asks for more, then it "overflows" to the heap. Best of both worlds.

IMO it is better to have flexible and replaceable allocators than single purpose built-in feature. I once described what features could an allocator have in #480.

[PavelVozenilek]

There was also useful proposal on automatic resource deallocation #782. It would allow to implement this feature cleanly, w/o need for language support.

[shawnl]

TBH this issue was just an excuse to try to bring back VLAs and @alloca(), which I see as important access to the most performant implementation of a very performant data-structure (a stack). Issue updated.