Swift Beta performance: sorting arrays

itemprop="text">

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..            {
 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..
            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..            {
 for j in 0..
 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.

itemprop="text">

class="normal">Answer

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 href="https://stackoverflow.com/questions/24101718/swift-performance-sorting-arrays/24102759#24102759">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