src/doc/trpl/the-stack-and-the-heap.md

   1 % The Stack and the Heap
   2
   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.
   9
  10 # Memory management
  11
  12 These two terms are about memory management. The stack and the heap are
  13 abstractions that help you determine when to allocate and deallocate memory.
  14
  15 Here’s a high-level comparison:
  16
  17 The stack is very fast, and is where memory is allocated in Rust by default.
  18 But the allocation is local to a function call, and is limited in size. The
  19 heap, on the other hand, is slower, and is explicitly allocated by your
  20 program. But it’s effectively unlimited in size, and is globally accessible.
  21
  22 # The Stack
  23
  24 Let’s talk about this Rust program:
  25
  26 ```rust
  27 fn main() {
  28     let x = 42;
  29 }
  30 ```
  31
  32 This program has one variable binding, `x`. This memory needs to be allocated
  33 from somewhere. Rust ‘stack allocates’ by default, which means that basic
  34 values ‘go on the stack’. What does that mean?
  35
  36 Well, when a function gets called, some memory gets allocated for all of its
  37 local variables and some other information. This is called a ‘stack frame’, and
  38 for the purpose of this tutorial, we’re going to ignore the extra information
  39 and just consider the local variables we’re allocating. So in this case, when
  40 `main()` is run, we’ll allocate a single 32-bit integer for our stack frame.
  41 This is automatically handled for you, as you can see, we didn’t have to write
  42 any special Rust code or anything.
  43
  44 When the function is over, its stack frame gets deallocated. This happens
  45 automatically, we didn’t have to do anything special here.
  46
  47 That’s all there is for this simple program. The key thing to understand here
  48 is that stack allocation is very, very fast. Since we know all the local
  49 variables we have ahead of time, we can grab the memory all at once. And since
  50 we’ll throw them all away at the same time as well, we can get rid of it very
  51 fast too.
  52
  53 The downside is that we can’t keep values around if we need them for longer
  54 than a single function. We also haven’t talked about what that name, ‘stack’
  55 means. To do that, we need a slightly more complicated example:
  56
  57 ```rust
  58 fn foo() {
  59     let y = 5;
  60     let z = 100;
  61 }
  62
  63 fn main() {
  64     let x = 42;
  65
  66     foo();
  67 }
  68 ```
  69
  70 This program has three variables total: two in `foo()`, one in `main()`. Just
  71 as before, when `main()` is called, a single integer is allocated for its stack
  72 frame. But before we can show what happens when `foo()` is called, we need to
  73 visualize what’s going on with memory. Your operating system presents a view of
  74 memory to your program that’s pretty simple: a huge list of addresses, from 0
  75 to a large number, representing how much RAM your computer has. For example, if
  76 you have a gigabyte of RAM, your addresses go from `0` to `1,073,741,823`. That
  77 number comes from 2<sup>30</sup>, the number of bytes in a gigabyte.
  78
  79 This memory is kind of like a giant array: addresses start at zero and go
  80 up to the final number. So here’s a diagram of our first stack frame:
  81
  82 | Address | Name | Value |
  83 |---------|------|-------|
  84 | 0       | x    | 42    |
  85
  86 We’ve got `x` located at address `0`, with the value `42`.
  87
  88 When `foo()` is called, a new stack frame is allocated:
  89
  90 | Address | Name | Value |
  91 |---------|------|-------|
  92 | 2       | z    | 100   |
  93 | 1       | y    | 5     |
  94 | 0       | x    | 42    |
  95
  96 Because `0` was taken by the first frame, `1` and `2` are used for `foo()`’s
  97 stack frame. It grows upward, the more functions we call.
  98
  99
 100 There’s some important things we have to take note of here. The numbers 0, 1,
 101 and 2 are all solely for illustrative purposes, and bear no relationship to the
 102 actual numbers the computer will actually use. In particular, the series of
 103 addresses are in reality going to be separated by some number of bytes that
 104 separate each address, and that separation may even exceed the size of the
 105 value being stored.
 106
 107 After `foo()` is over, its frame is deallocated:
 108
 109 | Address | Name | Value |
 110 |---------|------|-------|
 111 | 0       | x    | 42    |
 112
 113 And then, after `main()`, even this last value goes away. Easy!
 114
 115 It’s called a ‘stack’ because it works like a stack of dinner plates: the first
 116 plate you put down is the last plate to pick back up. Stacks are sometimes
 117 called ‘last in, first out queues’ for this reason, as the last value you put
 118 on the stack is the first one you retrieve from it.
 119
 120 Let’s try a three-deep example:
 121
 122 ```rust
 123 fn bar() {
 124     let i = 6;
 125 }
 126
 127 fn foo() {
 128     let a = 5;
 129     let b = 100;
 130     let c = 1;
 131
 132     bar();
 133 }
 134
 135 fn main() {
 136     let x = 42;
 137
 138     foo();
 139 }
 140 ```
 141
 142 Okay, first, we call `main()`:
 143
 144 | Address | Name | Value |
 145 |---------|------|-------|
 146 | 0       | x    | 42    |
 147
 148 Next up, `main()` calls `foo()`:
 149
 150 | Address | Name | Value |
 151 |---------|------|-------|
 152 | 3       | c    | 1     |
 153 | 2       | b    | 100   |
 154 | 1       | a    | 5     |
 155 | 0       | x    | 42    |
 156
 157 And then `foo()` calls `bar()`:
 158
 159 | Address | Name | Value |
 160 |---------|------|-------|
 161 | 4       | i    | 6     |
 162 | 3       | c    | 1     |
 163 | 2       | b    | 100   |
 164 | 1       | a    | 5     |
 165 | 0       | x    | 42    |
 166
 167 Whew! Our stack is growing tall.
 168
 169 After `bar()` is over, its frame is deallocated, leaving just `foo()` and
 170 `main()`:
 171
 172 | Address | Name | Value |
 173 |---------|------|-------|
 174 | 3       | c    | 1     |
 175 | 2       | b    | 100   |
 176 | 1       | a    | 5     |
 177 | 0       | x    | 42    |
 178
 179 And then `foo()` ends, leaving just `main()`:
 180
 181 | Address | Name | Value |
 182 |---------|------|-------|
 183 | 0       | x    | 42    |
 184
 185 And then we’re done. Getting the hang of it? It’s like piling up dishes: you
 186 add to the top, you take away from the top.
 187
 188 # The Heap
 189
 190 Now, this works pretty well, but not everything can work like this. Sometimes,
 191 you need to pass some memory between different functions, or keep it alive for
 192 longer than a single function’s execution. For this, we can use the heap.
 193
 194 In Rust, you can allocate memory on the heap with the [`Box<T>` type][box].
 195 Here’s an example:
 196
 197 ```rust
 198 fn main() {
 199     let x = Box::new(5);
 200     let y = 42;
 201 }
 202 ```
 203
 204 [box]: ../std/boxed/index.html
 205
 206 Here’s what happens in memory when `main()` is called:
 207
 208 | Address | Name | Value  |
 209 |---------|------|--------|
 210 | 1       | y    | 42     |
 211 | 0       | x    | ?????? |
 212
 213 We allocate space for two variables on the stack. `y` is `42`, as it always has
 214 been, but what about `x`? Well, `x` is a `Box<i32>`, and boxes allocate memory
 215 on the heap. The actual value of the box is a structure which has a pointer to
 216 ‘the heap’. When we start executing the function, and `Box::new()` is called,
 217 it allocates some memory for the heap, and puts `5` there. The memory now looks
 218 like this:
 219
 220 | Address         | Name | Value          |
 221 |-----------------|------|----------------|
 222 | 2<sup>30</sup>  |      | 5              |
 223 | ...             | ...  | ...            |
 224 | 1               | y    | 42             |
 225 | 0               | x    | 2<sup>30</sup> |
 226
 227 We have 2<sup>30</sup> in our hypothetical computer with 1GB of RAM. And since
 228 our stack grows from zero, the easiest place to allocate memory is from the
 229 other end. So our first value is at the highest place in memory. And the value
 230 of the struct at `x` has a [raw pointer][rawpointer] to the place we’ve
 231 allocated on the heap, so the value of `x` is 2<sup>30</sup>, the memory
 232 location we’ve asked for.
 233
 234 [rawpointer]: raw-pointers.html
 235
 236 We haven’t really talked too much about what it actually means to allocate and
 237 deallocate memory in these contexts. Getting into very deep detail is out of
 238 the scope of this tutorial, but what’s important to point out here is that
 239 the heap isn’t just a stack that grows from the opposite end. We’ll have an
 240 example of this later in the book, but because the heap can be allocated and
 241 freed in any order, it can end up with ‘holes’. Here’s a diagram of the memory
 242 layout of a program which has been running for a while now:
 243
 244
 245 | Address              | Name | Value                |
 246 |----------------------|------|----------------------|
 247 | 2<sup>30</sup>       |      | 5                    |
 248 | (2<sup>30</sup>) - 1 |      |                      |
 249 | (2<sup>30</sup>) - 2 |      |                      |
 250 | (2<sup>30</sup>) - 3 |      | 42                   |
 251 | ...                  | ...  | ...                  |
 252 | 3                    | y    | (2<sup>30</sup>) - 3 |
 253 | 2                    | y    | 42                   |
 254 | 1                    | y    | 42                   |
 255 | 0                    | x    | 2<sup>30</sup>       |
 256
 257 In this case, we’ve allocated four things on the heap, but deallocated two of
 258 them. There’s a gap between 2<sup>30</sup> and (2<sup>30</sup>) - 3 which isn’t
 259 currently being used. The specific details of how and why this happens depends
 260 on what kind of strategy you use to manage the heap. Different programs can use
 261 different ‘memory allocators’, which are libraries that manage this for you.
 262 Rust programs use [jemalloc][jemalloc] for this purpose.
 263
 264 [jemalloc]: http://www.canonware.com/jemalloc/
 265
 266 Anyway, back to our example. Since this memory is on the heap, it can stay
 267 alive longer than the function which allocates the box. In this case, however,
 268 it doesn’t.[^moving] When the function is over, we need to free the stack frame
 269 for `main()`. `Box<T>`, though, has a trick up its sleeve: [Drop][drop]. The
 270 implementation of `Drop` for `Box` deallocates the memory that was allocated
 271 when it was created. Great! So when `x` goes away, it first frees the memory
 272 allocated on the heap:
 273
 274 | Address | Name | Value  |
 275 |---------|------|--------|
 276 | 1       | y    | 42     |
 277 | 0       | x    | ?????? |
 278
 279 [drop]: drop.html
 280 [^moving]: We can make the memory live longer by transferring ownership,
 281            sometimes called ‘moving out of the box’. More complex examples will
 282            be covered later.
 283
 284
 285 And then the stack frame goes away, freeing all of our memory.
 286
 287 # Arguments and borrowing
 288
 289 We’ve got some basic examples with the stack and the heap going, but what about
 290 function arguments and borrowing? Here’s a small Rust program:
 291
 292 ```rust
 293 fn foo(i: &i32) {
 294     let z = 42;
 295 }
 296
 297 fn main() {
 298     let x = 5;
 299     let y = &x;
 300
 301     foo(y);
 302 }
 303 ```
 304
 305 When we enter `main()`, memory looks like this:
 306
 307 | Address | Name | Value |
 308 |---------|------|-------|
 309 | 1       | y    | 0     |
 310 | 0       | x    | 5     |
 311
 312 `x` is a plain old `5`, and `y` is a reference to `x`. So its value is the
 313 memory location that `x` lives at, which in this case is `0`.
 314
 315 What about when we call `foo()`, passing `y` as an argument?
 316
 317 | Address | Name | Value |
 318 |---------|------|-------|
 319 | 3       | z    | 42    |
 320 | 2       | i    | 0     |
 321 | 1       | y    | 0     |
 322 | 0       | x    | 5     |
 323
 324 Stack frames aren’t just for local bindings, they’re for arguments too. So in
 325 this case, we need to have both `i`, our argument, and `z`, our local variable
 326 binding. `i` is a copy of the argument, `y`. Since `y`’s value is `0`, so is
 327 `i`’s.
 328
 329 This is one reason why borrowing a variable doesn’t deallocate any memory: the
 330 value of a reference is just a pointer to a memory location. If we got rid of
 331 the underlying memory, things wouldn’t work very well.
 332
 333 # A complex example
 334
 335 Okay, let’s go through this complex program step-by-step:
 336
 337 ```rust
 338 fn foo(x: &i32) {
 339     let y = 10;
 340     let z = &y;
 341
 342     baz(z);
 343     bar(x, z);
 344 }
 345
 346 fn bar(a: &i32, b: &i32) {
 347     let c = 5;
 348     let d = Box::new(5);
 349     let e = &d;
 350
 351     baz(e);
 352 }
 353
 354 fn baz(f: &i32) {
 355     let g = 100;
 356 }
 357
 358 fn main() {
 359     let h = 3;
 360     let i = Box::new(20);
 361     let j = &h;
 362
 363     foo(j);
 364 }
 365 ```
 366
 367 First, we call `main()`:
 368
 369 | Address         | Name | Value          |
 370 |-----------------|------|----------------|
 371 | 2<sup>30</sup>  |      | 20             |
 372 | ...             | ...  | ...            |
 373 | 2               | j    | 0              |
 374 | 1               | i    | 2<sup>30</sup> |
 375 | 0               | h    | 3              |
 376
 377 We allocate memory for `j`, `i`, and `h`. `i` is on the heap, and so has a
 378 value pointing there.
 379
 380 Next, at the end of `main()`, `foo()` gets called:
 381
 382 | Address         | Name | Value          |
 383 |-----------------|------|----------------|
 384 | 2<sup>30</sup>  |      | 20             |
 385 | ...             | ...  | ...            |
 386 | 5               | z    | 4              |
 387 | 4               | y    | 10             |
 388 | 3               | x    | 0              |
 389 | 2               | j    | 0              |
 390 | 1               | i    | 2<sup>30</sup> |
 391 | 0               | h    | 3              |
 392
 393 Space gets allocated for `x`, `y`, and `z`. The argument `x` has the same value
 394 as `j`, since that’s what we passed it in. It’s a pointer to the `0` address,
 395 since `j` points at `h`.
 396
 397 Next, `foo()` calls `baz()`, passing `z`:
 398
 399 | Address         | Name | Value          |
 400 |-----------------|------|----------------|
 401 | 2<sup>30</sup>  |      | 20             |
 402 | ...             | ...  | ...            |
 403 | 7               | g    | 100            |
 404 | 6               | f    | 4              |
 405 | 5               | z    | 4              |
 406 | 4               | y    | 10             |
 407 | 3               | x    | 0              |
 408 | 2               | j    | 0              |
 409 | 1               | i    | 2<sup>30</sup> |
 410 | 0               | h    | 3              |
 411
 412 We’ve allocated memory for `f` and `g`. `baz()` is very short, so when it’s
 413 over, we get rid of its stack frame:
 414
 415 | Address         | Name | Value          |
 416 |-----------------|------|----------------|
 417 | 2<sup>30</sup>  |      | 20             |
 418 | ...             | ...  | ...            |
 419 | 5               | z    | 4              |
 420 | 4               | y    | 10             |
 421 | 3               | x    | 0              |
 422 | 2               | j    | 0              |
 423 | 1               | i    | 2<sup>30</sup> |
 424 | 0               | h    | 3              |
 425
 426 Next, `foo()` calls `bar()` with `x` and `z`:
 427
 428 | Address              | Name | Value                |
 429 |----------------------|------|----------------------|
 430 |  2<sup>30</sup>      |      | 20                   |
 431 | (2<sup>30</sup>) - 1 |      | 5                    |
 432 | ...                  | ...  | ...                  |
 433 | 10                   | e    | 9                    |
 434 | 9                    | d    | (2<sup>30</sup>) - 1 |
 435 | 8                    | c    | 5                    |
 436 | 7                    | b    | 4                    |
 437 | 6                    | a    | 0                    |
 438 | 5                    | z    | 4                    |
 439 | 4                    | y    | 10                   |
 440 | 3                    | x    | 0                    |
 441 | 2                    | j    | 0                    |
 442 | 1                    | i    | 2<sup>30</sup>       |
 443 | 0                    | h    | 3                    |
 444
 445 We end up allocating another value on the heap, and so we have to subtract one
 446 from 2<sup>30</sup>. It’s easier to just write that than `1,073,741,823`. In any
 447 case, we set up the variables as usual.
 448
 449 At the end of `bar()`, it calls `baz()`:
 450
 451 | Address              | Name | Value                |
 452 |----------------------|------|----------------------|
 453 |  2<sup>30</sup>      |      | 20                   |
 454 | (2<sup>30</sup>) - 1 |      | 5                    |
 455 | ...                  | ...  | ...                  |
 456 | 12                   | g    | 100                  |
 457 | 11                   | f    | 9                    |
 458 | 10                   | e    | 9                    |
 459 | 9                    | d    | (2<sup>30</sup>) - 1 |
 460 | 8                    | c    | 5                    |
 461 | 7                    | b    | 4                    |
 462 | 6                    | a    | 0                    |
 463 | 5                    | z    | 4                    |
 464 | 4                    | y    | 10                   |
 465 | 3                    | x    | 0                    |
 466 | 2                    | j    | 0                    |
 467 | 1                    | i    | 2<sup>30</sup>       |
 468 | 0                    | h    | 3                    |
 469
 470 With this, we’re at our deepest point! Whew! Congrats for following along this
 471 far.
 472
 473 After `baz()` is over, we get rid of `f` and `g`:
 474
 475 | Address              | Name | Value                |
 476 |----------------------|------|----------------------|
 477 |  2<sup>30</sup>      |      | 20                   |
 478 | (2<sup>30</sup>) - 1 |      | 5                    |
 479 | ...                  | ...  | ...                  |
 480 | 10                   | e    | 9                    |
 481 | 9                    | d    | (2<sup>30</sup>) - 1 |
 482 | 8                    | c    | 5                    |
 483 | 7                    | b    | 4                    |
 484 | 6                    | a    | 0                    |
 485 | 5                    | z    | 4                    |
 486 | 4                    | y    | 10                   |
 487 | 3                    | x    | 0                    |
 488 | 2                    | j    | 0                    |
 489 | 1                    | i    | 2<sup>30</sup>       |
 490 | 0                    | h    | 3                    |
 491
 492 Next, we return from `bar()`. `d` in this case is a `Box<T>`, so it also frees
 493 what it points to: (2<sup>30</sup>) - 1.
 494
 495 | Address         | Name | Value          |
 496 |-----------------|------|----------------|
 497 |  2<sup>30</sup> |      | 20             |
 498 | ...             | ...  | ...            |
 499 | 5               | z    | 4              |
 500 | 4               | y    | 10             |
 501 | 3               | x    | 0              |
 502 | 2               | j    | 0              |
 503 | 1               | i    | 2<sup>30</sup> |
 504 | 0               | h    | 3              |
 505
 506 And after that, `foo()` returns:
 507
 508 | Address         | Name | Value          |
 509 |-----------------|------|----------------|
 510 |  2<sup>30</sup> |      | 20             |
 511 | ...             | ...  | ...            |
 512 | 2               | j    | 0              |
 513 | 1               | i    | 2<sup>30</sup> |
 514 | 0               | h    | 3              |
 515
 516 And then, finally, `main()`, which cleans the rest up. When `i` is `Drop`ped,
 517 it will clean up the last of the heap too.
 518
 519 # What do other languages do?
 520
 521 Most languages with a garbage collector heap-allocate by default. This means
 522 that every value is boxed. There are a number of reasons why this is done, but
 523 they’re out of scope for this tutorial. There are some possible optimizations
 524 that don’t make it true 100% of the time, too. Rather than relying on the stack
 525 and `Drop` to clean up memory, the garbage collector deals with the heap
 526 instead.
 527
 528 # Which to use?
 529
 530 So if the stack is faster and easier to manage, why do we need the heap? A big
 531 reason is that Stack-allocation alone means you only have LIFO semantics for
 532 reclaiming storage. Heap-allocation is strictly more general, allowing storage
 533 to be taken from and returned to the pool in arbitrary order, but at a
 534 complexity cost.
 535
 536 Generally, you should prefer stack allocation, and so, Rust stack-allocates by
 537 default. The LIFO model of the stack is simpler, at a fundamental level. This
 538 has two big impacts: runtime efficiency and semantic impact.
 539
 540 ## Runtime Efficiency
 541
 542 Managing the memory for the stack is trivial: The machine just
 543 increments or decrements a single value, the so-called “stack pointer”.
 544 Managing memory for the heap is non-trivial: heap-allocated memory is freed at
 545 arbitrary points, and each block of heap-allocated memory can be of arbitrary
 546 size, the memory manager must generally work much harder to identify memory for
 547 reuse.
 548
 549 If you’d like to dive into this topic in greater detail, [this paper][wilson]
 550 is a great introduction.
 551
 552 [wilson]: http://www.cs.northwestern.edu/~pdinda/icsclass/doc/dsa.pdf
 553
 554 ## Semantic impact
 555
 556 Stack-allocation impacts the Rust language itself, and thus the developer’s
 557 mental model. The LIFO semantics is what drives how the Rust language handles
 558 automatic memory management. Even the deallocation of a uniquely-owned
 559 heap-allocated box can be driven by the stack-based LIFO semantics, as
 560 discussed throughout this chapter. The flexibility (i.e. expressiveness) of non
 561 LIFO-semantics means that in general the compiler cannot automatically infer at
 562 compile-time where memory should be freed; it has to rely on dynamic protocols,
 563 potentially from outside the language itself, to drive deallocation (reference
 564 counting, as used by `Rc<T>` and `Arc<T>`, is one example of this).
 565
 566 When taken to the extreme, the increased expressive power of heap allocation
 567 comes at the cost of either significant runtime support (e.g. in the form of a
 568 garbage collector) or significant programmer effort (in the form of explicit
 569 memory management calls that require verification not provided by the Rust
 570 compiler).