Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Allocating on the Stack

go.dev

Post reply on HN
Print view View original

41–50 of 59 posts

Re: Allocating on the Stack

#41

Post by cyberax »

spacechild1 wrote: post #7
HarHarVeryFunny wrote: post #2

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 point…

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…

> alloca() is super useful, but it's also quite dangerous because you can easily overflow the stack.

This is not a problem for Go, because it has resizable stacks.

Re: Allocating on the Stack

#42

Post by spacechild1 »

wat10000 wrote: post #39
12_throw_away wrote: post #16

Earlier quoted context omitted.

> 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 thei…

Personally, I only use alloca() if:

1. I know that the function will never be called recursively and

2. the total amount of stack allocation is limited to a few kilobytes at most.

alloca() is more problematic on embedded platforms because default stack sizes tend to be tiny. Either document your stack usage requirements or provide an option to disable all calls to alloca(). For example, Opus has the OPUS_NONTHREADSAFE_PSEUDOSTACK option.

Re: Allocating on the Stack

#43

Post by karel-3d »

tptacek wrote: post #15
anematode wrote: post #10

Awesome stuff! Does Go have profile-guided optimization? I'm wondering whether a profile could hint to the compiler how large to make the pre-reserved stack space.

Yep. `go build -pgo=foo.pprof` https://go.dev/doc/pgo

I never noticed much difference with using pgo even after taking a very long real life profile. All the machinery required to get it and put it to CI was never worth the speed-up. Of course YMMV.

Re: Allocating on the Stack

#44

Post by fsckboy »

csjh wrote: post #36

Optimizations like these are so cool. I love seeing higher level languages take advantage of their high level-ness

you can do this in C, you just need to let its low level-ness be at the same level as everything else you do, just a setjmp longerjmp

Re: Allocating on the Stack

#45

Post by matthewaveryusa »

It's kind of like the small string optimization you see in C++[1] where all the string metadata to account for heap pointer, size and capacity is union'ed with char*. Getting the stack allocation doesn't costs extra memory, but does cost a bit check. Not sure if slices in go use the same method. 32 bytes is a lot so maybe they fattened slice representations a bit to get a bit more bang for your buck?

[1] https://github.com/elliotgoodrich/SSO-23

Re: Allocating on the Stack

#46

Post by kbolino »

OptionOfT wrote: post #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 ability to grow without copying is already part of how slices work. Every slice is really a 3-word tuple of pointer, length, and capacity. If not explicitly set with make, the capacity property defaults to a value that fills out the size class of the allocation. It just so happens that, in this case, the size of the Task type doesn't allow for more than 1 value to fit in the smallest allocation. If you were to do this with a []byte or []int32 etc., you would see that the capacity doesn't necessarily start at 1: https://go.dev/play/p/G5cifdChGIZ

Re: Allocating on the Stack

#47

Post by [deleted] »

OptionOfT wrote: post #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…

[deleted]

Re: Allocating on the Stack

#49

Post by up2isomorphism »

HarHarVeryFunny wrote: post #2

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 point…

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.

Re: Allocating on the Stack

#50

Post by KolmogorovComp »

bertylicious wrote: post #5

Nice! That's (seems) so simple yet also so very effective. Shouldn't other memory-managed languages be able to profit from this as well?

It’s a very well known pattern, as someone else mentioned it’s used in CPP in smallstring, Rust smallvec, C usually hand rolled etc.
Post reply on HN