The many meanings of “stack”

With regards to “same word different meaning”, the term stack comes up top (pun intended). This post is not written to be comprehensive, but I hope it provides sufficient detail to save you the few hours I spent being very confused.

Stack vs queue

The stack is a data structure where it’s easy to remove the item most recently-added to the collection (Last-In-First-Out or LIFO). Think of a stack of pancakes, where it’s easy to remove the pancake at the top. This is in contrast to the queue, where it’s easy to remove the item that’s been in the collection for the longest time (First-In-First-Out or FIFO).

From Crafting Interpreters

A nice contrast arises when the data structures are used to traverse a graph. If you use a stack you’ll go depth-first (DFS), with a queue breadth-first (BFS).

Stack vs heap

To enable code execution, the OS allocates a region in memory for the running process. The stack is for local variables, function arguments and return addresses - the size of these objects are known at compile time. This is in contrast with the heap, which is used for dynamically-located data such as lists and dictionaries.

From OS: Three Easy Pieces

With regards to performance, it’s faster to use the stack since there’s very little overhead - the stack is managed by simply changing a counter (the stack pointer). Allocating on the heap takes a bit more work. We’ll need to find a free contiguous memory block of the right size, update the list of free blocks, and free the block when no longer needed.

For further details, Operating Systems: Three Easy Pieces discusses memory allocation of a process in Section 4.3. Computer Systems: A Programmer’s Perspective goes through dynamic memory allocation in Section 9.9. For a more intuitive (or perhaps, less counter-intuitive) way of thinking about stack growth on the x86, Eli Bendersky has a helpful post.

Stack-based VM

The term virtual machine is also overloaded. For our purposes, we’re referring to the process virtual machine which lets you run the same instructions across different OS or different processors. For example, you can run Java bytecode on any platform that supports the JVM, and WebAssembly on any web browser. This is in contrast to the system virtual machine, which lets you play Windows games on a Linux machine (example from Bob Nystrom).

A stack-based VM executes instructions by using a stack in the sense of “stack vs queue” above, through push (add to stack) and pop (remove from stack) operations. In fact, both the JVM and WebAssembly use stack-based VMs. This is in contrast with a register-based VM, which uses virtual registers and maps more naturally to physical registers.

The second part of Crafting Interpreters involves implementing a stack-based VM. Lua moved from a stack-based to a register-based VM in the upgrade from 4.0 to 5.0. The paper describes a number of language optimizations in the upgrade, but the VM change alone shows significant performance gains. Linus Lee has a thoughtful post on Lua internals based on the paper.

Stack-based calling convention

A calling convention defines how function calls in a programming language operate at the machine-code level. With a stack-based calling convention, function arguments and return values are passed on the stack in the sense of “stack vs heap” above. This is in contrast to a register-based calling convention, which uses physical registers and allows state be kept in registers across function calls.

Go moved from a stack-based to a register-based calling convention in the upgrade from 1.16 to 1.17. The stack-based calling convention has the benefit of being simple - all platforms use the same conventions and thus no processor-specific register details are needed. The register-based calling convention, however, benefits from higher throughput as accessing arguments in registers is faster than on the stack.

Details on the upgrade can be found in the proposal, with an approachable post on the topic by Menno Finlay-Smits (with assembly and benchmarks!). What’s also worth a read is the switch to a multiple ABI mechanism done in parallel to support the change.