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.
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
- Learning Rust (Part 3): Ownership explains the rules that manage this memory.
- What actually happens when you run
python script.py? shows what the interpreter does, from bytecode to frames.
Keyboard shortcuts
- j k
- scroll down / up
- n p
- next / previous section
- g G
- start / end of the article
- t
- show outline
- ?
- show this help
- Esc
- close
0 comments
No comments yet. Be the first!
Sign in to leave a comment.