Implementing a concurrency-safe collection

Using Swift
1

Conformance requirements mean that an async method cannot be used for an async-less conformance method. A wrapping type can be used, but it still requires turning an async function call to a non-async result. How do you bring async function calls back to non-async code?

2

There's some disconnect here between the subject and the question :)

As for moving between async and sync worlds:

  • if the function in question doesn't return anything and could be done "asynchronously" to the caller (i.e. it's effects could happen after you returned to the caller of a sync function) – then it's easy, just wrap async call in Task { await someAsyncWork() }
  • otherwise if the function has a result but still could happen "asynchronously" after returning from a sync call to the caller, and you could modify the sync function to take a callback parameter - Task { let result = await someAsyncWork(); callback(result) }
  • otherwise (have result, and either need the sync behaviour or can't use a callback e.g. because you can't change the API) - you'd have to block the caller:
func someAsyncWork() async -> Int { 42 }

func foo() -> Int {
    nonisolated(unsafe) var result = 0
    let group = DispatchGroup()
    group.enter()
    Task { @Sendable in
        result = await someAsyncWork()
        group.leave()
    }
    group.wait()
    return result
}
3

Think there are two questions here:

  1. Implementing a concurrency-safe collection
  2. How do you bring async function calls back to non-async code?

For both think answer is to design your system correctly—you don't make collections and data structures concurrent and keep them low level, but owners of this code should reason about how they've communicating with outside world and update inner state accordingly, and abstract it (make concurrent or something else).

4

It’s #2, so I can implement #1.

5

I’m using the question to implement the subject. Wouldn’t the only two places needed to be concurrency-safe are the MutableCollection and RangeReplaceableCollection parts; everything else should be read-only?

1 Like
6

The Collection protocol is fundamentally concurrency-unsafe.

A concurrency-safe collection can't expose a count, can't expose indexes or allow indexing according to normal Swift conventions, can't directly expose iterators, etc.

Examples of concurrency-safe collections (not Collections) you can create are:

  • stack (expose only push(_: Element) & pop() -> Element?)
  • queue (similarly)
  • deque (similarly)
  • priority queue (similarly)

You can also safely offer "snapshot" functionality, which offers a read-only view of the contents at a particular moment of time, where the snapshot can be a Collection.

2 Likes
7

Great summary, thank you!

To OP: what is your use case, in other words why you want that?

Say you want to use one of those simpler concurrency-safe containers like stack (with only push & pop exposed). And say you need to atomically pop from one and push onto another. You'd need to protect it yourself (mutex, actors, queues, etc):

// pseudocode:
protect somehow {
    element = stack1.pop()
    stack2.push(element)
}

And if you only deal with one stack - it could still be:

// pseudocode:
protect somehow {
    stack1.push(element)
}