12

The stack pointer points to the top of the stack, which stores data on what we call a "LIFO" basis. To steal someone else's analogy, it's like a stack of dishes in which you put and take dishes at the top. The stack pointer, OTOH, points to the top "dish" of the stack. At least, that's true for x86.

But why does the computer/program "care" what the stack pointer's pointing to? In other words, what purpose does having the stack pointer and knowing where it points to serve?

An explanation understandable by C programmers would be appreciated.

6
  • Because you can't see the top of the stack in ram like you can see the top of a stack of dishes.
    – tkausl
    Dec 4, 2015 at 9:59
  • 1
  • 8
    You do not take a dish from the bottom of a stack. You add one on top and someone else takes it from the top. You're thinking of a queue here. Dec 4, 2015 at 10:04
  • @Snowman Your edit seems to change the meaning of the question. moonman239, can you verify if Snowman's change is accurate, specifically the addition of "What purpose does this stack actually serve, as opposed to explaining its structure?"
    – 8bittree
    Dec 4, 2015 at 19:47
  • 1
    @8bittree Please see the edit description: I copied the question as stated in the subject line into the body of the question. Of course, I am always open to the possibility that I altered something and the original author is always free to roll back or otherwise edit the post.
    – user22815
    Dec 4, 2015 at 19:55

9 Answers 9

24

What purpose does this stack actually serve, as opposed to explaining its structure?

You have many answers which accurately describe the structure of the data stored on the stack, which I note is the opposite of the question you asked.

The purpose that the stack serves is: the stack is part of the reification of continuation in a language without coroutines.

Let's unpack that.

Continuation is simply put, the answer to the question "what is going to happen next in my program?" At every point in every program something is going to happen next. Two operands are going to be computed, then the program continues by computing their sum, and then the program continues by assigning the sum to a variable, and then... and so on.

Reification is just a highfalutin word for making a concrete implementation of an abstract concept. "What happens next?" is an abstract concept; the way the stack is laid out is a part of how that abstract concept is turned into a real machine that really computes things.

Coroutines are functions that can remember where they were, yield control to another coroutine for a while, and then resume where they left off later, but not necessarily immediately after the just-called coroutine yields. Think of "yield return" or "await" in C#, which must remember where they were when the next item is requested or the asynchronous operation completes. Languages with coroutines or similar language features require more advanced data structures than a stack in order to implement continuation.

How does a stack implement continuation? Other answers say how. The stack stores (1) values of variables and temporaries whose lifetimes are known to be not greater than the activation of the current method, and (2) the address of the continuation code associated with the most recent method activation. In languages with exception handling the stack may also store information about the "error continuation" -- that is, what the program will do next when an exceptional situation occurs.

Let me take this opportunity to note that the stack does not tell you "where did I come from?" -- though it is often so used in debugging. The stack tells you where you are going to next, and what the values of the activation's variables will be when you get there. The fact that in a language without coroutines, where you are going next is almost always where you came from makes this kind of debugging easier. But there is no requirement that a compiler store information about where control came from if it can get away without doing so. Tail-call optimizations for example destroy information about where the program control came from.

Why do we use the stack to implement continuation in languages without coroutines? Because the characteristic of synchronous activation of methods is that the pattern of "suspend the current method, activate another method, resume the current method knowing the result of the activated method" when composed with itself logically forms a stack of activations. Making a data structure that implements this stack-like behaviour is very cheap and easy. Why is it so cheap and easy? Because chip sets have been for many decades specifically designed to make this sort of programming easy for compiler writers.

2
  • Note that the quote you reference was mistakenly added in an edit by another user and has since been corrected, making this answer not quite address the question.
    – 8bittree
    Jun 8, 2016 at 16:03
  • 5
    I'm pretty certain an explanation is supposed to increase clarity. I'm not entirely convinced that "the stack is part of the reification of continuation in a language without coroutines" comes even close to that :-)
    – user10776
    Jan 11, 2017 at 8:23
5

LIFO vs FIFO

LIFO stands for Last In, First Out. As in, the Last item put Into the stack is the First item taken out of the stack.

What you described with your dishes analogy (in the first revision), is a queue or FIFO, First In, First Out.

The major difference between the two, being that the LIFO/stack pushes (inserts) and pops (removes) from the same end, and a FIFO/queue does so from opposite ends.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

The stack pointer

Let's take a look at what's happening under the hood of the stack. Here's some memory, each box is an address:

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

