Skip to content

cat posts/en/stack-und-heap.md

Stack and heap—and how Python does it

What lives on the stack and what lives on the heap, measured in Rust and Python: why a String takes 24 bytes, a move costs next to nothing, and a million numbers in Python need ten times the space.

Retro photo: neatly folded stacks of clothes sit on a dresser, while next to it a wooden chair disappears under a chaotic heap of crumpled clothing.

In part 3 of Learning Rust, there was a sentence that takes a lot for granted: a String sits on the stack as a pointer, a length, and a capacity, while its characters live on the heap. This article measures what that means and compares it with Python. In Python, the question never comes up, and that has a price.

Two kinds of memory

Every thread gets its own stack, a contiguous block of memory with a fixed size. When one function calls another, a frame with the called function's local variables goes on top. When that function returns, the frame comes off again. Allocating and freeing cost next to nothing: a register points to the top, and the program moves it. In return, the size of every frame has to be known at compile time.

The heap is everything else. There, the program requests memory of any size at runtime, and an allocator finds a free spot for it. That's considerably slower, and someone has to free the memory again. In C, that's the programmer; in Python, it's the interpreter. In Rust, it happens when the owner leaves its scope.

Measured in Rust

size_of returns the size of a type in bytes, which is the space a variable takes up on the stack:

fn main() {
    println!("u16:              {:>4} bytes", size_of::<u16>());
    println!("usize:            {:>4} bytes", size_of::<usize>());
    println!("[u8; 1024]:       {:>4} bytes", size_of::<[u8; 1024]>());
    println!("&str:             {:>4} bytes", size_of::<&str>());
    println!("String:           {:>4} bytes", size_of::<String>());
    println!("Vec<u32>:         {:>4} bytes", size_of::<Vec<u32>>());
    println!("Box<u64>:         {:>4} bytes", size_of::<Box<u64>>());
    println!("Option<Box<u64>>: {:>4} bytes", size_of::<Option<Box<u64>>>());
}
u16:                 2 bytes
usize:               8 bytes
[u8; 1024]:       1024 bytes
&str:               16 bytes
String:             24 bytes
Vec<u32>:           24 bytes
Box<u64>:            8 bytes
Option<Box<u64>>:    8 bytes

Measured on a 64-bit system. Numbers and arrays live entirely on the stack, even an array of 1024 bytes. A &str consists of a pointer and a length, 16 bytes in total. A String adds the capacity, which makes 24 bytes, whether it holds three characters or three million. A Vec is built the same way. Box<u64> puts a single value on the heap and keeps only the pointer on the stack.

The last line is a small optimization: a pointer in a Box is never null, so Rust can represent the “no value” case as null and needs no extra byte for it. Option itself comes up in part 6planned of the series.

To see how the capacity grows, append to a String piece by piece (wort is German for word):

let mut text = String::new();
for wort in ["404", " ", "/favicon.ico", " ", "/wp-login.php"] {
    text.push_str(wort);
    println!("len {:>2}, capacity {:>2}", text.len(), text.capacity());
}
len  3, capacity  8
len  4, capacity  8
len 16, capacity 16
len 17, capacity 32
len 30, capacity 32

When the space runs out, String gets a larger block from the heap, at least twice the size, and copies the contents over if the old block can't grow in place. The exact numbers are an implementation detail of the standard library. If you know in advance how big the text will get, String::with_capacity(n) saves you the copying.

What a move costs

Now it's clear why a move in Rust is cheap. let b = a; copies the 24 bytes on the stack: pointer, length, and capacity. The characters on the heap stay where they are and now belong to b. That's why a has to become invalid: otherwise there would be two pointers to the same heap block and two owners that both want to free it.

a.clone(), on the other hand, requests a new block on the heap and copies all the characters. For a 2 GB log, that's 2 GB. This is why Rust insists that you write clone yourself. For Copy types like u16, the difference doesn't exist: they own no memory on the heap, so a bitwise copy is already a complete copy.

When the stack is full

The stack is small. On Linux, the main thread usually gets 8 MiB (ulimit -s), and threads that a Rust program starts itself get 2 MiB by default. Recursion that never stops fills it quickly (tiefer is German for deeper, puffer for buffer):

fn tiefer(n: u64) -> u64 {
    let puffer = [0u8; 1024];
    puffer[0] as u64 + tiefer(n + 1)
}

fn main() {
    println!("{}", tiefer(0));
}

Even the compiler has its doubts:

warning: function cannot return without recursing
 --> src/main.rs:1:1
  |
1 | fn tiefer(n: u64) -> u64 {
  | ^^^^^^^^^^^^^^^^^^^^^^^^ cannot return without recursing
2 |     let puffer = [0u8; 1024];
3 |     puffer[0] as u64 + tiefer(n + 1)
  |                        ------------- recursive call site
  |
  = help: a `loop` may express intention better if this is on purpose
  = note: `#[warn(unconditional_recursion)]` on by default

If you run the program anyway as a debug build, every call puts another kilobyte on the stack until there's no room left:

thread 'main' (10764) has overflowed its stack

At that point, the process is dead. This is a crash, not a panic: unlike a panic, the program can't catch it. Python protects itself against this with a cap on recursion depth: sys.getrecursionlimit() returns 1000 by default, and beyond that you get a RecursionError: maximum recursion depth exceeded. That's an ordinary exception.

How Python does it

In CPython, almost every object lives on the heap, even a number like 1000. Only a few built-in objects such as None and the small integers (more on those in a moment) are baked into the interpreter itself. For its local variables, a Python frame holds nothing but pointers to such objects. Every object carries a header with a reference count and a type pointer:

>>> import sys
>>> sys.getsizeof(1)
28
>>> sys.getsizeof(2**70)
36
>>> sys.getsizeof([])
56

Measured with 64-bit Python 3.14. A small integer takes 28 bytes; a u16 in Rust takes 2. You can even watch the count:

>>> logs = []
>>> sys.getrefcount(logs)
2
>>> alias = logs
>>> sys.getrefcount(logs)
3

The 2 instead of 1 comes from the call itself, which holds one more reference as its argument. Every alias = logs increments the count, and every reference that goes away decrements it. When it drops to zero, CPython frees the object. It's the same question Rust answers with ownership, only at runtime and with any number of owners.

A few numbers are never created fresh. CPython keeps the integers from -5 to 256 around as ready-made objects:

>>> a = 256; b = int("256"); a is b
True
>>> a = 257; b = int("257"); a is b
False

That saves memory for the most common values, but it's an implementation detail. Always compare numbers with ==, never with is.

A million numbers

A list of one million integers shows how this adds up. In Python, measured with tracemalloc (zahlen is German for numbers):

import tracemalloc

tracemalloc.start()
zahlen = list(range(1000, 1_001_000))
print(tracemalloc.get_traced_memory()[0])
39999640

Just under 40 MB. The list itself holds a million pointers at 8 bytes each, which makes 8 MB. The rest is the numbers themselves, each one a separate object on the heap. That comes to about 32 bytes per number, a bit more than the 28 that getsizeof reports. The numbers start at 1000 so that the cache for small integers stays out of the picture.

In Rust:

let zahlen: Vec<u32> = (1000..1_001_000).collect();
println!("{} bytes", zahlen.capacity() * size_of::<u32>());
4000000 bytes

4 MB, a tenth. The numbers sit right next to each other on the heap, with no header and no pointer. That saves time, too: when a program walks over the numbers, the processor reads them from the cache in one contiguous run instead of following a pointer somewhere else for each one. It's one of the reasons numeric Python libraries like NumPy store their data the same way Rust does.

Further reading

0 comments

No comments yet. Be the first!