0

In C++ a variable is allocated in the 'Call Stack' ('Stack') or the 'Heap.' Frequently when referring to allocating a variable to the 'Stack', people use the phrase "Push to the Stack."

My issue with this is that the variables allocated to the Stack can be randomly accessed in any order. Therefore, the variables are not being stored in a stack, and the word "Push" should be avoid to avoid ambiguity to its meaning. (I.e. "Push" as in the common stack function, or "Push" as in some other meaning)

Rather, the 'Stack' is a stack with respect to 'Stack Frames' NOT the local variables within the 'Stack Frame.'

Am I correct in thinking that the correct phrase should be "Allocate to the Stack?"

  • 2
    Strictly speaking, even in assembler you often don't push and pop, instead reserving enough space for local use and then accessing every location as needed, afterwards returning everything at once. It's still a stack though, even if you have random access, the defining characteristic being where space is allocated / returned and the ability to address from there. – Deduplicator Oct 3 '16 at 18:39
  • I think the stack that you mean is the definition used in theoretical computer science. Specific implementations can add extra operations other than push and pop - it doesn't matter, all algorithms written with a stack in mind will still work with such structures as long as they support this minimal set of operations. – kamilk Oct 3 '16 at 19:43
7

A Stack is a data structure where you can only add to the end, and only remove from the end, without the ability to manipulate any other item. It doesn't necessarily mean that you can only read the last item in the stack. (Many specific implementation will in fact only allow the last item to be read, but others will allow any item in the stack to be ready, possibly exposing random access by position.)

With respect to the call stack, you can only ever allocate new items on the end of the stack, and only ever deallocate from that same end of the stack, so these operations are in fact semantically identical to the general case "push" and "pop" operations. The fact that the various items in the stack can be read through random access doesn't change any of that.

While it will be the case that, as an implementation detail, multiple items will be pushed and popped from the stack all at once as an optimization, doesn't change the fact that conceptually, you're still pushing and popping from a logical stack. That a stack frame is pushing multiple items when entered, and popping multiple items when exiting, is still consistent with that. Of course if you do think of the stack as pushing and popping entire stack frames that is also meeting all of the criteria of a logical stack, if you prefer to think of it that way, but you don't have to think of it that way.

|improve this answer|||||
  • I was under the impression that, even reading from a stack was restricted to "LIFO" pattern by definition. But then again, I don't recall reading stack values ever being mentioned when defining a stack. I guess I was mistaken in extending the "Push, Pop" requirement for writing values, to include reading values. – M. Evers Oct 3 '16 at 18:51
  • 1
    @M.Evers It's an understandable misconception in that it's not uncommon for a given stack implementation to either expose no reading operation, only only a Peek for the last item, but it's pretty common to expose an iterator allowing one to iterate the whole thing, and not unheard of (and not against the definition of the term) to expose an accessor for random access. – Servy Oct 3 '16 at 18:53
  • Sorry to nitpick, but technically variables on the stack can be written to in random access, not just read. So it kind of does go against your definition. – kamilk Oct 3 '16 at 20:04
  • 1
    @kamilk The structure of the stack itself can only be modified by adding to the end or removing from the end. When you mutate a variable you're not removing it from the collection and then adding it back in. The idea of a stack of mutable objects is not, by definition, contradictory. – Servy Oct 3 '16 at 20:06
1

C, and C++ (prior to C++11) use the optional keyword auto for local variables. auto meaning automatic, which is to say these variables are created automatically by entering into the scope in which they are declared, and destructed automatically by exiting out of that scope.

(With C++11 the keyword auto has been given new meanings.)

Am I correct in thinking that the correct phrase should be "Allocate to the Stack?"

Because local variables are automatically allocated, constructed, destructed and freed, I would prefer to simply call them "local variables" (in common vernacular) or automatic variables (in old C/C++ language terminology), but if I had to, I'd say "allocated on the stack".

When someone talks about "pushing (on)to the stack", for me at least, it evokes the notion of parameter passing, since with (parts of) many calling conventions, passing an actual argument may be done by such a push operation, especially when parameters overflow the argument registers. Such pushing is often ordered as are the actual arguments / formal parameters.

Though one problem will all of this is that a good compiler will prefer registers over memory when possible. A compiler is also free to sometimes use a register and other times use memory for the same variable, as long is it can keep that all straight (i.e. doesn't make some kind of error in doing that). It may reuse the same memory or the same register(s) for different local variables if it can determine their lifetime does not overlap.

So, sometimes local variables don't even get any stack space allocated at all because it is allocated to registers or reusing some existing memory.

I say the best terminology is to just call them local variables, or to describe them as declared locally.

|improve this answer|||||
1

Automatic variables in C aren't pushed, allocated or anything like that; the best phrase I can think of to describe the process is "made room for." The fact that the stack is involved is an implementation detail which, while popular, is not mandated by the language.

The compiler knows how much space is going to be taken up by the automatic variables in a block because they have to be declared. On entry, the compiler will push* the contents of any registers it plans to overwrite and then nudge the stack pointer by enough bytes to hold the automatics.** The gap left in the stack gets treated like a struct, with each automatic having a known offset relative to the stack pointer, which will always be in the same place when that block is running.

Purists will correctly point out that this behavior as an abuse of the stack as a data structure. When you're writing assembly, there really is no such thing. The stack pointer is just a place to hold an address, and nothing stops the running code from looking anywhere in the stack. It sounds dangerous, but that's why we try to let smart people write compilers: they're disciplined enough to use the chainsaw to do good things without removing a limb that should have stayed on.


*The compiled code may not actually use the processor's PUSH instruction to do this. It may adjust the stack pointer and do stores relative to it; which is the same method being described here for automatics.

**This is subject to optimizations; not all automatics need actual memory and can be held in a register if the compiler deems that okay.

|improve this answer|||||
1

It is a metaphore that works well as a model for calling subroutines, passing arguments and returning to the point of the call. The stack concept in this context does not so much stand for the physical qualities of the implementation, it models the logical sequence of events. It illustrates that keeping track of a single stack pointer allows you to nest subroutine calls in an easily controlled manner.

If you look close enough at an implementation, any abstraction will break down. It will also get you further away from essence of the matter though. The stack metaphore makes sense as long as you focus on program execution. If you focus on storing data instead, you may see a different abstraction like the geographical one that talks about local and global variables.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.