C arrays on stack

Question

In c (and c++), one can create an integer array in the following ways:

int a[const];

Where const is a compile-time constant, or

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

According to my understanding, the first allocates the memory on stack, and the second on the heap. Now, as far as i know, memory on the stack is ordered such that the program can pop it off the top as needed. This would imply that the elements in the array are not necessarily stored sequentially, which sound odd.

What, precisely, is happening here?

Edit:

Thanks for the replies guys. With your answers and some follow up Googling i found the source of my confusion. I was assuming that the program would only really use the top variable of the stack, and pop them on/off one by one.

Why wouldn't the elements be stored sequentially? How else would they be stored? — Lasse V. Karlsen, Dec 25 '17 at 22:45
@Anton Quelle It is unclear why you made the following resume: "This would imply that the elements in the array are not necessarily stored sequentially" — Vlad from Moscow, Dec 25 '17 at 22:48
once `a` is passed to a function, there's no way of telling what's the origin of the pointer, so the mechanism _has_ to be the same. So it's the same. — Jean-François Fabre, Dec 25 '17 at 22:51
There's no guarantee stack will be in a contiguous physical memory. — Tony Tannous, Dec 25 '17 at 22:51
Elements of an array are always stored sequentially (and contiguously!). Management of lifetime of the array is a completely different thing. Also "heap" and "stack" have been inaccurate descriptions for a little while now (20 years or more). — Peter, Dec 25 '17 at 23:15
*"This would imply that the elements in the array are not necessarily stored sequentially, which sound odd."* - this is a rather surprising conclusion. How did you come to this implication? What made you believe that regular stack-based lifetime rules of C would require non-sequantial storage of array elements? You need to clarify that, since without it your question is unclear. I don't see any difference between array or any other local object (e.g. an `int` can be seen as an "array" of bytes). So, why do you see an `int[42]` array as something different from any other local object? — AnT stands with Russia, Dec 26 '17 at 01:07
The stack of the processor does not act as a true stack data structure. It is possible to allocate an arbitrary amount of storage for each stack element. Which a function does when it is entered, reserving space for its local variables. Like that array. That storage is contiguous. — Hans Passant, Dec 26 '17 at 01:16
In C [you don't cast the result of `malloc`](http://stackoverflow.com/q/605845/995714) and you can't use a declared `const` inside brackets in an array declaration — phuclv, Dec 26 '17 at 02:41

score 8 · Answer 1 · answered Dec 26 '17 at 01:15

While abstract C language does not say how local objects are allocated (i.e. there's no explicit references to "stack" language specification), the storage duration of local objects is well aligned with LIFO properties of stacks: local objects are destroyed in the reverse order of their creation. Object that are created last are destroyed first and vice versa.

This principle applies uniformly to all local objects. Arrays are no exception. Every array is just an appropriately sized block of contiguous memory bytes (which, BTW, is true for objects of any type). There's nothing special about arrays. There's no reason to store array elements non-sequentially.

Every array object is created in its entirety on top of the stack. And when array object reaches the end of its storage duration, it is simply "popped off the top", just like you said. Anything that could have possibly resided above it in the stack should have already been popped off by that moment.

I voted this up because it is the only answer so far that addresses some confusion the OP seems to have. Their questions suggests they think the individual elements of the array might be pushed onto the stack in the order they are first assigned values, and this answer says an array object is created in its entirety. I think expanding on that a little more could be helpful to clarify for the OP how things work. — Eric Postpischil, Dec 26 '17 at 01:28

score 3 · Accepted Answer · answered Dec 25 '17 at 23:11

3

You may be misunderstanding something.

In fact, the stack will always be sequential storage. The stack, however, will be far more limited in size than the heap. While it is true that things are "popped" off of the stack, this will effectively not apply within the function where the local array is declared.

The heap, on the other hand, can grow. When running out of memory, malloc implementations will call sbrk() to request additional memory. This means that, overall, the heap need not be contiguous, though when you call malloc or realloc, you can be confident that the memory will be at least as large as what you have requested and that the addresses will be sequential (at least, from your point of view).

answered Dec 25 '17 at 23:11

David Hoelzer

15,862
4
48
67

Can you cite a reference which explicitly says the stack has to be contiguous ? – Tony Tannous Dec 25 '17 at 23:47
@TonyTannous can you cite a reference that C *has* a stack? – Weather Vane Dec 26 '17 at 00:04
@TonyTannous No, But in 40 years of C programming I've never seen a platform where, from the perspective of the C program, if the platform uses a stack, the stack isn't contiguous; it seems a pretty safe bet as a convention. – David Hoelzer Dec 26 '17 at 00:17
Plus one for mentioning that popping off the stack doen not occur within a function – Anton Quelle Dec 26 '17 at 08:27

score 0 · Answer 3 · edited Dec 26 '17 at 02:28

There are 3 main memory types in programming: static memory, heap and stack.

Static memory is used to allocate all 'static' variables, i.e. variables declared in global scope or declared as static in functions. This means that the number of static variables and their size is known at compilation time and compiler just reserves memory for them.

Heap is a dynamic memory pool where you can borrow memory when you need it and return the memory to it. So, when you borrow memory, i.e. 'malloc' it, you can use it as you wish till you return (free) it so that it could be reused by a different piece of the program.

The stack is a special memory region, used to allocate local variables for functions. When you call a function which has non-static local variables, it will allocate enough space for those variables in the memory (plus additional space needed for the function's needs). When you return from the function, the memory gets automatically return to the system for reuse in another function call.

In your case, the first declaration could either be a static variable or could be a local function variable. Depending on this it could be allocated in one of those pools. The second case borrows memory from heap.

Usually every single variable occupies contiguous space in memory. It does not matter which type of the memory it is. Array is such a variable which occupies a memory region. The order in which data is put in memory itself depends on architecture. The task of the compiler is to give you a standard view of the variables, i.e. array[0] should contain data for array[0] and pointer arithmetic should work in the standard way.

So, in practice all elements of an array are stored sequentially. If not, it will not alter anything in the programming. Though I have not seen a case where they would not be as such.

C arrays on stack

3 Answers3