Is a String array e.g. [String; 3] stored on the stack or heap?

Question

The Rust book specifies that:

Another property that makes the stack fast is that all data on the stack must take up a known, fixed size.

It also says that String is stored on the heap as the size is not known and can mutate.

Where are "composite" data structures such as arrays containing String stored? The array is fixed in size however the components of the array can change in size.

let array: [String; 3] = ["A","B","C"];

What is the rule for where such "composite" data types are stored?

Matthieu M. Matthieu M. · Accepted Answer · 2017-11-08T12:42:34

Both.

A point of terminology: when discussing the memory layout of a type, one should not talk about stack vs heap, but about inline vs offline¹:

inline means that the data is right here,
offline means that the data is available behind a pointer (wherever it points).

An easy example, integers are stored inline:

//  i32
+---+
| 3 |
+---+

A typical struct Point { x: i32, y: i32 } is also stored inline:

//  Point
+---+---+
| x | y |
+---+---+

A String, typically represented as struct String { data: *mut u8, len: usize, cap: usize } is stored both inline and offline:

//   String
+-------+-------+-------+
| data  |  len  |  cap  |
+-------+-------+-------+
    |
     \
      +-------------+
      |Hello, World!|
      +-------------+

The inline part is 3 pointers worth of storage, and the offline part, is a heap-allocated record containing the content of the string "Hello, World!" here.

However, inline does not always mean stack. A Box<Point>:

//  Box<Point>
+-------+
| data  |
+-------+
    |
     \
      +---+---+
      | x | y |
      +---+---+

Stores its Point (which stores its data members inline) on the heap!

And similarly, offline does not always mean heap:

fn main() {
    let i = 3;
    let r = &i;
}

Here, r is a reference (pointer), which points to i, and i is on the stack!

¹Yes, I am making this up, better terms would be appreciated.

So, back to the question:

It also says that String is stored on the heap as the size is not known and can mutate.

This is an approximation, as mentioned above the String has some of its data inline (pointer, length and capacity) and some on the heap (the string content).

Where are "composite" data structures such as arrays containing String stored? The array is fixed in size however the components of the array can change in size.
let array: [String; 3] = ["A","B","C"];

It is stored both on the stack and heap:

//  [String; 3]
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
| data  |  len  |  cap  | data  |  len  |  cap  | data  |  len  |  cap  |
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
    |                       |                       |    
     \                       \                       \
      +-+                     +-+                     +-+
      |A|                     |B|                     |C|
      +-+                     +-+                     +-+

That's 9 pointers' worth of data inline (here on the stack), and 3 separate allocations on the heap.

What is the rule for where such "composite" data types are stored?

Data-members are always inline, pointers and references may point to offline data, which may be on the heap, on the stack, etc...

Is a String array e.g. [String; 3] stored on the stack or heap?

2 Answers