Lesson 02 of 05 · published

Copy-on-Write Tiles

~15 min · copy-on-write, tiles, undo, swift, memory

Level 0Blank Canvas

0 XP0/37 lessons0/12 achievements

0/100 XP to next level100 XP to go0% complete

Many Holders, One Tile

A tile in a painting app is never wanted by just one party. The live layer writes it. Undo needs what it looked like before the stroke and after. A save in flight needs a picture of it that will not change while a background thread compresses it. A duplicated layer starts out identical to it. A Transform, an Adjustment, a Liquify or a Text edit keeps the layer as it was when the session began, so it can preview against the original and commit once.

The simple answer is to give each holder its own copy, and for the first three hours of Ariandel's life that is what the engine did. A stroke copied every tile it touched twice, once for undo's before-state and once for its after-state, and undoing copied again on the way back. Commit 6479f1f replaced that with copy-on-write tiles, and the contract is short enough to hold in your head.

The Contract

A TileBuffer is written in place until something besides the live store takes hold of it. Taking hold freezes it, and a frozen buffer is never written again: the store swaps in a copy before its next write. In code that is one flag and one method. freeze() sets isFrozen and returns the buffer. fill, the one writing method on the buffer itself, opens with precondition(!isFrozen, "a frozen tile is never written"). The thread rule rides along: only the thread that owns the artwork freezes or writes, and once frozen, any thread may read the pixels. That is why FrozenTile can declare @unchecked Sendable; its own comment says so plainly: the invariant, not a lock, is what makes the conformance true.

One Door: writableTile(at:)

TileStore.writableTile(at:) is the only way to a writable buffer, and the project's house rules repeat it as a prohibition: never write tile.pixels you did not get from writableTile or allocate yourself. The method does four things, in order (first code block):

Records the before-state through noteWrite, if a change is being recorded.
Marks the tile dirty, so the GPU mirror re-uploads it (lesson five).
Copies the tile if it is frozen, puts the copy in the store, and returns the copy.
Creates a transparent tile if none exists.

Its neighbor setTile is not a second door. It replaces a tile wholesale (undo, file load, layer operations) and takes the buffer as it is: hand it a frozen buffer and the store holds a frozen buffer, which the next write through writableTile will copy.

The Before-State Costs Nothing Extra

Here is the trick that turns two copies into one. noteWrite does not copy the current buffer into the recording. It freezes it there. Now the recording owns the old pixels, the store still points at the same object, and step 3 of writableTile notices the freeze and copies. The copy that undo needed and the copy that writing needed are the same copy. After the first touch, the store's tile is that fresh, unfrozen copy, so the remaining dabs of the stroke write in place for free. For a plain stroke, that is one copy per touched tile for the whole stroke, however many dabs land on it. The compiled sketch below counts exactly that.

Two details are worth copying. First, noteWrite uses updateValue, not subscript assignment, because assigning nil through a dictionary subscript removes the key, and "this tile did not exist" is precisely the before-state undo must restore. That comment has a history: the commit that gave Ariandel its undo history, twenty-three minutes after the repository was born, fixed exactly that bug, where undo could not remove tiles a stroke had created. Second, there are two recordings: recording, per stroke or undo step, and batchRecording, per batch of dabs, which a stroke opens only when it is limited to a selection or laid through a grain (dual-brush and clone strokes keep batch recordings on stores of their own). The batch recording freezes too, so those strokes pay one copy per touched tile per batch, still bounded by what they touch, never by what the layer holds.

libmypaint at the Door

The engine reaches the store through two C callbacks, always on the artwork's thread and always inside a call Swift made. Most requests come during ard_surface_end, when libmypaint renders the dabs it queued. Some come earlier, inside mypaint_brush_stroke_to. A brush that smudges samples color as it goes, and libmypaint's get_color first flushes that tile's queued dabs and then reads it. A shaped dab skips the queue altogether, so the bridge acquires each tile it writes on the spot and holds it until ard_surface_end releases the batch. A read-only acquire gets tiles[key]?.pixels: whatever buffer is there, frozen or not, since reading a frozen buffer is always allowed; for an absent tile it gets nil, and the bridge lends its own shared transparent tile. A writable acquire goes through the one door, writableTile(at: key).pixels, so even libmypaint's writes land in a copy when the tile is shared. A writable release marks the tile dirty. If the store ever failed to lend a writable buffer, the bridge would lend a scratch tile and discard its paint rather than write somewhere it should not. Track 2 walks through how those function pointers carry the store across the C boundary.

Make the expensive thing happen at the one moment it is unavoidable, and nowhere else. Sharing is free and copying costs 32 KiB, so Ariandel copies at the first write to a shared tile and at no other time: not when a save starts, not when history records, not when a layer is duplicated.

Code

The only way to a writable buffer (AriandelEngine/Tiles.swift, verbatim)·swift

    /// The tile at `key`, writable: created transparent if absent, copied
    /// first if a holder shares it. Records the before-state when a change is
    /// being recorded, and marks the tile dirty.
    public func writableTile(at key: TileKey) -> TileBuffer {
        noteWrite(key)
        dirty.insert(key)
        if let tile = tiles[key] {
            guard tile.isFrozen else { return tile }
            let copy = tile.copy()
            tiles[key] = copy
            return copy
        }
        let tile = TileBuffer()
        tiles[key] = tile
        return tile
    }

