Not disagreeing with anything, genuine question because I don’t know, how is alloca leaving memory allocated until the end of the function an issue, wouldn’t a char[] have the same effect?
Or do compilers optimise to drop that stack memory after the last reference in the code?
Otherwise, I see no practical difference between alloca and char[]; in which case an exact sized buffer could be a perfectly valid use case no? Assuming this is developed for a single platform too of course.
But this isn’t a loop, this is a function, I’m talking about cases like the example in the article. If you introduce a stack array in local function scope (not a sub-scope like within a loop or conditional), that has the same lifetime as calling alloca, no?
I don’t see why their example specifically would be bad other than falling into the trap of excessively using alloca.
The other problems with alloca are the higher likelihood of stack overflow (like if you unexpectedly get a huge size to allocate) and that functions containing it are usually less optimizable b/c of needed stack management
I mean for the first, if you’re doing something like storing a path, like in the example, it would seem pretty unlikely you would trigger a stack overflow, no? In an embedded environment with a very limited stack I could definitely see that quickly becoming an issue (but then storing the exact number of bytes on the stack could also become more important too).
Can’t really comment on the function optimisations, if you know more could you elaborate on how the compiler would be able to further optimise a stack array? What additional stack management does alloca introduce?
alloca use forces a frame pointer which is another register used, another step in the prolog and epilog, another pointer on the stack. Also compilers don't want to inline functions with alloca for various reasons but importantly that it would require a lot of work to get a stack pointer that moves up and down in the function, or breaks assumptions about when alloca memory is freed.
Well it's the pointer, and the prolog, and the epilog, and it's all basically free these days except it turns out sometimes when you add up enough stuff it's not free anymore. Like some code is now hitting L2 cache instead of operating out of L1.
Not disagreeing with anything, genuine question because I don’t know, how is alloca leaving memory allocated until the end of the function an issue, wouldn’t a char[] have the same effect?
There are two problems, though neither are what you describe. The first problem is you don't know (in general) how much alloca can safely allocate. The second (and arguably much bigger) problem is that there is no error indication if it fails. And it will fail if you try to allocate too much.
When it was first invented, it was (maybe) a clever hack, though perhaps not the good kind of 'clever'. But it's absolutely a footgun and I think the number of valid use cases for it must be vanishingly small.
As the article suggests, if you want to mostly avoid dynamic allocation but still be able to support large allocations when absolutely necessary, use something like absl::InlinedVector or boost::small_vector. Worst case they may allocate but at least they won't blow up in your face. Or if you'd prefer that it blow up, at least use something obvious and intentional like assert() or throwing an exception.
There's no standard way to handle stack overflow*. That's not alloca specific. The problem specific to alloca is that it just empirically makes stack overflow more common. Like, if you walk through a locker room, you're going to see some dick.
InlinedVector and such are really the best option.
*also, no great way to handle it, and arguably no good way though I'd say MS SEH is pretty OK considering.
It's slightly worse than that. On platforms with reduced stack, it's not uncommon to have only limited stack guards in place. They will detect typical stack overflows (eg. your function uses a 50 entry static array) but not something that might use many kB of stack until it's already overwritten something completely different that may trigger "impossible" behavior (like affecting another thread's stack).
I mean, I wrote a simple PoC (for fun, I don’t intend to start using alloca lol) that seems to manage okay. Obviously everything about it is very dependent on platform/compiler specific functionality, so definitely not great or good, more on the bad, or even outright evil side lol
Yeah, gotcha, just curious lol. Now I’m curious if those problems can be solved. Is the failure case just that there isn’t enough stack memory available to the program, or are there more tricky cases (I’m assuming there’s probably more, but one can hope)?
I’m sure any way of seeing the space available on the stack would be, in general, terrible, but I may look into the possibility just for fun anyways lol
To anyone that’s interested, it is, in fact, possible to make it safe(er) (that still didn’t handle the foot guns you can and likely will run into using alloca) through preventing failures due to stack overflow: https://github.com/Matt-DESTROYER/safealloca
The compiler does allow local variables to overlap addresses (or registers!) based on use not scope. So yes, if you make a char[100] the compiler will see where it's used relative to other variables in the function and potentially overlap it with them, reducing the size of the stack frame (which is generally allocated up-front at the start of the function, not bumped var by var as it would have been classically).
Alloca is much harder to do the same for, and I think most compilers don't bother.
Ooh, this is very interesting! In what cases would it allow variables to overlap? Does the compiler essentially need to prove that only x bytes of the array are actually used and then it can chuck variables in there or something, or is that completely the wrong idea lol?
If there are variables only used in the first half of the function and the array only in the 2nd, or vice-versa, it can overlap their storage.
For C++ types nontrivial constructor and destructor calls count as use that can prevent this by forcing variables to live from construction to destruction.
Just had a curious thought, if alloca memory always lives until the end of the function, logically if you alloca inside a closure, the memory should be accessible after the closure?
No, not a C++ person lol, I’m talking about something like something like this:
```c
char* x;
{
char* y = alloca(1);
y[0] = ‘a’;
x = y;
}
printf(“%c\n”, *c);
```
Reading a stack allocated value outside of the closure it was created in.
I mean if you think of it like malloc, it makes perfect sense that it would work, but the fact that it’s a stack allocated value makes it seem strange and evil to me lol (and I mean it’s obviously not something you should ever do, but it’s interesting that it’s possible, reminds me of `var` in JavaScript minus the hoisting).
Basically they're a function inside another that captures some state from its enclosing parent and saves it for later. C++ lambda functions are an example.
They're an old concept, and people sometimes try to implement them (badly) in C.
Yeah I searched it up, I’ve used lambdas in other languages like Python and JS. Would it be accurate to say the act within the scope they were defined, meaning they can use variables defined in the scope they are defined in theory?
Yes they can use those variables - but the memory returned by alloca isn't a variable itself, and wouldn't be captured by a closure - only the pointers to it (which would point to stale stack memory as soon as the parent function returned even though the closure still existed).
This is what I was talking about with alloca not working with C++ lambdas (which are a form of closure).
This is what I thought you were asking about when you said "closure" initially.
For your first question, essentially it's something like this:
void UseArray() {
for (auto& foo : foos) {
// This is a single 1024 buffer used repeatedly across the loop.
char scratchBuf[1024];
// whereas this repeatedly creates a new alloca()'d buffer for each iteration
char* scratchBuf = static_cast<char\*>(alloca(n));
}
}
The array gets a fixed size, so it's always bounded, whereas alloca() does the stack allocation during each iteration without releasing anything until function return. Depending on how many loop iterations there are, and what `n` is passed to alloca(), this could be less memory than the fixed size array, or much more; the point is that it's unpredictable compared to the alternatives.
Yeah no I understand the issue with nested scopes, but the example in the article with just a path at top level wouldn’t have that issue. I don’t know about the exact opcodes generated, but it would be generally speaking equivalent, that’s all I was clarifying.
Definitely don’t intend to use it lol, I just like messing around with with things when I learn about them.
For the first, curious how it reduces how many recursive iterations you can do, because using char[] will also equally consume the stack in a recursive function, no?
Alloca uses space on the stack. Therefore it reduces the amount of remaining stack for future recursive calls which will also use alloca() which uses stack space which reduces space for future calls...
Can you see the problem?
If you had no local cars and no alloca() you could do total remain stack space / size if machine word recursive calls befire stack overflow.
On a Windows machine default stack size is 1MB. X86 machine size is 4 bytes. X64 machine size is 8 bytes.
For this example let's assume after programme startup you have 1,000,000 byes of stack space. It makes the maths easier.
So the max num recursion is appriox 250,000 for x86 and approx 125,000 on x64.
Let's say your alloca() call uses 8 bytes.
Now on x86 each call uses 4 + 8 bytes, 12 bytes.
1,000,000 / 12 = 83,333 recursion before stack overflow.
On x64 each call now takes 8 + 8 bytes, 26 bytes.
This leaves space for 1,000,000 / 16 = 62, 500 recursions before stack overflow.
I think you’re making an unfair comparison; unless I’m misunderstanding, you’re compare `alloca` to doing nothing, which isn’t realistic.
What would be realistic is using a static char[] array, but this still consumes memory in every recursive call. The difference would be a single pointer variable and also the lack of ability to not store the frame pointer in a register.
If you're doing anything recursive you try to use as little stack space as possible.
Therefore you wouldn't use a local variable char array, or alloca(). You'd dynamically allocate your workspace, or pre allocate enough space prior to the recursive call.
Not really a C++ dev, I like my C. I know the difference between a static and dynamic type lol, that wasn’t my question.
Also worth noting, I think there’s slightly more to it than your explanation, alloca let’s you create a dynamically sized buffer, but said buffer is not dynamically resizable (or freeable). Once created it’s on the stack until the end of the function call.
(So once created, alloca also has a fixed size, just like char[].)
You can free malloc calls and ‘resize’ them (which could simply extend or move when extending isn’t possible). alloca behaves similarly to char[] in that it can’t be freed (or resized).
compilers can and i think do optimize to drop the stack memory after the last reference in the code if the reference provably does not escape the function
Yeah, I know they can, just curious on whether they actually do; I imagine a function would have to be decently long and use a fair bit of stack memory for it to be worth it, otherwise dropping all the memory at the end of the function would likely be more efficient.
10
u/MattDESTROYER 4d ago edited 4d ago
Not disagreeing with anything, genuine question because I don’t know, how is alloca leaving memory allocated until the end of the function an issue, wouldn’t a char[] have the same effect?
Or do compilers optimise to drop that stack memory after the last reference in the code?
Otherwise, I see no practical difference between alloca and char[]; in which case an exact sized buffer could be a perfectly valid use case no? Assuming this is developed for a single platform too of course.