And there's a stack pointer pointing at the bottom of the currently empty stack (whether the stack grows up or grows down isn't particularly relevant here so we'll ignore that, but of course in the real world, that does determine which operation adds, and which subtracts from the SP).

So let's push a, b, and c again. Graphics on the left, "high level" operation in the middle, C-ish pseudo code on the right:

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

As you can see, each time we push, it inserts the argument in the location the stack pointer is currently pointing, and adjusts the stack pointer to point at the next location.

Now let's pop:

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Pop is the opposite of push, it adjusts the stack pointer to point at the previous location and removes the item that was there (usually to return it to whoever called pop).

You probably noticed that b and c are still in memory. I just want to assure you that those are not typos. We'll return to that shortly.

Life without a stack pointer

Let's see what happens if we don't have a stack pointer. Starting with pushing again:

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

Er, hmm... if we don't have a stack pointer, then we can't move something to the address it points to. Maybe we can use a pointer that points to the base instead of the top.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

Uh oh. Since we can't change the fixed value of the stack's base, we just overwrote the a by pushing b to the same location.

Well, why don't we keep track of how many times we've pushed. And we'll also need to keep track of the times we've popped.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

Well it works, but it's actually pretty similar to before, except *pointer is cheaper than pointer[offset] (no extra arithmetic), not to mention it's less to type. This seem like a loss to me.

Let's try again. Instead of using the Pascal string style of finding the end of an array-based collection (tracking how many items are in the collection), let's try the C string style (scan from the beginning to the end):

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

You may have already guessed the problem here. Uninitialized memory is not guaranteed to be 0. So when we look for the top to place a, we end up skipping over a bunch of unused memory location that have random garbage in them. Similarly, when we scan to the top, we end up skipping well beyond the a we just pushed until we finally find another memory location that just happens to be 0, and move back and return the random garbage just before that.

That's easy enough to fix, we just have to add operations to Push and Pop to make sure the top of the stack is always updated to be marked with a 0, and we have to initialize the stack with such a terminator. Of course that also means we can't have a 0 (or whatever value we pick as a terminator) as an actually value in the stack.

On top of that, we've also changed what were O(1) operations into O(n) operations.

TL;DR

The stack pointer keeps track of the top of the stack, where all of the action occurs. There are ways to sort of get rid of it (bp[count] and top are essentially still the stack pointer), but they both end up being more complicated and slower than simply having the stack pointer. And not knowing where the top of the stack is means you can't use the stack.

Note: The stack pointer pointing to the "bottom" of the runtime stack in x86 might be a misconception related to the entire runtime stack being upside down. In other words, the base of the stack is placed at a high memory address, and the tip of the stack grows down into lower memory addresses. The stack pointer does point to the tip of the stack where all the action occurs, just that tip is at a lower memory address than the base of the stack.

4

Most basic use of stack is to store return address for functions:

void a(){
    sub();
}
void b(){
    sub();
}
void sub() {
    //should i got back to a() or to b()?
}

and from C point of view this is all. From compiler point of view:

  • all function arguments are passed by CPU registers - if there is not enough registers the arguments will be put on stack
  • after function ends (most) registers should have same values as before entering it - so used registers are backed up on stack

And from OS point of view: program can be interrupted any time so after we are done with system task we have to restore CPU state, so lets store everything on stack

All of this works since we don't care how much items are already on stack or how many items someone else will add in future, we just need to know how much we moved the stack pointer and restore it after we are done.

1
  • 1
    I think it is more accurate to say that arguments are pushed on the stack, though often as an optimization registers are used instead on processors that have enough free registers for the task. That's a nit, but I think it matches better how the languages have evolved historically. The earliest C/C++ compilers didn't use registers at all for this. Dec 4, 2015 at 17:53
2

The stack pointer is used (with the frame pointer) for the call stack (follow the link to wikipedia, where there is a good picture).

The call stack contains call frames, which contain return address, local variables and other local data (in particular, spilled content of registers; formals).

