TLDR

  • Allow yourself to go down the rabbit hole if you find it compounds.
  • A stack is a data structure; it is a Last In First Out (LIFO) structure.
  • The stack tracks which subroutines are active.
  • The heap let’s you store whatever you need but is slower than the stack.

Compounding Knowledge had a big effect on me. The idea of making sure a vast majority of your time is spent on things that compound is very applicable to the tech world. Tech has no shortage of distractions so I’m making an effort to focus on the things that (theoretically) remain true.

Lacking a clear and obvious “start here” sign, I chose to learn a little Lisp/Scheme. I was curious about the reported mind blowing paradigm shift of Lisp and thought it would be an interesting way to get started. Then I fell into the rabbit hole of collectors…

Take Away #1: Allow yourself to go down the rabbit hole if you find it compounds.

As I began studying collectors I ran into the idea of continuations. Continuations led to continuation passing style. Which led to the ideas of control flow and higher order programming. Which led to the call stack, stack based memory allocation and heap allocation. I’m leaving out a handful of interesting subjects from this rabbit trail network.

So let’s just zoom in on one idea that seems to be near the bottom of all these ideas.

What is a Stack?

A stack is an abstract data structure. Think of it like a literal stack of papers; you can place one item at a time on top and you can only retrieve the last thing you placed on it.

In computer terms, we “push” an item on to the stack and we “pop” an item off of the stack.

Take Away #2: A stack is a data structure; it is a Last In First Out (LIFO) structure.

What is “The Stack”?

When we talk about the stack in terms of an application we’re generally referring to a section of memory that is used to track the active subroutines of the application. Basically, it helps the processor know where it’s at within all the subroutines of the application and when it should return to a prior subroutine. The stack is a very important part of the application as it allows the application to behave the way you want it to. Let me explain.

function add(x, y) {
  return x + y;
}

function getThree() {
  return add(1, 2);
}

const three = getThree();

If we follow this code as a series of instructions we might oversimplify it like this:

  1. Start the application
  2. Call subroutine getThree
  3. Call subroutine add
  4. Return to subroutine getThree
  5. Return to the start and exit

Do you see how this follows a pattern that matches a stack data structure? The computer can only work on one item at a time and it must do so in the order we programmed it. The stack data structure is how we do this.

It just so happens that memory and memory addresses are great for this kind of stuff. Take a look at yet another oversimplified example of what this might look like in actual memory; remember that the stack is mainly repsponsible for tracking which subroutine is currently executing:

------------------------------------------------------------------------
Address | Contents
------------------------------------------------------------------------
  1     | the address of variable "three"
  2     | the parameters of getThree, the address of where to return (1)
  3     | the parameters of add, the address of where to return (2)
------------------------------------------------------------------------

In this manner, we can describe the execution of our application with a bit more detail:

  1. Start the application. Push the address for the variable “three” at stack address (1)
  2. Evaluating the rest of the line, notice that we have a subroutine to call. Push the parameters and return address (1) for getThree onto stack address (2).
  3. Evaluate the first line of getThree, notice that we have a subroutine to call. Push the parameters and return address (2) for add onto stack address (3).
  4. Evaluate add. Notice that we have no more subroutines so evaluate the addition of x and y, “pop” the stack and give the return value to return address (2).
  5. “Pop” the stack again and return the value to return address (1).
  6. There are no more instructions, “pop” the stack at address (1) and exit the program.

Take Away #3: The stack tracks which subroutines are active.

What is the Heap?

Hopefully, the description of the stack made sense. It’s very structured, it’s very rigid. There’s only one way to get values onto and off of the stack. The heap is kind of the opposite.

The heap is an open space for storing whatever values your application needs to store. In this way it’s very convenient because you can typically store whatever you need to store without too much concern.

However, it’s also generally well known to be slower than the stack for two reasons:

  1. The stack is very structured and only works a certain way.
  2. The heap can experience fragmentation.

Since the heap can store any type of value, it is subject to fragmentation. Let’s say you store a value that is 2 bytes. Then you store another value that is 1 byte. Finally, you store a third value that is 2 bytes. Great, you’ve stored 5 bytes.

Now let’s say you are finished with your 1 byte value and you delete it. That’s fine, but now there’s a 1 byte gap in our memory addresses. A 1 byte gap that, for the most part will remain unused.

Take Away #4: The heap let’s you store whatever you need but is slower than the stack.

What Does This Mean for My Applications?

On your day to day schedule, these things might not mean a whole lot. For the most part you can code some amazing stuff without really needing to consider this.

On the other hand, knowing this will certainly help you with optimizing and troubleshooting efforts. Wikipedia has some really nice articles: