2

This is my problem in essence. In the life of a function, I generate some integers, then use the array of integers in an algorithm that is also part of the same function. The array of integers will only be used within the function, so naturally it makes sense to store the array on the stack.

The problem is I don't know the size of the array until I'm finished generating all the integers.

I know how to allocate a fixed size and variable sized array on the stack. However, I do not know how to grow an array on the stack, and that seems like the best way to solve my problem. I'm fairly certain this is possible to do in assembly, you just increment stack pointer and store an int for each int generated, so the array of ints would be at the end of the stack frame. Is this possible to do in C though?

akhileshmoghe
  • 603
  • 8
  • 21
Thomas
  • 6,032
  • 6
  • 41
  • 79
  • 1
    Don't. Do it on the heap. – Karoly Horvath Jan 19 '15 at 14:04
  • 2
    Even this hypothetical assembly implementation could only have one growable array per function. This would be too much of a restriction for a C program. – interjay Jan 19 '15 at 14:13
  • ＶＬＡ in C is possible to change the size every time it encounters a Declaration, but it can not operate as your desired because it can not hold the value. such cases In C is expanding by `realloc` the area on the heap. – BLUEPIXY Jan 19 '15 at 14:17

7 Answers7

8

I would disagree with your assertion that "so naturally it makes sense to store the array on the stack". Stack memory is really designed for when you know the size at compile time. I would argue that dynamic memory is the way to go here

sedavidw
  • 11,116
  • 13
  • 61
  • 95
4

C doesn't define what the "stack" is. It only has static, automatic and dynamic allocations. Static and automatic allocations are handled by the compiler, and only dynamic allocation puts the controls in your hands. Thus, if you want to manually deallocate an object and allocate a bigger one, you must use dynamic allocation.

Quentin
  • 62,093
  • 7
  • 131
  • 191
  • This is true. I'm always in two minds when we talk about the call stack because the C Standard only talks about automatic allocations and 'environment' (e.g. ``). But it seems to be lingua franca to refer to the stack. – Persixty Jan 19 '15 at 15:17
2

Don't use dynamic arrays on the stack (compare Why is the use of alloca() not considered good practice?), better allocate memory from the heap using malloc and resize it using realloc.

Community
  • 1
  • 1
Werner Henze
  • 16,404
  • 12
  • 44
  • 69
0

In order to address your issue dynamic memory allocation looks ideal.

int *a = malloc(sizeof(int));

and dereference it to store the value . Each time a new integer needs to be added to the existing list of integers 

int *temp = realloc(a,sizeof(int) * (n+1)); /* n = number of new elements */
if(temp != NULL)
a = temp;

Once done using this memory free() it.

Gopi
  • 19,784
  • 4
  • 24
  • 36
0

The innards of the C compiler requires stack sizes to be fixed or calculable at compile time. It's been a while since I used C (now a C++ convert) and I don't know exactly why this is. http://gribblelab.org/CBootcamp/7_Memory_Stack_vs_Heap.html provides a useful comparison of the pros and cons of the two approaches.

I appreciate your assembly code analogy but C is largely managed, if that makes any sense, by the Operating System, which imposes/provides the task, process and stack notations.

John
  • 6,433
  • 7
  • 47
  • 82
  • Actually, the addition of variable length arrays (VLAs for short) in C99 makes it necessary to allow run-time sizing of stack frames. – Klas Lindbäck Jan 19 '15 at 14:17
  • @KlasLindbäck Far from necessarily. The C Standard clearly permits using free-store allocation for VLAs and even allows you to break `longjmp()` in doing it. See 7.13.2.1/5 here. http://port70.net/~nsz/c/c99/n1256.html#7.13.2.1. Indeed if you think about the shenanigans required to implement multiple variable length arrays and the prospect of how large they could be, I would suggest free-store allocation with concealed C++ style destructor clean-up is the easiest and most natural implementation. – Persixty Jan 19 '15 at 15:23
  • @KlasLindbäck I think that's a disappointment. Introducing a language feature but not making it compatible with all existing constructs makes VLA a little half-baked. However, it's historical record that CFront died because it couldn't implement non-local exception handling. If you have a `longjmp()` compatible free-store allocating VLA you're within a spit of non-local exception handling (i.e. non-local jumps with non-trival stack unwinding). Are so many still extant C compilers equally design limited? – Persixty Jan 19 '15 at 16:18