Read also about tail calls (some tail-recursive calls don't need any call frame), exception handling (like setjmp & longjmp, they may involve popping many stack frames at once), signals & interrupts, and continuations. See also calling conventions and application binary interfaces (ABIs), in particular the x86-64 ABI (which defines that some formal arguments are passed by registers).

Also, code some simple function(s) in C, then use gcc -Wall -O -S -fverbose-asm to compile it, and look into the generated .s assembler file.

Appel wrote an old 1986 paper claiming that garbage collection can be faster than stack allocation (using Continuation-Passing Style in the compiler), but this is probably false on today's x86 processors (notably because of cache effects).

Notice that calling conventions, ABIs, and stack layout are different on 32 bits i686 and on 64 bits x86-64. Also, calling conventions (and who is responsible for allocating or popping the call frame) may be different with different languages (e.g. C, Pascal, Ocaml, SBCL Common Lisp have different calling conventions ....)

BTW, recent x86 extensions like AVX are imposing increasingly large alignment constraints on the stack pointer (IIRC, a call frame on x86-64 wants to be aligned to 16 bytes, i.e. two words or pointers).

1
  • 1
    You might want to mention that aligning to 16 bytes on x86-64 means twice the size/alignment of a pointer, which is actually more interesting than the byte-count. Dec 4, 2015 at 19:01
2

Modern programming languages, as you well know, support the concept of subroutine calls (most often called "function calls"). This means that:

  1. In the middle of some code, you can call some other function in your program;
  2. That function doesn't explicitly know where it was called from;
  3. Nevertheless, when its work is done and it returns, control goes back to the exact point where the call was initiated, with all the local variable values in effect as when the call was initiated.

How does the computer keep track of that? It maintains an ongoing record of which functions are waiting for which calls to return. This record is a stack—and since it's such an important one, we normally call it the stack.

And since this call/return pattern is so important, CPUs have long been designed to provide special hardware support for it. The stack pointer is a hardware feature in CPUs—a register that's exclusively dedicated to keeping track of the top of the stack, and used by the CPU's instructions for branching into a subroutine and returning from it.

1

In simple terms, the program cares because it's using that data and needs to keep track of where to find it.

If you declare local variables in a function, the stack is where they are stored. Also, if you call another function, the stack is where it stores the return address so it can get back to the function you were in when the one you called is finished and pick up where it left off.

Without the SP, structured programming as we know it would be essentially impossible. (You could work around not having it, but it would pretty much require implementing your own version of it, so that's not much of a difference.)

5
  • 1
    Your assertion that structured programming without a stack would be impossible is false. Programs compiled into continuation passing style consume no stack, but they are perfectly sensible programs. Dec 4, 2015 at 18:53
  • @EricLippert: For values of "perfectly sensible" sufficiently nonsensical that they include standing on one's head and turning oneself inside out, perhaps. ;-) Dec 4, 2015 at 20:06
  • 1
    With continuation passing, it is possible to not need a call stack at all. Effectively, every call is a tail call and goto rather than return. "As CPS and TCO eliminate the concept of an implicit function return, their combined use can eliminate the need for a run-time stack."
    – user40980
    Dec 4, 2015 at 20:21
  • @MichaelT: I said "essentially" impossible for a reason. CPS can theoretically accomplish this, but in practice it becomes ridiculously difficult very quickly to write real-world code of any complexity in CPS, as Eric pointed out in a series of blog posts on the subject. Dec 4, 2015 at 20:26
  • 1
    @MasonWheeler Eric is talking about programs compiled into CPS. For example, quoting Jon Harrop's blog: In fact, some compilers don’t even use stack frames [...], and other compilers like SML/NJ convert every call into continuation style and put stack frames on the heap, splitting every segment of code between a pair of function calls in the source into its own separate function in the compiled form. That's different from "implementing your own version of [the stack]".
    – Doval
    Dec 4, 2015 at 22:22
1

For the processor stack in an x86 processor, the analogy of a stack of dishes is really inaccurate.
For various reasons (mostly historical), the processor stack grows from the top of memory towards the bottom of memory, so a better analogy would be chain of chain links hanging from the ceiling. When pushing something onto the stack, a chain link gets added to the lowest link.

The stack pointer refers to the lowest link of the chain and is used by the processor to "see" where that lowest link is, so that links can be added or removed without having to travel the entire chain from the ceiling down.

In a sense, inside a x86 processor, the stack is upside down but normal stack-terminology sill gets used, so that lowest link gets referred to as being the top of the stack.


The chain links that I referred to above are actually memory cells in a computer and they get used to store local variables and some intermediate results of computations. Computer programs care where the top of the stack is (i.e. where that lowest link hangs), because the large majority of variables that a function needs to access exist close to where the stack pointer is referring to and fast access to them is desirable.

6
  • 1
    The stack pointer refers to the lowest link of the chain and is used by the processor to "see" where that lowest link is, so that links can be added or removed without having to travel the entire chain from the ceiling down. I'm not sure this is a good analogy. In reality links never get added or removed. The stack pointer is more like a bit of tape you use to mark one of the links. If you lose that tape, you won't have a way to know which was the bottom-most link you used at all; traveling the chain from the ceiling down wouldn't help you.
    – Doval
    Dec 4, 2015 at 13:33
  • So the stack pointer provides a reference point the program/computer can use to find the local variables of a function?
    – moonman239
    Dec 4, 2015 at 17:59
  • If that's the case, then how does the computer find the local variables? Does it just go searching every memory address from the bottom up?
    – moonman239
    Dec 4, 2015 at 18:06
  • @moonman239: No, when compiling, the compiler keeps track of where each variable is stored relative to the stack pointer. The processor understands such relative addressing to give direct access to the variables. Dec 4, 2015 at 18:17
  • 1
    @BartvanIngenSchenau Ah, OK. Kind of like when you're out in the middle of nowhere and you need help, so you give 911 an idea of where you are relative to a landmark. The stack pointer, in this case, is usually the nearest "landmark" and therefore, perhaps, the best reference point.
    – moonman239
    Dec 4, 2015 at 20:13
1

This answer refers specifically to the stack pointer of the current thread (of execution).

In procedural programming languages, a thread typically has access to a stack1 for the following purposes:

  • Control flow, namely "call stack".
    • When one function calls another function, the call stack remembers where to return to.
    • A call stack is necessary because this is how we want a "function call" to behave - "to pick up where we left off".
    • There are other programming styles that do not have function calls in the middle of execution (e.g. only allowed to specify the next function when the end of the current function is reached), or have no function calls at all (only using goto and conditional jumps). These programming styles might not need a call stack.
  • Function call parameters.
    • When a function calls another function, parameters can be pushed onto the stack.
    • It is necessary for the caller and the callee to follow the same convention as to who is responsible for clearing the parameters from the stack, when the call finishes.
  • Local variables that live within a function call.
    • Note that a local variable belonging to a caller can be made accessible to a callee by passing a pointer to that local variable to the callee.

Note1: dedicated to the thread's use, although its content is entirely readable - and smashable - by other threads.

In assembly programming, C, and C++, all three purposes can be fulfilled by the same stack. In some other languages, some purposes may be fulfilled by separate stacks, or dynamically-allocated memory.

1

Here is a deliberately oversimplified version of what the stack is used for.

Imagine the stack as a pile of index cards. The stack pointer points to the top card.

When you call a function:

  • You write the address of the code immediately after the line that called the function on a card and put it on the pile. (I.e. you increment the stack pointer by one and write the address to where it points to)
  • Then you write down the values contained in registers onto some cards, and put them on the pile. (i.e. you increment the stack pointer by the number of registers, and copy the register contents to the place it points to)
  • Then you put a marker card on the pile. (i.e. you save off the current stack pointer.)
  • Then you write the value of each parameter the function is called with, one to a card, and put it on the pile. (i.e you increment the stack pointer by the number of parameters and write the parameters to the place the stack pointer points to.)
  • Then you add a card for each local variable, potentially writing the initial value on it. (i.e. you increment the stack pointer by the number of local variables.)

At this point, the code in the function runs. The code is compiled to know where each card is relative to the top. So it knows that the variable x is the third card from the top (i.e. the stack pointer - 3) and that the parameter y is the sixth card from the top (i.e. the stack pointer - 6.)

This method means that the address of each local variable or parameter does not need to be baked into the code. Instead, all of these data items are addressed relative to the stack pointer.

When the function returns, the reverse operation is simply:

  • Look for the marker card and throw all the cards above it away. (i.e. set the stack pointer to the saved address.)
  • Restore the registers from the cards saved before and throw them away. (i.e. subtract a fixed value from the stack pointer)
  • Start running code from the address on the card on top and then throw that away. (i.e. subtract 1 from the stack pointer.)

The stack is now back in the state it was before the function was called.

When you consider this, note two things: allocation and deallocation of locals is an extremely fast operation as it is just adding a number to or subtracting a number from the stack pointer. Also note how naturally this works with recursion.

This is oversimplified for explanatory purposes. In practice, parameters and locals may be put in registers as an optimization, and the stack pointer will generally be incremented and decremented by the word size of the machine, not one. (To name a couple of things.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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