Unit Testing Thread Safe List in Swift

Question

I have an AtomicList type:

public struct AtomicList<Element> {
    public var values: [Element] = []
    private let queue = DispatchQueue(label: UUID().uuidString)
    
    public var last: Element? {
        self.queue.sync { return self.values.last }
    }
    
    public mutating func append(item: Element) {
        self.queue.sync {
            self.values.append(item)
        }
    }
}

And a flaky failing test that should validate that it's thread safe:

class AtomicListTests: XCTestCase {
    func testReadingAndWritingOnDifferentThreads() {
        var arrayA = AtomicList<Int>()
        var arrayB = AtomicList<Int>()
        
        let expectation = expectation(description: "thread safety test")
        expectation.expectedFulfillmentCount = 10000
        
        for i in 0..<expectation.expectedFulfillmentCount {
            DispatchQueue.global().async {
                arrayA.append(item: i)
                if let last = arrayA.last {
                    arrayB.append(item: last)
                }
                expectation.fulfill()
            }
        }
        
        wait(for: [expectation], timeout: 5.0)
        XCTAssertEqual(arrayA.values.count, arrayB.values.count)
    }
}

I have 2 questions:

1. Is this even a valid test to check whether this type is thread safe?
2. Why is the test occasionally failing with the error that 9999 is not equal to 10000 (i.e. the counts don't match)

Note: I noticed a couple solutions that fix this and make it pass the test such as:

1. Changing AtomicList from a struct to a class
2. Changing var last to a mutating func
3. Synchronizing access to arrayA and arrayB in the test

But I still don't fully understand why the existing code doesn't work, and why the first 2 solutions above make it pass.

Answer 1

Is this even a valid test to check whether this type is thread safe?

No. Just because a race condition fails to cause a symptom does not mean there is no race condition. To test for basic memory race conditions that occur during your test, you need to use the thread sanitizer. This instruments your code to ensure that every cross-thread memory access is guarded by a lock. This still doesn't prove there are no low-level race conditions, since it may not execute all code-paths (though it will detect unguarded accesses, even if they happen not to collide, which is its point).

All of that still doesn't mean there are no higher-level race conditions. See bbum's answer on why Objective-C's atomic doesn't provide high-level thread-safety, even though it eliminates all low-level data races. Proving that a system is thread-safe in that way is likely impossible.

To your question of why this code doesn't work, this isn't a valid way to access value types. Value types are copied when passed to functions or mutated. They are values. They are not an object that can have multiple references pointing the same one. Accessing the same struct from multiple threads is not defined behavior and is breaking copy-on-write optimizations. You have a lock around the internal array, but you don't have a lock around the AtomicList struct. (It would be nice if the compiler failed on this, but it would break too many common GCD patterns that do a single struct modification.)

This means that the accesses to the internal arrays are synchronized, but the modification of the struct is not. Your problem is much bigger than occasional mismatched lengths. The values are wrong too. If I run this 100 times and check arrayB, the first few elements are often wrong. Sometimes [1,1,2], sometimes [1,0,2], etc.

The right tool for this is actor. But for GCD this can only make sense with a class, which is a reference type, and so locks can work.

Answer 2

First of all consider using Swift Atomics, so you won't need a custom class. Or consider using an actor for your data structure, as suggested in the comment.

A couple of implementation notes:

1. Your access to values is not thread-safe. I would recommend to make them private, and either create a thread-safe iterator, or provide a copy of the array. Otherwise you may get an exception (I forget the exact wording, but it says something like "array was mutated while being accessed")

2. Each operation in your atomic class is atomic, but their sequential calls are not. For example in your test you do this:

arrayA.append(item: i)
if let last = arrayA.last

While each operation is atomic here, you are not guaranteed that arrayA.last will be the same element you appended just in the line above (because other thread may have appended something else after it)

So if you do need to access array and then modify it (or vice versa), consider adding an atomic operation that does such sequence, or some generic approach for sequential calls, for example described here

3. I also agree that it makes more sense to make Atomic to be a class or actor, not struct. But BTW the problem above is not solved even if you switch your data structure to be an actor.

4. Number of DispatchQueues in the system is limited. So depending on how you are planning to use this atomic list (or how many of them you are planning to have), you may need a static queue.

Thirdly: XCTestExpectation (surprise-surprise) is not thread safe and hence cannot be used as a reliable method of checking thread safety of your atomic class. There are well documented cases where it caused various issues (this for example), and I can confirm from my experience as well that it may indeed cause something like "9999 is not equal to 10000".

So what I usually suggest to do for testing such a component is

1. Break it to several tests: a test for each operation, and test for each combination of operations that makes sense. In your case it means 3 tests: for last, for append and for the both operations working together. I am disregarding the access to array itself here, but if you make it thread-safe, you will need then a test for array, as well as possibly additional tests for "read and modify array concurrently" (but that depends on how you implement your array access)

2. Use DispatchQueue.concurrentPerform as a way to do operations concurrently. Why? because it guarantees to complete after all iterations are done, and hence you don't need XCTestExpectation. BTW: the Swift Atomics I mentioned above also uses this method in its tests, and to demo the thread safety.

3. Also you don't need that many iterations, all you really want is to load all threads available during the test. Usually the test only has about 10 threads. Fine, you can run 100 iterations just to be sure, but 10000 is quite excessive, and doesn't add any value to your test.

So a simple set of tests would look like this:

func testLast() {

    // Given
    var a = AtomicList<Int>()
    var i =  Int.random(in: 1...100)
    a.append(i)

    // When: several threads reading the value of `last` concurrently
    DispatchQueue.concurrentPerform(iterations: 100) { _ in

        // Then: the read value is correct (and no crash happened)
        XCTAssertEqual(a.last, i)
    }
}

func testAppend() {

    // Given
    var a = AtomicList<Int>()
    let iterations = 100

    // When: several threads appending concurrently
    // We cannot control the order of values, so we will test after all iterations are done.
    DispatchQueue.concurrentPerform(iterations: iterations) { i in
        a.append(i)
    }

    // Then
    XCTAssertEqual(a.count, iterations)
    // I would also sort an array and check its elements, but that's optional
}

func testAppendAndLast() {

    // Given
    var a = AtomicList<Int>()
    let iterations = 100
    
    // When
    DispatchQueue.concurrentPerform(iterations: iterations) { i in
        // We cannot be sure what last will be when we are reading it,
        // But we can be sure that if we read current last, then append, then read again, they should be different.
        let lastBefore = a.last
        a.append(i)
        let lastAfter = a.last
        XCTAssertNotEqual(lastBefore, lastAfter)
    }
}