How do Array capacity and growth work, and when does an array give memory back?

3.10.5 · L3 · Interview

Predict first

Which operations shrink the buffer?

var c = Array(0..<1000); c.removeLast(990)
print("count", c.count, "capacity >= 1000:", c.capacity >= 1000)
print("Array(c) shrinks:", Array(c).capacity < 1000)
print("c.map { $0 } shrinks:", c.map { $0 }.capacity < 1000)
var d = c; d[0] = 5
print("copy made by a write shrinks:", d.capacity < 1000, " original keeps:", c.capacity >= 1000)
c.removeAll()
print("removeAll() releases the buffer:", c.capacity == 0)
var e = Array(0..<1000); e.removeAll(keepingCapacity: true)
print("keepingCapacity keeps it:", e.capacity >= 1000)
var a: [Int] = [], prev = a.capacity, geometric = true
for i in 0..<5000 { a.append(i); if a.capacity != prev { if prev > 0 && Double(a.capacity) < 1.5 * Double(prev) { geometric = false }; prev = a.capacity } }
print("every growth step at least 1.5x:", geometric)
  • count 10 capacity >= 1000: true / Array(c) shrinks: false / map shrinks: true / COW copy shrinks: true, original keeps: true / removeAll releases: true / keepingCapacity keeps: true / growth at least 1.5x: true
  • removeLast shrinks the buffer
  • Array(c) shrinks but map does not

Mental model. A moving van that only ever gets bigger: when the load shrinks you keep paying for the large van until you swap it for a smaller one on purpose.

An array has a count and a capacity. When an append exceeds capacity the array allocates a bigger buffer and moves the elements; the growth is geometric (the check asserts each step is at least 1.5 times the last), so appending n elements costs amortised O(1) each. The exact sequence is an implementation detail (the allocator rounds block sizes, so you see values like 36 or 76 rather than clean doublings), so rely on “at least as big as requested” and not on numbers. reserveCapacity(n) allocates once when you know the size, avoiding repeated moves.

The part interviews probe is shrinking: mutating methods never shrink. After removeLast(990) the array still has capacity for 1000; Array(c) returns the same buffer, so it does not shrink either; map creates a right-sized new buffer, and so does the copy made by a write to a shared array (the original keeps its big buffer). removeAll() releases the buffer (capacity 0) but removeAll(keepingCapacity: true) keeps it, which is the right choice for a reused scratch buffer. For a long-lived model that once held a huge list, rebuild it (items = items.map { $0 } or Array(items.lazy.map { $0 })) if memory matters. Dictionaries and sets grow by the same logic but with their own load-factor-based capacity.

Only rebuilding (map, a COW copy) or removeAll() gives memory back.

Common traps

  • Assuming removeLast or removeAll(where:) frees memory. Capacity stays.
  • Asserting exact capacity values in tests. They depend on the allocator and the Swift version.

They might follow up with

  • Does a copy-on-write copy keep the same capacity? No, the copy is sized for the elements it holds.
  • When is ContiguousArray better? For class element types on Apple platforms it avoids bridging checks; capacity rules are the same.

Related questions

  • 3.5.3 What is an Array in memory, and what is special about the empty array?
  • 3.5.4 Why does a mutation sometimes copy the whole array, and how do you prove it?
  • 3.10.4 Why can a small slice keep a large array (or string) alive, and how do you stop it?

← Why can a small slice keep a large array (or string) alive, and how…   Which command-line tools inspect a running process’s memory on macOS… →