Top swift frequently asked interview questions
I was implementing an algorithm in Swift and noticed that the performance was very poor. After digging deeper I realised that one of the bottlenecks was something as simple as sorting arrays. The relevant part is here:
let n = 1000000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
x[i] = random()
}
// start clock here
let y = sort(x)
// stop clock here
In C++, a similar operation takes 0.06 s on my computer.
In Python it takes 0.6 s (no tricks, just y = sorted(x) for a list of integers).
In Swift it takes 6 s if I compile it with the following command:
xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`
And it takes as much as 88 s if I compile it with the following command:
xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`
Timings in Xcode with "Release" vs. "Debug" builds are similar.
What is wrong here? I could understand some performance loss in comparison with C++, but not a 10-fold slowdown in comparison with pure Python.
Edit: mweathers noticed that changing -O3 to -Ofast makes this code run almost as fast as the C++ version! However, -Ofast changes the semantics of the language a lot — in my testing, it disabled the checks for integer overflows and array indexing overflows. For example, with -Ofast the following Swift code runs silently without crashing (and prints out some garbage):
let n = 10000000
println(n*n*n*n*n)
let x = Int[](count: n, repeatedValue: 10)
println(x[n])
So -Ofast is not what we want; the whole point of Swift is that we have the safety nets in place. Of course the safety nets have some impact on the performance, but they should not make the programs 100 times slower. Remember that Java already checks for array bounds, and in typical cases the slowdown is by a factor much less than 2. And in Clang and GCC we have got -ftrapv for checking (signed) integer overflows, and it is not that slow, either.
Hence the question: how can we get a reasonable performance in Swift without losing the safety nets?
Edit 2: I did some more benchmarking, with very simple loops along the lines of
for i in 0..n {
x[i] = x[i] ^ 12345678
}
(Here the xor operation is there just so that I can more easily find the relevant loop in the assembly code. I tried to pick an operation that is easy to spot but also "harmless" in the sense that it should not require any checks related to integer overflows.)
Again, there was a huge difference in the performance between -O3 and -Ofast. So I had a look at the assembly code:
With -Ofast I get pretty much what I would expect. The relevant part is a loop with 5 machine language instructions.
With -O3 I get something that was beyond my wildest imagination. The inner loop spans 88 lines of assembly code. I did not try to understand all of it, but the most suspicious parts are 13 invocations of "callq _swift_retain" and another 13 invocations of "callq _swift_release". That is, 26 subroutine calls in the inner loop!
Edit 3: In comments, Ferruccio asked for benchmarks that are fair in the sense that they do not rely on built-in functions (e.g. sort). I think the following program is a fairly good example:
let n = 10000
let x = Int[](count: n, repeatedValue: 1)
for i in 0..n {
for j in 0..n {
x[i] = x[j]
}
}
There is no arithmetic, so we do not need to worry about integer overflows. The only thing that we do is just lots of array references. And the results are here—Swift -O3 loses by factor almost 500 in comparison with -Ofast:
- C++ -O3: 0.05 s
- C++ -O0: 0.4 s
- Java: 0.2 s
- Python with PyPy: 0.5 s
- Python: 12 s
- Swift -Ofast: 0.05 s
- Swift -O3: 23 s
- Swift -O0: 443 s
(If you are concerned that the compiler might optimise out the pointless loops entirely, you can change it to e.g. x[i] ^= x[j], and add a print statement that outputs x[0]. This does not change anything; the timings will be very similar.)
And yes, here the Python implementation was a stupid pure Python implementation with a list of ints and nested for loops. It should be much slower than unoptimised Swift. Something seems to be seriously broken with Swift and array indexing.
Edit 4: These issues (as well as some other performance issues) seems to have been fixed in Xcode 6 beta 5.
For sorting, I now have the following timings:
- clang++ -O3: 0.06 s
- swiftc -Ofast: 0.1 s
- swiftc -O: 0.1 s
- swiftc: 4 s
For nested loops:
- clang++ -O3: 0.06 s
- swiftc -Ofast: 0.3 s
- swiftc -O: 0.4 s
- swiftc: 540 s
It seems that there is no reason anymore to use the unsafe -Ofast (a.k.a. -Ounchecked); plain -O produces equally good code.
Source: (StackOverflow)