# Swift Beta performance: sorting arrays

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
``````