1

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
  • 583
  • 7
  • 21
Thomas
  • 5,698
  • 3
  • 38
  • 68
  • 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

6 Answers6

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
  • 10,038
  • 12
  • 53
  • 88
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
  • 60,592
  • 7
  • 125
  • 183
  • 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
  • 15,667
  • 12
  • 43
  • 65
1

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
  • 6,928
  • 2
  • 11
  • 32
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,679
  • 4
  • 22
  • 35
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,135
  • 6
  • 43
  • 77
  • 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