0

Never Use alloca()

IMHO this point hasn't been made well enough in the standard references.

One rule of thumb is:

If you're not prepared to statically allocate the maximum possible size as a fixed length C array then you shouldn't do it dynamically with alloca() either.

Why? The reason you're trying to avoid malloc() is performance.

alloca() will be slower and won't work in any circumstance static allocation will fail. It's generally less likely to succeed than malloc() too.

One thing is sure. Statically allocating the maximum will outdo both malloc() and alloca(). Static allocation is typically damn near a no-op. Most systems will advance the stack pointer for the function call anyway. There's no appreciable difference for how far.

So what you're telling me is you care about performance but want to hold back on a no-op solution? Think about why you feel like that.

The overwhelming likelihood is you're concerned about the size allocated.

But as explained it's free and it gets taken back. What's the worry? If the worry is "I don't have a maximum or don't know if it will overflow the stack" then you shouldn't be using alloca() because you don't have a maximum and know it if it will overflow the stack.

If you do have a maximum and know it isn't going to blow the stack then statically allocate the maximum and go home. It's a free lunch - remember?

That makes alloca() either wrong or sub-optimal.

Every time you use alloca() you're either wasting your time or coding in one of the difficult-to-test-for arbitrary scaling ceilings that sleep quietly until things really matter then f**k up someone's day.

Don't.

PS: If you need a big 'workspace' but the malloc()/free() overhead is a bottle-neck for example called repeatedly in a big loop, then consider allocating the workspace outside the loop and carrying it from iteration to iteration. You may need to reallocate the workspace if you find a 'big' case but it's often possible to divide the number of allocations by 100 or even 1000.

Footnote: There must be some theoretical algorithm where a() calls b() and if a() requires a massive environment b() doesn't and vice versa. In that event there could be some kind of freaky play-off where the stack overflow is prevented by alloca(). I have never heard of or seen such an algorithm. Plausible specimens will be gratefully received!

Persixty
  • 8,165
  • 2
  • 13
  • 35
  • *If you do have a maximum and know it isn't going to blow the stack then statically allocate the maximum and go home. It's a free lunch - remember?* Ooof. Multiple threaded processes **do** exist. – Andrew Henle Nov 26 '22 at 21:28
  • When you say "static", do you actually mean `static int foo[max];`? Or do you mean using automatic storage with a fixed upper limit like `int foo[max];`? If the latter, "static" is a confusing choice of word to describe using a compile-time constant, because of the other meaning as a 3rd storage class. I think this answer does mean "constant-size automatic storage" since it's talking about compilers moving the stack pointer in prologue/epilogue code (@AndrewHenle), so yeah a large array can just get folded into that. – Peter Cordes Nov 26 '22 at 21:52
  • 1
    One downside to using a fixed max size is that if it's quite large, like a few hundred KiB or even a couple MiB, you're wasting that much memory while this function isn't running, since it won't get handed back to the OS. And it's so far below the old stack memory that you probably get a TLB miss on first access, and a page fault to grow the stack. Of course, a large malloc will be fresh memory from the kernel, too, so it'll also pagefault and TLB miss, but that's something you could avoid with a 128-byte alloca or VLA. – Peter Cordes Nov 26 '22 at 21:55
  • @PeterCordes I mean the second one. Static is overused as a term. In this case I mean 'determined at compile time. Using `alloca()` is by definition no better than the worst case in the worst case. Normally that means your code is really no more scalable than the `int foo[MAX]` case where `MAX` is a compile-time constant. – Persixty Nov 27 '22 at 22:08
  • @AndrewHenle You're missing the point. `Alloca()` is as bad as the worst case in the worst case. That's by definition. Also threads each allocate their own stack so it makes no real difference to the point. – Persixty Nov 27 '22 at 22:10
  • 1
    @Persixty Somewhere in all your misguided certainty you utterly missed things like stack growth and unnecessary page faults - among other things. You could say you missed only one of the points in @PeterCordes' comments. A bad mechanic blames his tools - and `alloca()` is a tool. If using it is beyond **your** ken, that's on you. – Andrew Henle Nov 27 '22 at 23:04
  • My point remains that it `alloca()` doesn't improve scaling except in some exotic cases. It's an execution overhead. It's a tool but not one of general value and quite right not generally recommended or part of the standard set. If you have a use case for it, then please describe it. I asked for one 7 years ago and I do believe they should exist. But in the normal case it's no better than `int foo[MAX]`. – Persixty Nov 27 '22 at 23:12
  • 1
    A max-size stack growth could waste maybe an extra 512KiB of RAM if that was your upper limit, dirtying those pages which will never be used again, vs. if the common case would have only grown by under 4K. You'd pay for page faults the first time, and on systems with stack probes on large growth (e.g. Windows, or GCC hardening against stack-clashes like `-fstack-check` on Linux), growing the stack that much would loop and store every 4k, maybe causing dTLB misses and cache-miss stores. Just to save a few integer insns using the variable size. – Peter Cordes Nov 28 '22 at 02:03
  • 1
    Leaving the extra 512K dirtied long-term is not much of a problem on modern systems; you wouldn't use a limit (or constant size) much higher than that in most cases, especially if this isn't a leaf function and any callers might take the same approach to using large amounts of stack space. I do more or less agree that for correctness, always using the max size should be equivalent to the worst-case VLA, but as I explained last comment, not for performance. (@AndrewHenle). – Peter Cordes Nov 28 '22 at 02:11
  • The other use-case for alloca is that you can do it in a loop, to get multiple small objects on the stack. If you're not doing that, in C you should just use a VLA like `int foo[n];` instead of `int *foo = alloca(n);`, unless there are scoping reasons like only doing the allocation inside an `if` or `else` but wanting it for the rest of the function. – Peter Cordes Nov 28 '22 at 02:12
