Stuart Breckenridge

Performance Analysis of appendIfUnique

Last week we looked at extending Array to include an appendIfUnique function. In this post—inspired by feedback from Twitter—we assess the performance of that function against the built in contains(element: Self.Generator.Element) and Swift’s Set type.

The difference between O(n2) and O(n) can be seen in this graph:

via justin.abrah.ms

To see how close we are to O(n2) I’ve created three test cases:

  • one will insert n elements to a Set and then create an Array from that set;
  • one will append n unique elements to an Array using appendIfUnique; and,
  • one will append n unique elements to an Array using the contains(element:Self.Generator.Element) function
struct Benchmarks { 
    static func testNumbersSetToArray(size:Int) {
        var set = Set<Int>()
        
        while set.count < size {
            set.insert(set.count + 1)
        }
        
        let _ = Array(set)
    }
    
    static func testAppendIfUnique(size:Int) {
        var numbers = [Int]()
        
        while numbers.count < size {
            numbers.appendIfUnique(numbers.count + 1)
        }
    }
    
    static func testArrayContains(size:Int) {
        var numbers = [Int]()
        
        while numbers.count < size {
            if !numbers.contains(numbers.count + 1)
            {
                numbers.append(numbers.count + 1)
            }
        }
    }
}

Function performance is measured from XCTestCase by calling:

    func testAppend() {
        self.measureBlock {
            Benchmarks.testAppendIfUnique(60000)
        }
    }
    
    func testArrayContains(){
        self.measureBlock {
            Benchmarks.testArrayContains(60000)
        }
    }
    
    func testSet(){
        self.measureBlock {
            Benchmarks.testNumbersSetToArray(60000)
        }
    }

I ran tests with n going up to 60,000 and the compiler optimisation level set to Fast[-0] Whole Module Optimization. The results are below:

Elements appendIfUnique contains Set
10000 0.015s 0.029s 0.002s
20000 0.064s 0.112s 0.003s
30000 0.141s 0.251s 0.004s
40000 0.243s 0.450s 0.004s
50000 0.421s 0.695s 0.006s
60000 0.607s 1.019s 0.007s
Performance Results

Conclusion: Using Set is an outright winner, while appendIfUnique and contains are in line with O(n2). contains is, however, considerably slower than appendIfUnique which is surprising.

The source code for these tests is available on GitHub.

Recommended Reading:


Supported by