What is an Array in memory, and what is special about the empty array?

3.5.3 · L5 · Learning

Predict first

What does this print?

print(MemoryLayout<[Int]>.size, [Int]().capacity)
  • 24 0
  • 8 0
  • 8 8

Mental model. An array variable is a key to a storage unit. Copies of the key are free, and the unit is only duplicated when two key-holders want different contents.

An Array value is a single pointer to a heap buffer object, so MemoryLayout<[Int]>.size is 8 bytes however many elements it holds. The buffer starts with a header (type, reference count, element count, and capacity with some flags) followed by the elements stored contiguously. Copying an array copies the pointer and bumps the buffer’s count, which is the whole of “copy-on-write”.

The empty array is special: all empty arrays share one static singleton buffer, so creating [] allocates nothing and its capacity is 0. The first append allocates a real buffer, and later growth reallocates to a larger one. Dictionary and Set follow the same handle-to-buffer design, and a String is a 16-byte value that holds up to 15 UTF-8 bytes inline, so short strings allocate nothing either.

The array value is one 8-byte pointer, and the empty array has no storage of its own, so its capacity is 0.

Common traps

  • Thinking [] allocates. It points at a shared static buffer.
  • Equating array size with the byte size of its elements. The value is 8 bytes; the elements live elsewhere.

They might follow up with

  • Why does growth double? To make appends O(1) amortised; see the array growth question in the collections section.
  • Where do class-element arrays differ? On Apple platforms they may be backed by an NSArray, which is why ContiguousArray exists.

Related questions

  • 2.1.4 How does an Array grow, and when do reserveCapacity and ContiguousArray help?
  • 3.4.2 What do MemoryLayout’s size, stride and alignment mean, and why does field order matter?
  • 1.1.7 What is copy-on-write? Which types use it?

← What exactly does isKnownUniquelyReferenced check, and how do you…   Why does a mutation sometimes copy the whole array, and how do you… →