Swift Herding CoWs

CoW is an important part of several swift collections including Array, Dictionary and Set. This is quite a great feature for many applications. However, I'm usually busy with latency critical systems and CoW sometimes gives an interesting result.

I remember a basic structure that I had back in time and it was efficient: 

struct Storage<V: Sendable>: ~Copyable, Sendable {
    enum State: Sendable {
        case empty
        case payload([V])
    }
    private let state: Mutex<State>

    func add(value: V) {
        state.withLock { state in
            switch state {
            case .payload(var array):
                array.append(value)
                state = .payload(array)
            case .empty:
                state = .payload([value])
            }
        }
    }
}

What could be easier! A lot of things were built using this pattern and swift compiler knows that pattern and optimizes it very well. Indeed, this code works great: 

Array in enum: add()
╒═══════════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                        │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Instructions *                │        54 │        54 │        54 │        54 │        54 │        54 │        75 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Malloc (total) *              │         0 │         0 │         0 │         0 │         0 │         0 │         0 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Memory (resident peak) (M)    │        11 │        12 │        12 │        12 │        12 │        12 │        12 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Throughput (# / s) (M)        │       353 │       325 │       320 │       316 │       304 │       261 │        33 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Time (total CPU) (ns) *       │         4 │         4 │         4 │         5 │         5 │         6 │        34 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Time (wall clock) (ns) *      │         3 │         3 │         3 │         3 │         3 │         4 │        30 │    100000 │
╘═══════════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛

4-5ns for pre-allocated array! No additional allocations, just 54 instructions.

At some point in time I had to add a new function that allows access to this internal collection: 

extension Storage {
    func addOrModify(value: V, _ modifier: (inout [V]) throws -> ()) rethrows {
        try state.withLock { state in
            switch state {
            case .payload(var array):
                try modifier(&array)
                state = .payload(array)
            case .empty:
                state = .payload([value])
            }
        }
    }
}

What potentially could go wrong? Well…

Array in enum: addOrModify()
╒═══════════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                        │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Instructions *                │      1835 │      1835 │      1835 │      1835 │      1839 │      1848 │      1868 │     49030 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Malloc (total) *              │         1 │         1 │         1 │         1 │         1 │         1 │         1 │     49030 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Memory (resident peak) (M)    │        11 │        12 │        12 │        12 │        12 │        12 │        12 │     49030 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Throughput (# / s) (M)        │        15 │        14 │        13 │        13 │        13 │        12 │         7 │     49030 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Time (total CPU) (ns) *       │        69 │        74 │        76 │        78 │        80 │        87 │       113 │     49030 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Time (wall clock) (ns) *      │        67 │        72 │        75 │        76 │        79 │        86 │       139 │     49030 │
╘═══════════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛

Wow - 67-87ns. It is more than 15x slower!

Let’s look at stacks, maybe we will be able to find something interesting.

Stacks before:
Flame graph of stacks before the change — a shallow, mostly inlined call tree.
Stacks after:
Flame graph of stacks after the change — deep call tree with Array copy-on-write, allocations and releases.

Feels some difference… Some allocations, deallocations, retains, releases. But I don’t have any classes!

What is it?

It is CoW.

But why? We did not do any copies - refcount must’ve been equal to 1. Not exactly, compiler does copy when it sees var in payload case but previously optimizer could eliminate it. Then - why it could not do that now?

It tried but it failed because of try.

How this code looks for compiler:

  1. We need to copy array
  2. We need to provide its mutating copy closure
  3. If closure succeeded - we return this array back
  4. If closure fails - we should - ?

We should leave the state untouched. That is the reason why refcount is 2. Therefore modifier closure on modification does copy.

Let’s compare previous code and how that code looked for compiler:

  1. We need to copy array // retain count for original
  2. We need to mutate it
  3. We need to copy it back // release count from original + retain count on copying to original + release count copy

Optimizer can see - okay, here we have 2 retains + 2 releases and they can be eliminated because there are no side effects here.

Let’s try to help compiler and say that we will always return the same array back: 

func addOrModify(value: V, _ modifier: (inout [V]) throws -> ()) rethrows {
    try state.withLock { state in
        switch state {
        case .payload(var array):
            do {
                try modifier(&array)
            } catch {
                state = .payload(array)
                throw error
            }
            state = .payload(array)
        case .empty:
            state = .payload([value])
        }
    }
}

How this code looks like now:

  1. We need to copy array // retain count for original
  2. We need to mutate it
  3. If succeed - we need to copy it back // release count from original + retain count on copying to original + release count copy
  4. If fail - we need to copy it back // release count from original + retain count on copying to original + release count copy

So, we tried to explain to compiler what we wanted, result:

Array in enum: addOrModify+HelpCompiler()
╒═══════════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                        │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Instructions *                │        50 │        50 │        50 │        50 │        50 │        50 │        67 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Malloc (total) *              │         0 │         0 │         0 │         0 │         0 │         0 │         0 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Memory (resident peak) (M)    │        11 │        12 │        12 │        12 │        12 │        12 │        12 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Throughput (# / s) (M)        │       364 │       325 │       320 │       312 │       308 │       282 │        46 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Time (total CPU) (ns) *       │         4 │         4 │         5 │         5 │         5 │         6 │        20 │    100000 │
├───────────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Time (wall clock) (ns) *      │         3 │         3 │         3 │         3 │         3 │         4 │        22 │    100000 │
╘═══════════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛

What is bad with this code - it is not the same - it will not rollback the state if modifier changed the array. I did not need that but if you need - you will not be able not to copy array with basic manipulations.

Instead of conclusion: be careful when you are herding your CoWs - they can escape.

← back