Swift Beta performance: sorting arrays

Question

I was implementing an algorithm in Swift Beta and noticed that the performance was very poor. After digging deeper I realized that one of the bottlenecks was something as simple as sorting arrays. The relevant part is here:

let n = 1000000 var x =  [Int](repeating: 0, count: n) 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.06s on my computer.

In Python, it takes 0.6s (no tricks, just y = sorted(x) for a list of integers).

In Swift it takes 6s if I compile it with the following command:

xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx` 

And it takes as much as 88s 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: weather 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 print(n*n*n*n*n) let x =  [Int](repeating: 10, count: n) print(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 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 var x = [Int](repeating: 1, count: n) 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 a 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 optimize 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 unoptimized 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.

Answer 1

tl;dr Swift 1.0 is now as fast as C by this benchmark using the default release optimisation level [-O].

---

Here is an in-place quicksort in Swift Beta:

func quicksort_swift(inout a:CInt[], start:Int, end:Int) {     if (end - start < 2){         return     }     var p = a[start + (end - start)/2]     var l = start     var r = end - 1     while (l <= r){         if (a[l] < p){             l += 1             continue         }         if (a[r] > p){             r -= 1             continue         }         var t = a[l]         a[l] = a[r]         a[r] = t         l += 1         r -= 1     }     quicksort_swift(&a, start, r + 1)     quicksort_swift(&a, r + 1, end) } 

And the same in C:

void quicksort_c(int *a, int n) {     if (n < 2)         return;     int p = a[n / 2];     int *l = a;     int *r = a + n - 1;     while (l <= r) {         if (*l < p) {             l++;             continue;         }         if (*r > p) {             r--;             continue;         }         int t = *l;         *l++ = *r;         *r-- = t;     }     quicksort_c(a, r - a + 1);     quicksort_c(l, a + n - l); } 

Both work:

var a_swift:CInt[] = [0,5,2,8,1234,-1,2] var a_c:CInt[] = [0,5,2,8,1234,-1,2]  quicksort_swift(&a_swift, 0, a_swift.count) quicksort_c(&a_c, CInt(a_c.count))  // [-1, 0, 2, 2, 5, 8, 1234] // [-1, 0, 2, 2, 5, 8, 1234] 

Both are called in the same program as written.

var x_swift = CInt[](count: n, repeatedValue: 0) var x_c = CInt[](count: n, repeatedValue: 0) for var i = 0; i < n; ++i {     x_swift[i] = CInt(random())     x_c[i] = CInt(random()) }  let swift_start:UInt64 = mach_absolute_time(); quicksort_swift(&x_swift, 0, x_swift.count) let swift_stop:UInt64 = mach_absolute_time();  let c_start:UInt64 = mach_absolute_time(); quicksort_c(&x_c, CInt(x_c.count)) let c_stop:UInt64 = mach_absolute_time(); 

This converts the absolute times to seconds:

static const uint64_t NANOS_PER_USEC = 1000ULL; static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC; static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC;  mach_timebase_info_data_t timebase_info;  uint64_t abs_to_nanos(uint64_t abs) {     if ( timebase_info.denom == 0 ) {         (void)mach_timebase_info(&timebase_info);     }     return abs * timebase_info.numer  / timebase_info.denom; }  double abs_to_seconds(uint64_t abs) {     return abs_to_nanos(abs) / (double)NANOS_PER_SEC; } 

Here is a summary of the compiler's optimazation levels:

[-Onone] no optimizations, the default for debug. [-O]     perform optimizations, the default for release. [-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks. 

Time in seconds with [-Onone] for n=10_000:

Swift:            0.895296452 C:                0.001223848 

Here is Swift's builtin sort() for n=10_000:

Swift_builtin:    0.77865783 

Here is [-O] for n=10_000:

Swift:            0.045478346 C:                0.000784666 Swift_builtin:    0.032513488 

As you can see, Swift's performance improved by a factor of 20.

As per mweathers' answer, setting [-Ofast] makes the real difference, resulting in these times for n=10_000:

Swift:            0.000706745 C:                0.000742374 Swift_builtin:    0.000603576 

And for n=1_000_000:

Swift:            0.107111846 C:                0.114957179 Swift_sort:       0.092688548 

For comparison, this is with [-Onone] for n=1_000_000:

Swift:            142.659763258 C:                0.162065333 Swift_sort:       114.095478272 

So Swift with no optimizations was almost 1000x slower than C in this benchmark, at this stage in its development. On the other hand with both compilers set to [-Ofast] Swift actually performed at least as well if not slightly better than C.

It has been pointed out that [-Ofast] changes the semantics of the language, making it potentially unsafe. This is what Apple states in the Xcode 5.0 release notes:

A new optimization level -Ofast, available in LLVM, enables aggressive optimizations. -Ofast relaxes some conservative restrictions, mostly for floating-point operations, that are safe for most code. It can yield significant high-performance wins from the compiler.

They all but advocate it. Whether that's wise or not I couldn't say, but from what I can tell it seems reasonable enough to use [-Ofast] in a release if you're not doing high-precision floating point arithmetic and you're confident no integer or array overflows are possible in your program. If you do need high performance and overflow checks / precise arithmetic then choose another language for now.

BETA 3 UPDATE:

n=10_000 with [-O]:

Swift:            0.019697268 C:                0.000718064 Swift_sort:       0.002094721 

Swift in general is a bit faster and it looks like Swift's built-in sort has changed quite significantly.

FINAL UPDATE:

[-Onone]:

Swift:   0.678056695 C:       0.000973914 

[-O]:

Swift:   0.001158492 C:       0.001192406 

[-Ounchecked]:

Swift:   0.000827764 C:       0.001078914 

Answer 2

TL;DR: Yes, the only Swift language implementation is slow, right now. If you need fast, numeric (and other types of code, presumably) code, just go with another one. In the future, you should re-evaluate your choice. It might be good enough for most application code that is written at a higher level, though.

From what I'm seeing in SIL and LLVM IR, it seems like they need a bunch of optimizations for removing retains and releases, which might be implemented in Clang (for Objective-C), but they haven't ported them yet. That's the theory I'm going with (for now… I still need to confirm that Clang does something about it), since a profiler run on the last test-case of this question yields this “pretty” result:

As was said by many others, -Ofast is totally unsafe and changes language semantics. For me, it's at the “If you're going to use that, just use another language” stage. I'll re-evaluate that choice later, if it changes.

-O3 gets us a bunch of swift_retain and swift_release calls that, honestly, don't look like they should be there for this example. The optimizer should have elided (most of) them AFAICT, since it knows most of the information about the array, and knows that it has (at least) a strong reference to it.

It shouldn't emit more retains when it's not even calling functions which might release the objects. I don't think an array constructor can return an array which is smaller than what was asked for, which means that a lot of checks that were emitted are useless. It also knows that the integer will never be above 10k, so the overflow checks can be optimized (not because of -Ofast weirdness, but because of the semantics of the language (nothing else is changing that var nor can access it, and adding up to 10k is safe for the type Int).

The compiler might not be able to unbox the array or the array elements, though, since they're getting passed to sort(), which is an external function and has to get the arguments it's expecting. This will make us have to use the Int values indirectly, which would make it go a bit slower. This could change if the sort() generic function (not in the multi-method way) was available to the compiler and got inlined.

This is a very new (publicly) language, and it is going through what I assume are lots of changes, since there are people (heavily) involved with the Swift language asking for feedback and they all say the language isn't finished and will change.

Code used:

import Cocoa  let swift_start = NSDate.timeIntervalSinceReferenceDate(); let n: Int = 10000 let x = Int[](count: n, repeatedValue: 1) for i in 0..n {     for j in 0..n {         let tmp: Int = x[j]         x[i] = tmp     } } let y: Int[] = sort(x) let swift_stop = NSDate.timeIntervalSinceReferenceDate();  println("\(swift_stop - swift_start)s") 

P.S: I'm not an expert on Objective-C nor all the facilities from Cocoa, Objective-C, or the Swift runtimes. I might also be assuming some things that I didn't write.