The before-state is a freeze, not a copy (AriandelEngine/Tiles.swift, verbatim)·swift

    private func noteWrite(_ key: TileKey) {
        // Holding the current buffer freezes it, so the write that follows
        // lands in a copy: the before-state costs one copy, not two.
        // updateValue, not subscript assignment: assigning nil would drop the
        // key, and an absent before-state is exactly what undo must restore.
        if recording != nil, recording?.index(forKey: key) == nil {
            recording?.updateValue(tiles[key]?.freeze(), forKey: key)
        }
        if batchRecording != nil, batchRecording?.index(forKey: key) == nil {
            batchRecording?.updateValue(tiles[key]?.freeze(), forKey: key)
        }
    }

A minimal sketch of the same store, counting copies (pixels shrunk to four values; compiled and run with swiftc in Swift 6 mode)·swift

// A minimal sketch of Ariandel's copy-on-write tile store: freeze() marks a
// buffer shared, writableTile(at:) is the only way to a writable buffer.
final class Buffer {
    var pixels: [UInt16]
    private(set) var isFrozen = false
    init(_ pixels: [UInt16] = Array(repeating: 0, count: 4)) { self.pixels = pixels }
    func copy() -> Buffer { Buffer(pixels) }
    @discardableResult func freeze() -> Buffer { isFrozen = true; return self }
}

final class Store {
    private(set) var tiles: [Int: Buffer] = [:]
    private(set) var dirty: Set<Int> = []
    var copies = 0
    private var recording: [Int: Buffer?]?

    func writableTile(at key: Int) -> Buffer {
        noteWrite(key)
        dirty.insert(key)
        if let tile = tiles[key] {
            guard tile.isFrozen else { return tile }
            let copy = tile.copy()
            copies += 1
            tiles[key] = copy
            return copy
        }
        let tile = Buffer()
        tiles[key] = tile
        return tile
    }

    func beginRecording() { recording = [:] }
    func endRecording() -> [Int: Buffer?] { defer { recording = nil }; return recording ?? [:] }

    private func noteWrite(_ key: Int) {
        // Freezing the current buffer IS the before-state: no copy here.
        if recording != nil, recording?.index(forKey: key) == nil {
            recording?.updateValue(tiles[key]?.freeze(), forKey: key)
        }
    }

    func snapshot(of keys: some Sequence<Int>) -> [Int: Buffer?] {
        var s: [Int: Buffer?] = [:]
        for key in keys { s.updateValue(tiles[key]?.freeze(), forKey: key) }
        return s
    }

    func frozenTiles() -> [(key: Int, tile: Buffer)] {
        tiles.keys.sorted().map { ($0, tiles[$0]!.freeze()) }
    }
}

let store = Store()

// Stroke 1: touches tiles 0 and 1, each many times (one dab per call).
store.beginRecording()
for _ in 0..<50 { for key in [0, 1] { store.writableTile(at: key).pixels[0] &+= 1 } }
var before = store.endRecording()
var after = store.snapshot(of: before.keys)
print("stroke 1: copies =", store.copies, "(both tiles were absent: created, not copied)")

// Stroke 2: touches tile 1 again, fifty dabs.
store.copies = 0
store.beginRecording()
for _ in 0..<50 { store.writableTile(at: 1).pixels[0] &+= 1 }
before = store.endRecording()
after = store.snapshot(of: before.keys)
print("stroke 2: copies =", store.copies, "(one per touched tile, not one per dab)")
print("undo's before-state of tile 1 =", before[1]!!.pixels[0], " after-state =", after[1]!!.pixels[0])
print("after-state is the live tile:", after[1]!! === store.tiles[1]!)

// A save freezes every tile instead of copying it.
store.copies = 0
let archive = store.frozenTiles()
print("save: copies =", store.copies, " tiles in archive =", archive.count)

// Painting goes on; the archive never sees it.
for _ in 0..<10 { store.writableTile(at: 0).pixels[0] &+= 1 }
print("after more paint: archive tile 0 =", archive[0].tile.pixels[0],
      " live tile 0 =", store.tiles[0]!.pixels[0], " copies =", store.copies)

// Output (swiftc -swift-version 6):
// stroke 1: copies = 0 (both tiles were absent: created, not copied)
// stroke 2: copies = 1 (one per touched tile, not one per dab)
// undo's before-state of tile 1 = 50  after-state = 100
// after-state is the live tile: true
// save: copies = 0  tiles in archive = 2
// after more paint: archive tile 0 = 50  live tile 0 = 60  copies = 1

External links

Exercise

Find a place in your own code that snapshots mutable data by copying it: an undo stack, an autosave, a cache of last-known state. Add a sticky frozen flag to the thing being copied, route every write through one method that copies only when the flag is set, and make the snapshot freeze instead of copy. Then count copies for one realistic user action before and after.

Hint

Start by grepping for every place that writes the underlying storage directly. If you cannot make all of them go through one method, the scheme is not safe yet: one stray writer is enough to corrupt every snapshot that shares the buffer.

Progress

Progress is local-only — sign in to sync across devices.

← PreviousSixty-Four Squared, in Fix15 Next →The Autosave That Copied Everything

Spotted a bug or have feedback on this page?Report an Issue

Comments 0

🔔 Reply notifications (sign in)

No comments yet — be the first.