src/doc/rustc-dev-guide/src/memory.md

   1 # Memory Management in Rustc
   2
   3 Rustc tries to be pretty careful how it manages memory. The compiler allocates
   4 _a lot_ of data structures throughout compilation, and if we are not careful,
   5 it will take a lot of time and space to do so.
   6
   7 One of the main way the compiler manages this is using arenas and interning.
   8
   9 ## Arenas and  Interning
  10
  11 We create a LOT of data structures during compilation. For performance reasons,
  12 we allocate them from a global memory pool; they are each allocated once from a
  13 long-lived *arena*. This is called _arena allocation_. This system reduces
  14 allocations/deallocations of memory. It also allows for easy comparison of
  15 types for equality: for each interned type `X`, we implemented [`PartialEq for
  16 X`][peqimpl], so we can just compare pointers. The [`CtxtInterners`] type
  17 contains a bunch of maps of interned types and the arena itself.
  18
  19 [peqimpl]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.TyS.html#implementations
  20 [`CtxtInterners`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.CtxtInterners.html#structfield.arena
  21
  22 ### Example: `ty::TyS`
  23
  24 Taking the example of [`ty::TyS`] which represents a type in the compiler (you
  25 can read more [here](./ty.md)).  Each time we want to construct a type, the
  26 compiler doesn’t naively allocate from the buffer.  Instead, we check if that
  27 type was already constructed. If it was, we just get the same pointer we had
  28 before, otherwise we make a fresh pointer. With this schema if we want to know
  29 if two types are the same, all we need to do is compare the pointers which is
  30 efficient. `TyS` is carefully setup so you never construct them on the stack.
  31 You always allocate them from this arena and you always intern them so they are
  32 unique.
  33
  34 At the beginning of the compilation we make a buffer and each time we need to allocate a type we use
  35 some of this memory buffer. If we run out of space we get another one. The lifetime of that buffer
  36 is `'tcx`. Our types are tied to that lifetime, so when compilation finishes all the memory related
  37 to that buffer is freed and our `'tcx` references would be invalid.
  38
  39 In addition to types, there are a number of other arena-allocated data structures that you can
  40 allocate, and which are found in this module. Here are a few examples:
  41
  42 - [`Substs`][subst], allocated with `mk_substs` – this will intern a slice of types, often used to
  43   specify the values to be substituted for generics (e.g. `HashMap<i32, u32>` would be represented
  44   as a slice `&'tcx [tcx.types.i32, tcx.types.u32]`).
  45 - [`TraitRef`], typically passed by value – a **trait reference** consists of a reference to a trait
  46   along with its various type parameters (including `Self`), like `i32: Display` (here, the def-id
  47   would reference the `Display` trait, and the substs would contain `i32`). Note that `def-id` is
  48   defined and discussed in depth in the `AdtDef and DefId` section.
  49 - [`Predicate`] defines something the trait system has to prove (see `traits` module).
  50
  51 [subst]: ./generic_arguments.html#subst
  52 [`TraitRef`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.TraitRef.html
  53 [`Predicate`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.Predicate.html
  54
  55 [`ty::TyS`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.TyS.html
  56
  57 ## The tcx and how it uses lifetimes
  58
  59 The `tcx` ("typing context") is the central data structure in the compiler. It is the context that
  60 you use to perform all manner of queries. The struct `TyCtxt` defines a reference to this shared
  61 context:
  62
  63 ```rust,ignore
  64 tcx: TyCtxt<'tcx>
  65 //          ----
  66 //          |
  67 //          arena lifetime
  68 ```
  69
  70 As you can see, the `TyCtxt` type takes a lifetime parameter. When you see a reference with a
  71 lifetime like `'tcx`, you know that it refers to arena-allocated data (or data that lives as long as
  72 the arenas, anyhow).
  73
  74 ### A Note On Lifetimes
  75
  76 The Rust compiler is a fairly large program containing lots of big data
  77 structures (e.g. the AST, HIR, and the type system) and as such, arenas and
  78 references are heavily relied upon to minimize unnecessary memory use. This
  79 manifests itself in the way people can plug into the compiler (i.e. the
  80 [driver](./rustc-driver.md)), preferring a "push"-style API (callbacks) instead
  81 of the more Rust-ic "pull" style (think the `Iterator` trait).
  82
  83 Thread-local storage and interning are used a lot through the compiler to reduce
  84 duplication while also preventing a lot of the ergonomic issues due to many
  85 pervasive lifetimes. The [`rustc::ty::tls`][tls] module is used to access these
  86 thread-locals, although you should rarely need to touch it.
  87
  88 [tls]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/tls/index.html