4 ms·

This article is about Go, but I wonder how many C/C++ developers realize that you've always had the ability to allocate on the stack using alloca() rather than

This article is about Go, but I wonder how many C/C++ developers realize that you've always had the ability to allocate on the stack using alloca() rather than malloc(). Of course use cases are limited (variable length buffers/strings, etc) since the lifetime of anything on the stack has to match the lifetime of the stack frame (i.e the calling function), but it's super fast since it's just bumping up the stack pointer.

ozgrakkurt 8mo ago
This is more of a patch/hack solution as far as I can understand. You can just as well pass a heap allocated buffer + size around and allocate by incrementing/decrementing size. Or even better use something like zig's FixedSizeAllocator. Correct me if I am wrong please
- HarHarVeryFunny 8mo ago
  I wouldn't call it a hack, but it's not a general alternative for memory allocated on the heap since the lifetime is tied to that of the allocating function. I think what you're referring to is an arena allocator where you allocate a big chunk of memory from the heap, then sequentially sub-allocate from that, then eventually free the entire heap chunk (arena) in one go. Arena allocators are therefore also special use case since they are for when all the sub-allocations have the same (but arbitrary) lifetime, or at least you're willing to defer deallocation of everything to the same time. So, heap, arena and stack allocation all serve different purposes, although you can just use heap for everything if memory allocation isn't a performance issue for your program, which nowadays is typically the case. Back in the day when memory was scarce and computers were much slower, another common technique was to keep a reuse "free list" of allocated items of a given type/size, which was faster than heap allocate and free/coalesce, and avoided the heap fragmentation of random malloc/frees.
rwmj 8mo ago
Most C compilers let you use variable length arrays on the stack. However they're problematic and mature code bases usually disable this (-Werror -Wvla) because if the size is derived from user input then it's exploitable.
stackghost 8mo ago
alloca()'s availability and correctness/bugginess is platform dependent, so it probably sees only niche usage since it's not portable. Furthermore, even its man page discourages its use in the general case: >The alloca() function is machine- and compiler-dependent. Because it allocates from the stack, it's faster than malloc(3) and free(3). In certain cases, it can also simplify memory deallocation in applications that use longjmp(3) or siglongjmp(3). Otherwise, its use is discouraged. Furthermore: >The alloca() function returns a pointer to the beginning of the allocated space. If the allocation causes stack overflow, program behavior is undefined. https://man7.org/linux/man-pages/man3/alloca.3.html https://man7.org/linux/man-pages/man3/alloca.3.html
- HarHarVeryFunny 8mo ago
  Yeah, all stack overflow behavior is undefined in C/C++, although both on Linux and Windows you'll get a page fault (SEGV) on stack overflow since memory beyond the stack is deliberately unmapped.
spacechild1 8mo ago
alloca() is super useful, but it's also quite dangerous because you can easily overflow the stack. The obvious issue is that you can't know how much space is left on the stack, so you basically have to guess and pick an arbitrary "safe" size limit. This gets even more tricky when functions may be called recursively. The more subtle issue is that the stack memory returned by alloca() has function scope and therefore you must never call it directly in a loop. I use alloca() on a regular basis, but I have to say there are safer and better alternatives, depending on the particular use case: arena/frame allocators, threadlocal pseudo-stacks, static vectors, small vector optimizations, etc.
- 12_throw_away 8mo ago
  > The obvious issue is that you can't know how much space is left on the stack [...] Oh, huh. I've never actually tried it, but I always assumed it would be possible to calculate this, at least for a given OS / arch. You just need 3 quantities, right? `remaining_stack_space = $stack_address - $rsp - $system_stack_size`. But I guess there's no API for a program to get its own stack address unless it has access to `/proc/$pid/maps` or similar?
  - deleted 8mo ago
    [deleted]
  - chuckadams 8mo ago
    If your API includes inline assembly, then it's trivial. Go's internals would need it to swap stacks like it does. But I doubt any of that is exposed at the language level.
  - Joker_vD 8mo ago
    > $system_stack_size Does such thing even exist? And non-64 bit platforms the address space is small enough that with several threads of execution you may just be unable to grow your stack even up to $system_stack_size because it'd bump into something else.
    - 8mo ago
anematode 8mo ago
If you're not doing recursion, I prefer using an appropriately sized thread_local buffer in this scenario. Saves you the allocation and does the bookkeeping of having one per thread
lstodd 8mo ago
It becames super slow when you bump that pointer into a page that's missing from the TLB.
- HarHarVeryFunny 8mo ago
  A TLB miss could happen when executing the next statement in your program. It's not something you have a lot of control over, and doesn't change the fact that allocating from the stack (when an option) is going to be faster than allocating from the heap.
  - lstodd 8mo ago
    So you don't allocate left and right, be it stack or heap. It's all useless though unless you control the hardware. If you don't, you might as well prlimit --stack=unlimited and have at it.
dzdt 8mo ago
For purely historical reasons the C/C++ stack is "small" with exactly how small being outside of programmer control. So you have to avoid using the stack even if it would be the better solution. Otherwise you risk your program crashing/failing with stack overflow errors.
- csjh 8mo ago
  What do you mean outside of programmer control? What's stopping you from setting the stack size in the linker flags?
  - HarHarVeryFunny 8mo ago
    With Linux the stack size is a process limit, set with ulimit (default 8MB?). You can even set it to unlimited if you want, meaning that essentially (but not quite) the stack and heap grow towards each other only limited by the size of the address space. ulimit only affects the main program stack though. if you are using multi-threading then there is a per-thread stack limit, which you can configure with pthreads, but not until C++23 for std::thread.
