How can I make a container with copy-on-write semantics? (Swift)

Question

I have a very large structure, which I want to ensure is not copied needlessly. How can I make a copy-on-write container for it?

Chromo

What kind of large structure do you have? I am asking because Swift already does (part of) the job for you. See #26594492 – Malda

@AntonBronnikov: I am aware of these optimizations. This question was meant to be an educational Q/A tutorial. – Chromo

I understand. That's why I ask about the kind of large structure this is intended for. The fact that such educational Q/A exists suggests that there is a need for it (e.g. what if not all use cases are covered by Swift compiler optimisations?). It would only put things into a better picture if you could mention applicable use cases, as otherwise it would be a waste of effort to do/maintain something that Swift would do for you anyway and at no cost. – Malda

In Swift 4, use isKnownUniquelyReferenced instead of isUniquelyReferenced – Acceptance

Answer 1

A copy-on-write is usually a struct wrapper over some backing object.

public final class MutableHeapStore<T>: NonObjectiveCBase
{
    public typealias Storage = T

    public private(set) var storage: Storage

    public init(storage: Storage)
    {
        self.storage = storage
    }
}

public struct COW<T>
{
    public typealias Storage = MutableHeapStore<T>
    public typealias Value = T

    public var storage: Storage

    public init(storage: Storage)
    {
        self.storage = storage
    }

    public var value: Value
    {
        get
        {
            return storage.storage
        }

        set
        {
            if isUniquelyReferenced(&storage)
            {
                storage.storage = newValue
            }

            else
            {
                storage = Storage(storage: newValue)
            }
        }
    }

    public init(_ value: Value)
    {
        self.init(storage: Storage(storage: value))
    }
}

extension COW: CustomStringConvertible
{
    public var description: String
    {
        return String(value)
    }
}

The trick lies in asserting isUniquelyReferenced every time the boxed value is mutated. If the underlying storage object is singly referenced, nothing is to be done. However if another reference exists, one must create a new storage.

Is this code thread-safe? It is exactly as safe as any other value type, e.g. Int or Bool.

Chromo

seem like the code in the isUniquelyReferenced never got chance be executed, I add a print statement inside, never got the output – Irresponsive

Answer 2

The previous answers aren't wrong, but there's a much simpler way. The Swift team has a list of performance tips, and they say:

The easiest way to implement copy-on-write is to compose existing copy-on-write data structures, such as Array.

It doesn't get much simpler than that!

Predictor

Good advice, especially for beginners. – Chromo

Not just for beginners -- that document specifically says "The intended audience of this document is compiler and standard library developers." – Predictor

Answer 3

Here's a bit simpler example.

struct COWExample1<T> {
    private var box = Box<[T]>(value: [T]())
    var count: Int {
        return box.value.count
    }
    mutating func append(e: T) {
        ensureBoxUniqueRefed()
        box.value.append(e)
    }
    private mutating func ensureBoxUniqueRefed() {
        if isUniquelyReferencedNonObjC(&box) == false {
            box = box.duplicated()
        }
    }
}

private final class Box<T> {
    var value: T
    init(value: T) {
        self.value = value
    }
    func duplicated() -> Box<T> {
        return Box(value: value)
    }
}

Cheapen