How do you implement copy-on-write for your own struct?

3.5.1 · L3 · Interview

Predict first

How many times is the storage copied? (Using the Bag type above.)

var a = Bag()
a.add(1)
var b = a
b.add(2)
a.add(3)
print(Bag.copies)
  • 0
  • 1
  • 2

Predict first

How many copies if you never share?

var a = Bag()
a.add(1)
a.add(2)
a.add(3)
print(Bag.copies)
  • 0
  • 1
  • 3

Mental model. Everyone shares one master document through a link. The first person who wants to edit makes their own copy and edits that one.

Wrap the data in a private final class (the storage) and keep a single reference to it inside your struct. Reading goes straight to the storage. Every mutating method first asks isKnownUniquelyReferenced(&storage): if the answer is no, someone else shares the storage, so clone it into a new object and assign that, then mutate. A plain struct copy just copies the reference, which is why copying is O(1) until the first write.

Three rules keep it correct. Do the check in every mutating entry point, with no exceptions. Keep the storage private so nobody can mutate it behind your back. And never hand out the storage reference, or a cached copy of it, because that makes the object permanently non-unique and every write copies. Without this pattern a struct with a class property is a shallow copy that shares mutable state, which is the classic “value type that isn’t one” bug.

b.add(2) finds the storage shared and copies once. After that a is the only owner of the original, so a.add(3) does not copy.

A uniquely referenced storage is mutated in place, however many times you write.

Code

final class Storage {
    var items: [Int]
    init(_ items: [Int]) { self.items = items }
}

struct Bag {
    private var storage = Storage([])
    nonisolated(unsafe) static var copies = 0

    mutating func add(_ x: Int) {
        if !isKnownUniquelyReferenced(&storage) {
            storage = Storage(storage.items)
            Bag.copies += 1
        }
        storage.items.append(x)
    }
    var items: [Int] { storage.items }
}

var a = Bag()
a.add(1)
var b = a        // both share one Storage
a.add(2)         // not unique: copies here
b.add(9)         // b now owns the old Storage alone: no copy
print(a.items, b.items, Bag.copies)
[1, 2] [1, 9] 1

Common traps

  • Forgetting the uniqueness check in one mutator. That method then mutates storage shared with other values.
  • Checking isKnownUniquelyReferenced on a local copy. The copy itself adds a reference, so the answer is always no.

They might follow up with

  • Is the copy O(n)? Yes, once, when sharing is first broken. After that each value has its own storage.
  • Does reading need the check? No. Only writes do.

Related questions

  • 3.1.2 What is a reference count, and how do you check that you hold the only reference?
  • 3.5.2 What exactly does isKnownUniquelyReferenced check, and how do you defeat it by accident?
  • 1.1.7 What is copy-on-write? Which types use it?

What exactly does isKnownUniquelyReferenced check, and how do you… →