0

Is there an upper limit on the size? If you can impose one, so the size is at most a few tens of KiB, then yes alloca is appropriate (especially if this is a leaf function, not one calling other functions that might also allocate non-tiny arrays this way).

Or since this is C, not C++, use a variable-length array like int foo[n];.

But always sanity-check your size, otherwise it's a stack-clash vulnerability waiting to happen. (Where a huge allocation moves the stack pointer so far that it ends up in the middle of another memory region, where other things get overwritten by local variables and return addresses.) Some distros enable hardening options that make GCC generate code to touch every page in between when moving the stack pointer by more than a page.

It's usually not worth it to check the size and use alloc for small, malloc for large, since you also need another check at the end of your function to call free if the size was large. It might give a speedup, but this makes your code more complicated and more likely to get broken during maintenance if future editors don't notice that the memory is only sometimes malloced. So only consider a dual strategy if profiling shows this is actually important, and you care about performance more than simplicity / human-readability / maintainability for this particular project.

A size check for an upper limit (else log an error and exit) is more reasonable, but then you have to choose an upper limit beyond which your program will intentionally bail out, even though there's plenty of RAM you're choosing not to use. If there is a reasonable limit where you can be pretty sure something's gone wrong, like the input being intentionally malicious from an exploit, then great, if(size>limit) error(); int arr[size];.

If neither of those conditions can be satisfied, your use case is not appropriate for C automatic storage (stack memory) because it might need to be large. Just use dynamic allocation autom don't want malloc.

Windows x86/x64 the default user-space stack size is 1MiB, I think. On x86-64 Linux it's 8MiB. (ulimit -s). Thread stacks are allocated with the same size. But remember, your function will be part of a chain of function calls (so if every function used a large fraction of the total size, you'd have a problem if they called each other). And any stack memory you dirty won't get handed back to the OS even after the function returns, unlike malloc/free where a large allocation can give back the memory instead of leaving it on the free list.

Kernel thread stack are much smaller, like 16 KiB total for x86-64 Linux, so you never want VLAs or alloca in kernel code, except maybe for a tiny max size, like up to 16 or maybe 32 bytes, not large compared to the size of a pointer that would be needed to store a kmalloc return value.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847