1 % The Stack and the Heap
3 As a systems language, Rust operates at a low level. If you’re coming from a
4 high-level language, there are some aspects of systems programming that you may
5 not be familiar with. The most important one is how memory works, with a stack
6 and a heap. If you’re familiar with how C-like languages use stack allocation,
7 this chapter will be a refresher. If you’re not, you’ll learn about this more
8 general concept, but with a Rust-y focus.
10 As with most things, when learning about them, we’ll use a simplified model to
11 start. This lets you get a handle on the basics, without getting bogged down
12 with details which are, for now, irrelevant. The examples we’ll use aren’t 100%
13 accurate, but are representative for the level we’re trying to learn at right
14 now. Once you have the basics down, learning more about how allocators are
15 implemented, virtual memory, and other advanced topics will reveal the leaks in
16 this particular abstraction.
20 These two terms are about memory management. The stack and the heap are
21 abstractions that help you determine when to allocate and deallocate memory.
23 Here’s a high-level comparison:
25 The stack is very fast, and is where memory is allocated in Rust by default.
26 But the allocation is local to a function call, and is limited in size. The
27 heap, on the other hand, is slower, and is explicitly allocated by your
28 program. But it’s effectively unlimited in size, and is globally accessible.
32 Let’s talk about this Rust program:
40 This program has one variable binding, `x`. This memory needs to be allocated
41 from somewhere. Rust ‘stack allocates’ by default, which means that basic
42 values ‘go on the stack’. What does that mean?
44 Well, when a function gets called, some memory gets allocated for all of its
45 local variables and some other information. This is called a ‘stack frame’, and
46 for the purpose of this tutorial, we’re going to ignore the extra information
47 and only consider the local variables we’re allocating. So in this case, when
48 `main()` is run, we’ll allocate a single 32-bit integer for our stack frame.
49 This is automatically handled for you, as you can see; we didn’t have to write
50 any special Rust code or anything.
52 When the function exits, its stack frame gets deallocated. This happens
53 automatically as well.
55 That’s all there is for this simple program. The key thing to understand here
56 is that stack allocation is very, very fast. Since we know all the local
57 variables we have ahead of time, we can grab the memory all at once. And since
58 we’ll throw them all away at the same time as well, we can get rid of it very
61 The downside is that we can’t keep values around if we need them for longer
62 than a single function. We also haven’t talked about what the word, ‘stack’,
63 means. To do that, we need a slightly more complicated example:
78 This program has three variables total: two in `foo()`, one in `main()`. Just
79 as before, when `main()` is called, a single integer is allocated for its stack
80 frame. But before we can show what happens when `foo()` is called, we need to
81 visualize what’s going on with memory. Your operating system presents a view of
82 memory to your program that’s pretty simple: a huge list of addresses, from 0
83 to a large number, representing how much RAM your computer has. For example, if
84 you have a gigabyte of RAM, your addresses go from `0` to `1,073,741,823`. That
85 number comes from 2<sup>30</sup>, the number of bytes in a gigabyte. [^gigabyte]
87 [^gigabyte]: ‘Gigabyte’ can mean two things: 10^9, or 2^30. The SI standard resolved this by stating that ‘gigabyte’ is 10^9, and ‘gibibyte’ is 2^30. However, very few people use this terminology, and rely on context to differentiate. We follow in that tradition here.
89 This memory is kind of like a giant array: addresses start at zero and go
90 up to the final number. So here’s a diagram of our first stack frame:
92 | Address | Name | Value |
93 |---------|------|-------|
96 We’ve got `x` located at address `0`, with the value `42`.
98 When `foo()` is called, a new stack frame is allocated:
100 | Address | Name | Value |
101 |---------|------|-------|
106 Because `0` was taken by the first frame, `1` and `2` are used for `foo()`’s
107 stack frame. It grows upward, the more functions we call.
110 There are some important things we have to take note of here. The numbers 0, 1,
111 and 2 are all solely for illustrative purposes, and bear no relationship to the
112 address values the computer will use in reality. In particular, the series of
113 addresses are in reality going to be separated by some number of bytes that
114 separate each address, and that separation may even exceed the size of the
117 After `foo()` is over, its frame is deallocated:
119 | Address | Name | Value |
120 |---------|------|-------|
123 And then, after `main()`, even this last value goes away. Easy!
125 It’s called a ‘stack’ because it works like a stack of dinner plates: the first
126 plate you put down is the last plate to pick back up. Stacks are sometimes
127 called ‘last in, first out queues’ for this reason, as the last value you put
128 on the stack is the first one you retrieve from it.
130 Let’s try a three-deep example:
152 We have some kooky function names to make the diagrams clearer.
154 Okay, first, we call `main()`:
156 | Address | Name | Value |
157 |---------|------|-------|
160 Next up, `main()` calls `bold()`:
162 | Address | Name | Value |
163 |---------|------|-------|
164 | **3** | **c**|**1** |
165 | **2** | **b**|**100**|
166 | **1** | **a**| **5** |
169 And then `bold()` calls `italic()`:
171 | Address | Name | Value |
172 |---------|------|-------|
174 | **3** | **c**|**1** |
175 | **2** | **b**|**100**|
176 | **1** | **a**| **5** |
178 Whew! Our stack is growing tall.
180 After `italic()` is over, its frame is deallocated, leaving only `bold()` and
183 | Address | Name | Value |
184 |---------|------|-------|
185 | **3** | **c**|**1** |
186 | **2** | **b**|**100**|
187 | **1** | **a**| **5** |
190 And then `bold()` ends, leaving only `main()`:
192 | Address | Name | Value |
193 |---------|------|-------|
196 And then we’re done. Getting the hang of it? It’s like piling up dishes: you
197 add to the top, you take away from the top.
201 Now, this works pretty well, but not everything can work like this. Sometimes,
202 you need to pass some memory between different functions, or keep it alive for
203 longer than a single function’s execution. For this, we can use the heap.
205 In Rust, you can allocate memory on the heap with the [`Box<T>` type][box].
215 [box]: ../std/boxed/index.html
217 Here’s what happens in memory when `main()` is called:
219 | Address | Name | Value |
220 |---------|------|--------|
224 We allocate space for two variables on the stack. `y` is `42`, as it always has
225 been, but what about `x`? Well, `x` is a `Box<i32>`, and boxes allocate memory
226 on the heap. The actual value of the box is a structure which has a pointer to
227 ‘the heap’. When we start executing the function, and `Box::new()` is called,
228 it allocates some memory for the heap, and puts `5` there. The memory now looks
231 | Address | Name | Value |
232 |----------------------|------|------------------------|
233 | (2<sup>30</sup>) - 1 | | 5 |
236 | 0 | x | → (2<sup>30</sup>) - 1 |
238 We have (2<sup>30</sup>) - 1 addresses in our hypothetical computer with 1GB of RAM. And since
239 our stack grows from zero, the easiest place to allocate memory is from the
240 other end. So our first value is at the highest place in memory. And the value
241 of the struct at `x` has a [raw pointer][rawpointer] to the place we’ve
242 allocated on the heap, so the value of `x` is (2<sup>30</sup>) - 1, the memory
243 location we’ve asked for.
245 [rawpointer]: raw-pointers.html
247 We haven’t really talked too much about what it actually means to allocate and
248 deallocate memory in these contexts. Getting into very deep detail is out of
249 the scope of this tutorial, but what’s important to point out here is that
250 the heap isn’t a stack that grows from the opposite end. We’ll have an
251 example of this later in the book, but because the heap can be allocated and
252 freed in any order, it can end up with ‘holes’. Here’s a diagram of the memory
253 layout of a program which has been running for a while now:
256 | Address | Name | Value |
257 |----------------------|------|------------------------|
258 | (2<sup>30</sup>) - 1 | | 5 |
259 | (2<sup>30</sup>) - 2 | | |
260 | (2<sup>30</sup>) - 3 | | |
261 | (2<sup>30</sup>) - 4 | | 42 |
263 | 3 | y | → (2<sup>30</sup>) - 4 |
266 | 0 | x | → (2<sup>30</sup>) - 1 |
268 In this case, we’ve allocated four things on the heap, but deallocated two of
269 them. There’s a gap between (2<sup>30</sup>) - 1 and (2<sup>30</sup>) - 4 which isn’t
270 currently being used. The specific details of how and why this happens depends
271 on what kind of strategy you use to manage the heap. Different programs can use
272 different ‘memory allocators’, which are libraries that manage this for you.
273 Rust programs use [jemalloc][jemalloc] for this purpose.
275 [jemalloc]: http://www.canonware.com/jemalloc/
277 Anyway, back to our example. Since this memory is on the heap, it can stay
278 alive longer than the function which allocates the box. In this case, however,
279 it doesn’t.[^moving] When the function is over, we need to free the stack frame
280 for `main()`. `Box<T>`, though, has a trick up its sleeve: [Drop][drop]. The
281 implementation of `Drop` for `Box` deallocates the memory that was allocated
282 when it was created. Great! So when `x` goes away, it first frees the memory
283 allocated on the heap:
285 | Address | Name | Value |
286 |---------|------|--------|
291 [^moving]: We can make the memory live longer by transferring ownership,
292 sometimes called ‘moving out of the box’. More complex examples will
296 And then the stack frame goes away, freeing all of our memory.
298 # Arguments and borrowing
300 We’ve got some basic examples with the stack and the heap going, but what about
301 function arguments and borrowing? Here’s a small Rust program:
316 When we enter `main()`, memory looks like this:
318 | Address | Name | Value |
319 |---------|------|--------|
323 `x` is a plain old `5`, and `y` is a reference to `x`. So its value is the
324 memory location that `x` lives at, which in this case is `0`.
326 What about when we call `foo()`, passing `y` as an argument?
328 | Address | Name | Value |
329 |---------|------|--------|
335 Stack frames aren’t only for local bindings, they’re for arguments too. So in
336 this case, we need to have both `i`, our argument, and `z`, our local variable
337 binding. `i` is a copy of the argument, `y`. Since `y`’s value is `0`, so is
340 This is one reason why borrowing a variable doesn’t deallocate any memory: the
341 value of a reference is a pointer to a memory location. If we got rid of
342 the underlying memory, things wouldn’t work very well.
346 Okay, let’s go through this complex program step-by-step:
357 fn bar(a: &i32, b: &i32) {
371 let i = Box::new(20);
378 First, we call `main()`:
380 | Address | Name | Value |
381 |----------------------|------|------------------------|
382 | (2<sup>30</sup>) - 1 | | 20 |
385 | 1 | i | → (2<sup>30</sup>) - 1 |
388 We allocate memory for `j`, `i`, and `h`. `i` is on the heap, and so has a
389 value pointing there.
391 Next, at the end of `main()`, `foo()` gets called:
393 | Address | Name | Value |
394 |----------------------|------|------------------------|
395 | (2<sup>30</sup>) - 1 | | 20 |
401 | 1 | i | → (2<sup>30</sup>) - 1 |
404 Space gets allocated for `x`, `y`, and `z`. The argument `x` has the same value
405 as `j`, since that’s what we passed it in. It’s a pointer to the `0` address,
406 since `j` points at `h`.
408 Next, `foo()` calls `baz()`, passing `z`:
410 | Address | Name | Value |
411 |----------------------|------|------------------------|
412 | (2<sup>30</sup>) - 1 | | 20 |
420 | 1 | i | → (2<sup>30</sup>) - 1 |
423 We’ve allocated memory for `f` and `g`. `baz()` is very short, so when it’s
424 over, we get rid of its stack frame:
426 | Address | Name | Value |
427 |----------------------|------|------------------------|
428 | (2<sup>30</sup>) - 1 | | 20 |
434 | 1 | i | → (2<sup>30</sup>) - 1 |
437 Next, `foo()` calls `bar()` with `x` and `z`:
439 | Address | Name | Value |
440 |----------------------|------|------------------------|
441 | (2<sup>30</sup>) - 1 | | 20 |
442 | (2<sup>30</sup>) - 2 | | 5 |
445 | 9 | d | → (2<sup>30</sup>) - 2 |
453 | 1 | i | → (2<sup>30</sup>) - 1 |
456 We end up allocating another value on the heap, and so we have to subtract one
457 from (2<sup>30</sup>) - 1. It’s easier to write that than `1,073,741,822`. In any
458 case, we set up the variables as usual.
460 At the end of `bar()`, it calls `baz()`:
462 | Address | Name | Value |
463 |----------------------|------|------------------------|
464 | (2<sup>30</sup>) - 1 | | 20 |
465 | (2<sup>30</sup>) - 2 | | 5 |
468 | 11 | f | → (2<sup>30</sup>) - 2 |
470 | 9 | d | → (2<sup>30</sup>) - 2 |
478 | 1 | i | → (2<sup>30</sup>) - 1 |
481 With this, we’re at our deepest point! Whew! Congrats for following along this
484 After `baz()` is over, we get rid of `f` and `g`:
486 | Address | Name | Value |
487 |----------------------|------|------------------------|
488 | (2<sup>30</sup>) - 1 | | 20 |
489 | (2<sup>30</sup>) - 2 | | 5 |
492 | 9 | d | → (2<sup>30</sup>) - 2 |
500 | 1 | i | → (2<sup>30</sup>) - 1 |
503 Next, we return from `bar()`. `d` in this case is a `Box<T>`, so it also frees
504 what it points to: (2<sup>30</sup>) - 2.
506 | Address | Name | Value |
507 |----------------------|------|------------------------|
508 | (2<sup>30</sup>) - 1 | | 20 |
514 | 1 | i | → (2<sup>30</sup>) - 1 |
517 And after that, `foo()` returns:
519 | Address | Name | Value |
520 |----------------------|------|------------------------|
521 | (2<sup>30</sup>) - 1 | | 20 |
524 | 1 | i | → (2<sup>30</sup>) - 1 |
527 And then, finally, `main()`, which cleans the rest up. When `i` is `Drop`ped,
528 it will clean up the last of the heap too.
530 # What do other languages do?
532 Most languages with a garbage collector heap-allocate by default. This means
533 that every value is boxed. There are a number of reasons why this is done, but
534 they’re out of scope for this tutorial. There are some possible optimizations
535 that don’t make it true 100% of the time, too. Rather than relying on the stack
536 and `Drop` to clean up memory, the garbage collector deals with the heap
541 So if the stack is faster and easier to manage, why do we need the heap? A big
542 reason is that Stack-allocation alone means you only have 'Last In First Out (LIFO)' semantics for
543 reclaiming storage. Heap-allocation is strictly more general, allowing storage
544 to be taken from and returned to the pool in arbitrary order, but at a
547 Generally, you should prefer stack allocation, and so, Rust stack-allocates by
548 default. The LIFO model of the stack is simpler, at a fundamental level. This
549 has two big impacts: runtime efficiency and semantic impact.
551 ## Runtime Efficiency
553 Managing the memory for the stack is trivial: The machine
554 increments or decrements a single value, the so-called “stack pointer”.
555 Managing memory for the heap is non-trivial: heap-allocated memory is freed at
556 arbitrary points, and each block of heap-allocated memory can be of arbitrary
557 size, so the memory manager must generally work much harder to
558 identify memory for reuse.
560 If you’d like to dive into this topic in greater detail, [this paper][wilson]
561 is a great introduction.
563 [wilson]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.143.4688
567 Stack-allocation impacts the Rust language itself, and thus the developer’s
568 mental model. The LIFO semantics is what drives how the Rust language handles
569 automatic memory management. Even the deallocation of a uniquely-owned
570 heap-allocated box can be driven by the stack-based LIFO semantics, as
571 discussed throughout this chapter. The flexibility (i.e. expressiveness) of non
572 LIFO-semantics means that in general the compiler cannot automatically infer at
573 compile-time where memory should be freed; it has to rely on dynamic protocols,
574 potentially from outside the language itself, to drive deallocation (reference
575 counting, as used by `Rc<T>` and `Arc<T>`, is one example of this).
577 When taken to the extreme, the increased expressive power of heap allocation
578 comes at the cost of either significant runtime support (e.g. in the form of a
579 garbage collector) or significant programmer effort (in the form of explicit
580 memory management calls that require verification not provided by the Rust