Swift, Calculate the execution time of a sort algorithm

Question

I need calculate the execution time for 2 different algorithms then determine recommend one based on execution time. So I am fairly new to algorithms and data structures in general yet alone in Swift.

So I have done some searching and haven't found much. I did manage to find this:

func printTimeElapsedWhenRunningCode(title:String, operation:()->()) {
 let startTime = CFAbsoluteTimeGetCurrent()
 operation()
 let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
 print("Time elapsed for \(title): \(timeElapsed) s.")
}

This is then what I am actually trying to test:

printTimeElapsedWhenRunningCode(title: "Merge Sort") {
 let newSort = mergeSort(sortArray)
}

Now I am not sure if this is actually calculating what I am needing. Then every time I run this I always get a different time. Am I even on the right path?

• rmaddy: How/where are you running this code? Do not use a playground. Test the code with a fully optimized release build.
• Micheal: I been doing everything in playground. I will update my post with a bit more of information.
• rmaddy: Never attempt any performance testing in a playground.
• Micheal: This is for an assignment. Not real world. We were told to find sort algorithms and the test the execution. Basically the assignment is going over different sorting algorithms. I just need some way to show the execution time, of the algorithm.
• Micheal: I went ahead and just started a swift console application. I don't need to use playgrounds and that is good information.

Answer 1

Note: in the real life it is better to find some established performance testing framework. Doing test the right way is hard.

Here is an incomplete list of things you'd better do if you do your own testing:

1. Average over many iterations rather than just one. There are many reasons for results to be a bit noisy. If the total run time is less than 0.1 seconds, most probably it is totally unreliable. Better if it is at least 1 second. Also it makes sense to track not only the average but some other metrics like 95% percentile.

2. Do not ignore the results of the tested computation inside the loop. A smart compiler can optimize away not-used results and replace it with something like no-op. Ideally the result should be not predictable to the compiler. As an example: on i-th iteration add the i-th (or (i % array.length)-th) element of the sorted list to total sum and at the end return the sum or print it (obviously outside of the measured time)

3. Don't do any printing/logging/IO inside the tested algorithm unless you are trying to measure the performance of that IO operation. IO is very slow.

4. Do a few warm up iterations before the main "test" iterations. This is to make sure that all the data that can be in various CPU caches is there. Without warm up first runs and latter runs might differ very significantly. Also if you are running a managed code (like JavaScript or Java or .Net), many runs might force the VM to re-compile the code with some better optimizations. In such case you might need to run a few thousand of "warm up" iterations first to force it. Some better testing frameworks run batches until the time between different batches becomes stable.

5. Compare the code with the same level of optimization as will be used in production. Today's compilers can be very smart at optimizing if you allow them and "debug" builds can easily be 10 times slower than "release" builds.

For sorting algorithms there are some specific things to remember and the main is: do several measurements on different test arrays

1. Try different array sizes from a few to millions of elements. Today's memory access is a very complicated thing. Different algorithm have different memory usage patterns that might greatly affect performance at different sizes

2. Check different data. Some sorting algorithm have pathologically bad cases and some have none. Some might work especially fast on semi-sorted data and some can't exploit it. At least use some random data. It is better to use not only random though.

Answer 2

If you want to benchmark performance, using unit tests’ measure { ... } block is a good starting point, as it runs it a few times and calculates elapsed time, standard deviation, etc.

I’d also suggest:

• testing it with a type where sort is relatively efficient (e.g. [Int] rather than [String]) so that you focus on sort speed rather than comparison speed);
• do a sort that has observable time (e.g. a large array) and repeating the sort many times; and
• do something simple with the final result so that if you test an optimized build, you don’t risk having it optimize out some code that generates a result that you don’t use.

But for quick performance testing, Xcode unit tests are pretty easy. For example:

class MyAppTests: XCTestCase {
 let iterationCount = 1_000
 // build large array
 var array = (0 ..< 1_000).map { _ in Int.random(in: 0 ..< 1_000_000) }
 // test performance
 func testSortPerformance() {
 measure {
 for _ in 0 ..< iterationCount {
 let results = array.sorted()
 XCTAssert(!results.isEmpty)
 }
 }
 }
 func testBubbleSortPerformance() {
 measure {
 for _ in 0 ..< iterationCount {
 let results = array.bubbleSorted()
 XCTAssert(!results.isEmpty)
 }
 }
 }
}

That will yield the following results in the Report Navigator:

enter image description here

Or down in the console, you’ll see the details:

/.../MyAppTests.swift:33: Test Case '-[MyAppTests.MyAppTests testBubbleSortPerformance]' measured [Time, seconds] average: 0.603, relative standard deviation: 3.284%, values: [0.613748, 0.580443, 0.590879, 0.586842, 0.626791, 0.610288, 0.595295, 0.588713, 0.594823, 0.647156], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
/.../MyAppTests.swift:23: Test Case '-[MyAppTests.MyAppTests testSortPerformance]' measured [Time, seconds] average: 0.025, relative standard deviation: 13.393%, values: [0.033849, 0.026869, 0.022752, 0.023048, 0.023024, 0.022847, 0.023286, 0.023987, 0.023803, 0.022640], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100

And, while I’m at it, I’d probably test the sort algorithms themselves, too, e.g. making sure that the results were increasing values and that the total of all the items still added up:

func testBubbleSort() {
 let results = array.bubbleSorted()
 var previous = results[0]
 for index in 1 ..< results.count {
 let current = results[index]
 XCTAssertLessThanOrEqual(previous, current)
 previous = current
 }
 XCTAssertEqual(results.sum(), array.sum())
}

• Micheal: I feel like this honestly has been the best help so far, but I feel ultimately for what I am needing to be way complicated. I could be wrong. This is something that I haven't gotten into yet but planning on to. I have an array with 9 Ints. I just need them to be put in order using any 2 sort methods I choose. Then I need to know calculate the execution time of each sort. Then based on the time times compare them and whichever has the best time is recommended. I just need to know if the code I submitted up above is doing what I need on a simple level or in the right direction.
• Rob: Your approach is on the right direction, but testing one iteration with an array of 9 ints will not likely yield statistically significant results, which is why I suggest using much larger arrays and many more iterations. I’d also let the app reach quiescence before benchmarking. And if you’re testing two sort algorithms manually, like you are, make sure to discard the first iteration and try changing the order of the two sort algorithms. But one iteration with an array with 9 items is not enough dat to reach any conclusions.
• Micheal: So this is for a class assignment. We are given an array of 9 Ints. Then pick to sorting algorithms, find the code for each algorithm. Run the algorithm and calculate the execution time. I mean since asking this question I have already learned so much and want to continue furthering my knowledge with performance testing.