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.