[Advanced Rust] 1.7. Memory Part 5 - Heap vs. Stack Memory, Virtual Memory, and Guidelines for Displaying Data in RAM

1.7.1. Dynamic Memory Allocation

At any given moment, a running program occupies part of memory. Sometimes the program needs more memory, so it must request it from the operating system; this is called dynamic allocation.

The following diagram shows the steps of dynamic memory allocation:

• The program requests memory from the system through the allocator interface. On Unix-like systems this is typically done with malloc()/free(), and on Windows with HeapAlloc()/HeapFree().
• The program uses the allocated memory.
• If the memory is no longer needed after use, the program releases it back to the operating system.

PS: there is an **allocator* between the program and the system when memory is requested. It is a specialized subroutine hidden behind the scenes of the program, and it performs some optimizations to avoid a large amount of work for the CPU and the operating system.*

1.7.2. Why Is There a Performance Difference Between Stack Memory and Heap Memory?

First of all, it should be made clear that stack memory and heap memory are only concepts; physically, memory does not contain these two separate regions.

The reason stack memory is fast is that:

• Local variables of functions (all allocated on the stack) are adjacent to one another in RAM (contiguous layout). A contiguous layout is very cache-friendly.

The reason heap memory is slower is that:

• Data allocated on the heap is unlikely to be adjacent to one another.
• Accessing data on the heap requires dereferencing a pointer (which involves page-table lookups and then accessing main memory).

A Simple Comparison Between Stack and Heap

Stack	Heap	Notes
Simple	Complex
Safe	Dangerous	Dangerous here means Unsafe Rust
Fast	Slow
Rigid	Flexible

• Data structures on the stack cannot change size during their lifetime.
• Data structures on the heap are more flexible because the pointer can change.

1.7.3. Virtual Memory

Virtual memory is the memory view seen by a program. All data that a program can access is provided by the operating system within its address space.

Intuitively, a program’s memory is a sequence of bytes, from a starting position 0 to an ending position n. For example, if a program reports that it uses 100 KB of RAM, then n would be around 100000.

Let’s look at an example:

fn main() {
    let mut n_nonzero = 0;

    for i in 0..10000 {
        let ptr = i as *const u8;
        let byte_at_addr = unsafe { *ptr };
        if byte_at_addr != 0 {
            n_nonzero += 1;
        }
    }

    println!("{}", n_nonzero);
}

• This example scans the memory of the running program byte by byte, starting at position 0 and ending at 9999.
• let ptr = i as *const u8; converts i into an immutable raw pointer of type *const u8 (a u8 occupies one byte) so that the memory address can be checked. Here, we treat each address as one unit. In reality, many values occupy more than one byte and span multiple bytes, but we will ignore that here.
• The next line, let byte_at_addr = unsafe { *ptr };, dereferences the pointer (operations on raw pointers must be placed inside an unsafe block) and reads the value into byte_at_addr.
• If byte_at_addr is not 0, then n_nonzero increases by 1.
• Finally, the value of n_nonzero is printed.

Output:

segmentation fault

segmentation fault means an error that occurs when the CPU or operating system detects that a program is trying to access an illegal (unauthorized) memory address.

A segment refers to a block in virtual memory. Virtual memory is divided into blocks to minimize the space needed for translating between virtual and physical addresses.

So which memory access is illegal? Address 0. When i equals 0, it is effectively a null pointer, and a null pointer cannot be dereferenced. This also partly explains why raw pointer operations must be placed inside an unsafe block.

Let’s start the loop from 1 instead:

fn main() {
    let mut n_nonzero = 1;

    for i in 1..10000 {
        let ptr = i as *const u8;
        let byte_at_addr = unsafe { *ptr };
        if byte_at_addr != 0 {
            n_nonzero += 1;
        }
    }

    println!("{}", n_nonzero);
}

Output:

segmentation fault

The same error.

This example does not work, so let’s switch to another one:

static GLOBAL: i32 = 1000;

fn noop() -> *const i32 {
    let noop_local = 12345;
    &noop_local as *const i32
}

fn main() {
    let local_str = "a";
    let local_int = 123;
    let boxed_str = Box::new("b");
    let boxed_int = Box::new(789);
    let fn_int = noop();

    println!("GLOBAL:    {:p}", &GLOBAL as *const i32);
    println!("local_str: {:p}", local_str.as_ptr());
    println!("local_int: {:p}", &local_int as *const i32);
    println!("boxed_int: {:p}", Box::into_raw(boxed_int));
    println!("boxed_str: {:p}", Box::into_raw(boxed_str));
    println!("fn_int:    {:p}", fn_int);
}

