PerformanceTesting

PerformanceTesting provides tools for checking the asymptotic complexity of algorithms and operations over data structures.

For example, this is particularly useful for ensuring that an algorithm that you have written which should be perform in constant time (i.e., O(1)) isn't accidentally quadratic (i.e., O(n²)).

There are three types of operations which can be tested via static methods on the Benchmark structure.

If the operation that you are testing does not mutate its subject (e.g., Array.count), use Benchmark.nonMutating:

let benchmark = Benchmark.nonMutating(setup: { Array(0..<$0 }) { _ = $0.count }

If the operation that you are testing mutates its subject (e.g., Set.insert), use Benchmark.mutating:

let benchmark = Benchmark.mutating(setup: { Set(0..<$0) }) { _ = $0.insert(1) }

For algorithms that don't act upon data structures (e.g., fibonacci, etc.), Benchmark.algorithm wipes away the setup phase, and forwards the size directly to the measuring closure for you.

let benchmark = Benchmark.algorithm { _ = fibonacci($0) }

We are pretty sure that the performance guarantees documented by the Stdlib are accurate, so we used these as tests for our testing mechanism.

For example, in order to verify that the count property of an Array is performed in constant time, one can do the following within an XCTestCase subclass.

func testArrayCountIsConstant() {
    // Create a `Benchmark` for the given operation.
    let benchmark = Benchmark.nonMutating(
        // For each size, creates an `Array` with elements increasing from zero up to the size
        setup: { size in Array(0 ..< size) },
        // Measures `array.count` 10 times by default, averaging out the results
        measuring: { array in _ = array.count }
    )
    XCTAssert(benchmark.performance(is: .constant))
}

With the use of trailing closure syntax and shorthand closure parameter names, the above can be shortened to:

let benchmark = Benchmark.nonMutating(setup: { Array(0..<$0) }) { _ = $0.count }
XCTAssert(benchmark.performance(is: .constant))

More configuration is possible by specifying trialCount (i.e., how many times an operation is performed per test size), and testPoints (i.e., the sizes at which the operation is performed), like so:

let benchmark = Benchmark.nonMutating(
    trialCount: 1_000,
    testPoints: [1, 10, 100, 1_000, 1_000_000, 1_000_000_000],
    setup: { size in Array(0 ..< size) },
    measuring: { array in _ = array.count }
)

The Scale namespace offers default testPoints (.tiny, .small, .medium, .large) that are good for most tests.

See ./Tests for more example usage.

Include this package by adding the following line to your Package.swift's dependencies section:

.package(url: "https://github.com/dn-m/PerformanceTesting", .branch("master"))

Add import PerformanceTesting to the top of your test files, and you are good to go.

Clone and build this project with:

git clone https://github.com/dn-m/PerformanceTesting && cd PerformanceTesting
swift build

To run the tests that come with the library:

swift test