If I had a nickel for every article about avoiding implicit boxing in gc-heap languages...
...you would have the same balance as before, because this is not an article about implicit boxing. ;-)
Allocating on the Stack
31–40 of 59 posts
Re: Allocating on the Stack
#32This 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 point…
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.
Re: Allocating on the Stack
#33Earlier quoted context omitted.
C# has `stackalloc`
But that requires an explicit declaration and isn't done automatically under the hood, or am I missing something?
The JIT does this automatically in some cases as of .NET 10 (https://learn.microsoft.com/en-us/dotnet/core/whats-new/dotn...).
Re: Allocating on the Stack
#34Earlier quoted context omitted.
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 y…
> 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 `/pr…
You can do something like:
void *get_sp(void) {
volatile char c;
return (void *)&c;
}
void *get_sp(void) {
return __builtin_frame_address(0);
}
Re: Allocating on the Stack
#35This 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 point…
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.
What do you mean outside of programmer control? What's stopping you from setting the stack size in the linker flags?
Re: Allocating on the Stack
#36Optimizations like these are so cool. I love seeing higher level languages take advantage of their high level-ness
Re: Allocating on the Stack
#37Nice to see common and natural patterns to have their performance improved. Theoretically appending to a slice would be possible to handle with just stack growth, but that would require having large gaps between goroutine stacks and mapping them lazily upon access instead of moving goroutines to the new contiguous blocks as it's implemented right now. But given how many questionable changes it requires from runtime i…
Having big stack frames is bad for cache locality. Stack is not something magical, it's mapped to the same physical memory as heap and needs to be loaded. Pretty sure such optimization would reduce performance in most cases.
In the case where you're using the top of the stack as a, well, stack, I don't see the problem. It would only work if you're not interleaving processing of dynamically-sized objects and function codegen works out. It's similar to TCO in the sense of maintaining certain invariants across calls (e.g. no temporaries need be preserved), and actually in languages with TCO, like Lua, you can hack an application-level stack data structure using tail recursion (and coroutines/threads if you need more than one) that can sometimes be more performant or more convenient than using a native data structure.
There's been a least one experiment (posted a few years ago to HN) where someone benchmarked a stackful coroutine implementation with hundreds of thousands (millions?) of stacks that could grow contiguously on-demand up to, e.g., 2MB, but were initially minimally sized and didn't reserve the maximum stack size upfront. The bottleneck was the VMA bookkeeping--the syscalls, exploding the page table, TLB flushing, etc. In principle it could work well and be even more performant than existing solutions, and it might work better today since Linux 6.13's lightweight guard page feature, MADV_GUARD_INSTALL, but we probably still need more architectural support from the system (kernel, if not hardware) to make it performant and competitive with language-level solutions like goroutines, Rust async, etc.
Re: Allocating on the Stack
#38Earlier quoted context omitted.
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.
What do you mean outside of programmer control? What's stopping you from setting the stack size in the linker flags?
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.
Re: Allocating on the Stack
#39Earlier quoted context omitted.
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 y…
> 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 `/pr…
It's certainly possible on some systems. Even then, you have to fudge, as you don't know exactly how much stack space you need to save for other things.
Stack memory is weird in general. It's usually a fixed amount determined when the thread starts, with the size typically determined by vibes or "seems to work OK." Most programmers don't have much of a notion of how much stack space their code needs, or how much their program needs overall. We know that unbounded non-tail recursion can overflow the stack, but how about bounded-but-large? At what point do you need to start considering such things? A hundred recursive calls? A thousand? A million?
It's all kind of sketchy, but it works well enough in practice, I suppose.
Re: Allocating on the Stack
#40> ...
> On the third loop iteration, the backing store of size 2 is full. append again has to allocate a new backing store, this time of size 4. The old backing store of size 2 is now garbage.
Correct me if I'm wrong, but isn't this a worst-case scenario? realloc can, iirc, extend in place. Your original pointer is still invalid then, but no copy is needed then.
Unless I'm missing something?
Equally, what happens to the ordering of variables on the stack? Is this new one pushed as the last one? Or is there space kept open?
E.g.:
var tasks []task
var other_var int