How to achieve thread safety for removeAtIndex when array has concurrent reads in Swift?

Question

I was looking at this answer that provides code for a thread safe array with concurrent reads. As @tombardey points out in the comments the code (relevant snippet below) is not completely safe:

public func removeAtIndex(index: Int) {

    self.accessQueue.async(flags:.barrier) {
        self.array.remove(at: index)
    }
}

public var count: Int {
    var count = 0

    self.accessQueue.sync {
        count = self.array.count
    }

    return count
}

...Say the sychronized array has one element, wouldn't this fail? if synchronizedArray.count == 1 { synchronizedArray.remove(at: 0) } It's a race condition, say two threads execute the statement. Both read a count of 1 concurrently, both enqueue a write block concurrently. The write blocks execute sequentially, the second one will fail... (cont.)

@Rob replies:

@tombardey - You are absolutely right that this level of synchronization (at the property/method level) is frequently insufficient to achieve true thread-safety in broader applications. Your example is easily solved (by adding an method that dispatches block to the queue), but there are others that aren't (e.g. "synchronized" array simultaneously used by a UITableViewDataSource and mutated by some background operation). In those cases, you have to implement your own higher-level synchronization. But the above technique is nonetheless very useful in certain, highly constrained situations.

I am struggling to work out what @Rob means by "Your example is easily solved (by adding an method that dispatches block to the queue)". I would be interested to see an example implementation of this method (or any other) technique to solve the problem.

Answer 1

You said:

I am struggling to work out what @Rob means by “Your example is easily solved (by adding [a] method that dispatches block to the queue)”. I would be interested to see an example implementation of this method (or any other) technique to solve the problem.

Let’s expand upon the example that I posted in response to your other question (see point 3 in this answer), adding a few more Array methods:

class SynchronizedArray<T> {
    private var array: [T]
    private let accessQueue = DispatchQueue(label: "com.domain.app.reader-writer", attributes: .concurrent)

    init(_ array: [T] = []) {
        self.array = array
    }

    subscript(index: Int) -> T {
        get { reader { $0[index] } }
        set { writer { $0[index] = newValue } }
    }

    var count: Int {
        reader { $0.count }
    }

    func append(newElement: T) {
        writer { $0.append(newElement) }
    }

    func remove(at index: Int) {
        writer { $0.remove(at: index) }
    }

    func reader<U>(_ block: ([T]) throws -> U) rethrows -> U {
        try accessQueue.sync { try block(array) }
    }

    func writer(_ block: @escaping (inout [T]) -> Void) {
        accessQueue.async(flags: .barrier) { block(&self.array) }
    }
}

So, let’s imagine that you wanted to delete an item if there was only one item in the array. Consider:

let numbers = SynchronizedArray([42])

...

if numbers.count == 1 { 
    numbers.remove(at: 0) 
}

That looks innocent enough, but it is not thread-safe. You could have a race condition if other threads are inserting or removing values. E.g., if some other thread appended a value between the time you tested the count and when you went to remove the value.

You can fix that by wrapping the whole operation (the if test and the consequent removal) in a single block that is synchronized. Thus you could:

numbers.writer { array in
    if array.count == 1 { 
        array.remove(at: 0) 
    } 
}

This writer method (in this reader-writer-based synchronization) is an example of what I meant by a “method that dispatches block to the queue”.

---

Now, clearly, you could also give your SynchronizedArray its own method that did this for you, e.g.:

func safelyRemove(at index: Int) {
    writer { array in
        if index < array.count {
            array.remove(at: index)
        }
    }
}

Then you can do:

numbers.safelyRemove(at: index)

... and that is thread-safe, but still enjoys the performance benefits of reader-writer synchronization.

But the general idea is that when dealing with a thread-safe collection, you invariably have a series of tasks that you will want to synchronize together, at a higher level of abstraction. By exposing the synchronization methods of reader and writer, you have a simple, generalized mechanism for doing that.

---

All of that having been said, as others have said, the best way to write thread-safe code is to avoid concurrent access altogether. But if you must make a mutable object thread-safe, then it is the responsibility of the caller to identify the series of tasks that must be performed as a single, synchronized operation.