up2isomorphism 8mo ago
It is a good thing many people do not know it. Since if you need this to squeeze that little performance window, you’d better know what you are doing.

ozgrakkurt 8mo ago

This is more of a patch/hack solution as far as I can understand. You can just as well pass a heap allocated buffer + size around and allocate by incrementing/decrementing size. Or even better use something like zig's FixedSizeAllocator. Correct me if I am wrong please

HarHarVeryFunny 8mo ago
I wouldn't call it a hack, but it's not a general alternative for memory allocated on the heap since the lifetime is tied to that of the allocating function. I think what you're referring to is an arena allocator where you allocate a big chunk of memory from the heap, then sequentially sub-allocate from that, then eventually free the entire heap chunk (arena) in one go. Arena allocators are therefore also special use case since they are for when all the sub-allocations have the same (but arbitrary) lifetime, or at least you're willing to defer deallocation of everything to the same time. So, heap, arena and stack allocation all serve different purposes, although you can just use heap for everything if memory allocation isn't a performance issue for your program, which nowadays is typically the case. Back in the day when memory was scarce and computers were much slower, another common technique was to keep a reuse "free list" of allocated items of a given type/size, which was faster than heap allocate and free/coalesce, and avoided the heap fragmentation of random malloc/frees.

rwmj 8mo ago

Most C compilers let you use variable length arrays on the stack. However they're problematic and mature code bases usually disable this (-Werror -Wvla) because if the size is derived from user input then it's exploitable.

stackghost 8mo ago

alloca()'s availability and correctness/bugginess is platform dependent, so it probably sees only niche usage since it's not portable. Furthermore, even its man page discourages its use in the general case: >The alloca() function is machine- and compiler-dependent. Because it allocates from the stack, it's faster than malloc(3) and free(3). In certain cases, it can also simplify memory deallocation in applications that use longjmp(3) or siglongjmp(3). Otherwise, its use is discouraged. Furthermore: >The alloca() function returns a pointer to the beginning of the allocated space. If the allocation causes stack overflow, program behavior is undefined. https://man7.org/linux/man-pages/man3/alloca.3.html https://man7.org/linux/man-pages/man3/alloca.3.html

HarHarVeryFunny 8mo ago
Yeah, all stack overflow behavior is undefined in C/C++, although both on Linux and Windows you'll get a page fault (SEGV) on stack overflow since memory beyond the stack is deliberately unmapped.

spacechild1 8mo ago

alloca() is super useful, but it's also quite dangerous because you can easily overflow the stack. The obvious issue is that you can't know how much space is left on the stack, so you basically have to guess and pick an arbitrary "safe" size limit. This gets even more tricky when functions may be called recursively. The more subtle issue is that the stack memory returned by alloca() has function scope and therefore you must never call it directly in a loop. I use alloca() on a regular basis, but I have to say there are safer and better alternatives, depending on the particular use case: arena/frame allocators, threadlocal pseudo-stacks, static vectors, small vector optimizations, etc.

12_throw_away 8mo ago
> The obvious issue is that you can't know how much space is left on the stack [...] Oh, huh. I've never actually tried it, but I always assumed it would be possible to calculate this, at least for a given OS / arch. You just need 3 quantities, right? `remaining_stack_space = $stack_address - $rsp - $system_stack_size`. But I guess there's no API for a program to get its own stack address unless it has access to `/proc/$pid/maps` or similar?
- deleted 8mo ago
  [deleted]
- chuckadams 8mo ago
  If your API includes inline assembly, then it's trivial. Go's internals would need it to swap stacks like it does. But I doubt any of that is exposed at the language level.
- Joker_vD 8mo ago
  > $system_stack_size Does such thing even exist? And non-64 bit platforms the address space is small enough that with several threads of execution you may just be unable to grow your stack even up to $system_stack_size because it'd bump into something else.
  - 8mo ago

anematode 8mo ago

If you're not doing recursion, I prefer using an appropriately sized thread_local buffer in this scenario. Saves you the allocation and does the bookkeeping of having one per thread

lstodd 8mo ago

It becames super slow when you bump that pointer into a page that's missing from the TLB.

HarHarVeryFunny 8mo ago
A TLB miss could happen when executing the next statement in your program. It's not something you have a lot of control over, and doesn't change the fact that allocating from the stack (when an option) is going to be faster than allocating from the heap.
- lstodd 8mo ago
  So you don't allocate left and right, be it stack or heap. It's all useless though unless you control the hardware. If you don't, you might as well prlimit --stack=unlimited and have at it.

dzdt 8mo ago

For purely historical reasons the C/C++ stack is "small" with exactly how small being outside of programmer control. So you have to avoid using the stack even if it would be the better solution. Otherwise you risk your program crashing/failing with stack overflow errors.

csjh 8mo ago
What do you mean outside of programmer control? What's stopping you from setting the stack size in the linker flags?
- HarHarVeryFunny 8mo ago
  With Linux the stack size is a process limit, set with ulimit (default 8MB?). You can even set it to unlimited if you want, meaning that essentially (but not quite) the stack and heap grow towards each other only limited by the size of the address space. ulimit only affects the main program stack though. if you are using multi-threading then there is a per-thread stack limit, which you can configure with pthreads, but not until C++23 for std::thread.

up2isomorphism 8mo ago

It is a good thing many people do not know it. Since if you need this to squeeze that little performance window, you’d better know what you are doing.