• We declare variables such as GLOBAL, local_str, and local_int (static variables also count as variables). Some are stored on the heap, and some are stored on the stack.
• We print their memory addresses.
• local_str.as_ptr() prints the address of the string data. Prefer that over local_str as *const str with {:p}: a *const str is a wide pointer, and current Rust formats it as Pointer { addr: ..., metadata: ... } rather than a bare hex address.

Output:

GLOBAL:    0x102572ae4
local_str: 0x102572ae0
local_int: 0x16d8c260c
boxed_int: 0x102d89b10
boxed_str: 0x102d89c10
fn_int:    0x16d8c2620

Although our program is very small, the distribution of variables in virtual memory is quite scattered. Still, there is some pattern:

• The addresses of GLOBAL and local_str are relatively close.
• The addresses of boxed_int and boxed_str are relatively close.
• The addresses of local_int and fn_int are relatively close.

The size of virtual memory is roughly 2^48, but physical memory is certainly not that large. In addition, part of the virtual address space is reserved by the system for itself, and those reserved addresses cannot be used.

Through the Example

From these examples, we can learn a few things:

• Some memory addresses are illegal. If you access out-of-bounds memory, the program will be terminated.
• Memory addresses are not random. Although values of different types appear to be widely distributed in memory, there is actually a pattern.

1.7.4. Translating Virtual Addresses to Physical Addresses

Accessing data in a program requires virtual addresses (a program can only access virtual addresses). Virtual addresses are translated into physical addresses, which involves the program, the operating system, the CPU, and RAM hardware (and sometimes hard disks and other devices as well):

• The CPU is responsible for the translation; more specifically, the Memory Management Unit (MMU) inside the CPU performs this work.
• The operating system is responsible for storing instructions.
• These instructions also exist at predefined addresses in memory.

In the worst case, every memory access triggers two memory lookups: one for the memory being accessed and one for the instructions.

The CPU maintains a cache of recently translated addresses. It has its own fast memory to accelerate memory access. For historical reasons, this memory is called the Translation Lookaside Buffer (TLB).

To improve performance, programmers need to keep data structures compact and avoid deep nesting. This becomes especially important once the TLB capacity is reached (for x86 processors, roughly 100 pages).

Let’s define the terms:

• Page: a fixed-size block of bytes in physical memory; on 64-bit systems it is usually 4 KB.
• Word: any value whose size is the size of a pointer, i.e. the width of a CPU register. In Rust, usize and isize are word-length types.

Virtual addresses are divided into many blocks called pages, usually 4 KB each. Dividing memory into blocks helps avoid storing a translation mapping for every variable. In addition, pages have a uniform size, which helps avoid memory fragmentation (empty, unusable spaces appearing in available RAM).

Note: the above is only a general guideline; situations such as microcontrollers are different.

1.7.5. Practical Guidelines for Displaying Data in RAM

Keep the hot part of your program within 4 KB so that lookups stay fast and performance remains good. Many programs cannot keep their hot working set within 4 KB, and for such programs the 4 KB target is unrealistic. In that case, the next target should be 4 KB × 100. This means the CPU’s translation cache (TLB) can still support your program.

---

Avoid deeply nested data structures. If a pointer points to another page, performance will be affected.

---

When traversing arrays, the access order affects cache utilization (because the CPU reads small blocks of bytes from RAM, called a cache line), which in turn affects program performance. Two-dimensional arrays in C/C++, Rust, Python (NumPy), and similar languages are stored in row-major order. For example:

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

The layout in memory is:

1  2  3  |  4  5  6  |  7  8  9

If you use row-major traversal:

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        process(matrix[i][j]);
    }
}

matrix[i][j] is contiguous in memory, which makes good use of cache lines, reduces RAM access, and improves speed.

If you use column-major traversal:

for (int j = 0; j < 3; j++) {
    for (int i = 0; i < 3; i++) {
        process(matrix[i][j]);
    }
}

Because columns are scattered in memory, accessing matrix[i][j] may cross multiple cache lines. The CPU may frequently load new cache lines from RAM, causing cache misses and hurting performance.

To summarize:

• In languages such as C/C++, Rust, and Python (NumPy) that use row-major order by default, try to traverse arrays by row.
• In languages such as MATLAB and Fortran that use column-major order, traversing by column is more efficient.

---

Note:

Virtualization makes things even worse. If you run an application inside a virtual machine, the hypervisor must also translate addresses for the guest operating system. That is why many CPUs include hardware virtualization support — to reduce overhead by reducing the amount of translation work.

If you run containers inside a virtual machine, you add yet another layer of indirection, which also increases latency.

So, if you want bare-metal performance, you have to run the program on bare metal.