Author’s note: Hacker News comments here.
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).
. 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.