The stack and the heap

Before we get into ownership we need to understand how data works with memory. The stack and the heap both are parts of memory that are available to your program to use at runtime, but they have their own differences, in this lesson we're going to learn those differences, once you understand this concept, you'll have a better understanding of the different data types in Rust and how ownership works.

It's a linear data structure that stores data in order, the first data being stored in the stack is the last piece of data that's being removed later.

This is known as a LIFO (Last In First Out) data structure. Think of this like a stack of plates, the last plate that was added to the plate pile is the first plate that is removed from the pile.

A major difference between the stack and the heap is that, in the stack, the size and location of every data is known at compile time, this makes accessing data from the stack much faster because allocation and de-allocation is not required, since the data is fixed is means data also can not shrink or grow at runtime.

Let's visualize this concept with a simple example, we're going to write a simple Rust program that calls a few other functions and we're going to explain how they are stored on the stack:

fn main() {
    let result = do_math(3, 4);
    println!("Result: {}", result);
}
 
fn do_math(a: i32, b: i32) -> i32 {
    let sum = add(a, b);
    let difference = subtract(a, b);
    let product = multiply(a, b);
    let quotient = divide(a, b);
    sum + difference + product + quotient
}
 
fn add(a: i32, b: i32) -> i32 {
    a + b
}
 
fn subtract(a: i32, b: i32) -> i32 {
    a - b
}
 
fn multiply(a: i32, b: i32) -> i32 {
    a * b
}
 
fn divide(a: i32, b: i32) -> i32 {
    a / b
}

Let's break down the code:

1. The main function is the entry point of the program which is available in every Rust program, it calls the do_math.
2. The do_math function takes two arguments a and b and returns the sum, difference, product, and quotient of a and b.
3. We have 4 other functions, add, subtract, multiply, and divide that take two arguments a and b and return the sum, difference, product, and quotient of a and b respectively.

Here's what happens in the stack when the program is executed step by step:

1. The main() function is called.

fn main() {
    let result = do_math(3, 4);
    println!("Result: {}", result);
}

Stack main

2. The do_math(a: i32, b: i32) -> i32 function is called by the main function and is added on top of the stack, the 3 and 4 are primitive scalar values that are also stored on the stack, in this case they are stored in the a and b variables.

fn main() {
    let result = do_math(3, 4); // Called by main
    println!("Result: {}", result);
}

Do math function is called

3. The add(a: i32, b: i32) -> i32 function is called by the do_math function and is added on top of the stack.

fn main() {
    let result = do_math(3, 4); // Called by main
    println!("Result: {}", result);
}
 
fn do_math(a: i32, b: i32) -> i32 {
    let sum = add(a, b); // Called by do_math
    let difference = subtract(a, b);
    let product = multiply(a, b);
    let quotient = divide(a, b);
    sum + difference + product + quotient
}

Add function is called

4. The add() function finishes executing and is removed from the stack.

Add function is removed

5. The subtract(a: i32, b: i32) -> i32 function is called by the do_math function and is added on top of the stack.

fn main() {
    let result = do_math(3, 4); // Called by main
    println!("Result: {}", result);
}
 
fn do_math(a: i32, b: i32) -> i32 {
    let sum = add(a, b);
    let difference = subtract(a, b); // Called by do_math
    let product = multiply(a, b);
    let quotient = divide(a, b);
    sum + difference + product + quotient
}

Subtract function is called

6. The subtract() function finishes executing and is removed from the stack, this happens for the multiply() and divide() functions as well.

7. The do_math() function finishes executing and is removed from the stack.

Do math function is removed

8. The value is then assigned to the result variable which is Owned by the main() function.
9. The println! macro is called and the Result which does a few operations behind the scenes resulting in the output of the result.
10. The main() function finishes executing and is removed from the stack.

Main function is removed

11. The program terminates.

The heap is a less organized place for storing data compared to the stack. When you store data on the heap, you request a certain amount of space, the memory allocator finds a big enough space to hold the data and returns a pointer which then is stored on the stack (because it has a known, fixed size) that points to the location in the heap where the data is stored.

Understanding pointers are really important in Rust, because we're going to talk about and use them a lot when it comes to Rust programming, so let's talk about what pointers are.

Pointers are variables that are stored on the Stack that hold the memory address of the data that is stored somewhere else (mostly on the Heap). Since the size and location of each pointer is known, they can be stored on the stack.

When it comes to accessing data, the program follows the pointer and the pointer points to some data somewhere else.

Data located on the Heap can grow or shrink at runtime, unlike data on the stack which has a fixed size.

Memory allocation is the process of reserving a block of memory from the heap and storing a pointer on the stack to access the data.

Here's a simple visualization of data stored in the Heap.

fn main() {
    let x = Box::new(5);
    println!("x = {}", x);
}

Stack and heap

In the figure above, you can see that variable x is stored in the stack in the main() function which is a pointer that points to some data stored on the heap, when accessing the data, the program follows the pointer and reads the actual data stored on the heap.

All Scalar Types by default are stored on the stack, but if you want to store them on the heap you can use the Box type.

In low level programming languages, Heap allocations and data in the Heap are generally less predictable and involve a greater overhead due to dynamic memory management.

For example in not safe programming languages like C or C++ if we have multiple references to the same data and one of the references is mutating some data on the Heap, our other references will have no idea that the data has changed or even deleted, they will have no way of knowing that, which can lead to pointers pointing to data which doesn't exist, this is called Dangling Pointers in programming.

But luckily for us we are using Rust, which solves these issues with its Ownership system which we learn in the next lesson.

Dangling pointers are pointers that point to a memory location that has been de-allocated, this can lead to unpredictable behavior and bugs which could be difficult to track down.

There can be multiple pointers at the same time pointing to the same data. Here's an example:

Multiple pointers

If the data is de-allocated but some of the pointers still exist, they will then point to invalid memory locations, this is called a Dangling Pointer.

Dangling pointers

Luckily for us, in Rust this never happens and if you ever did this by mistake, the Rust compiler will catch this error at compile time.

Stack and heap both are parts of memory to be used at runtime, they service different needs and have different trade-offs. Data stored in the stack has a fixed size and known location at compile time which makes accessing data much faster.

Data stored in the heap has a dynamic size and can grow or shrink at runtime, but the trade-off is that accessing data from the heap is slower and each data stored on the heap needs a pointer to be saved on the stack to access the data.

In other low-level programming languages, managing memory can be a difficult and complicated task, but Rust makes this easier for us with its Ownership system.

In the next lesson, we're going to explore Ownership in detail.