欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

Swift Beta性能：排序数组

程序员文章站 2022-06-04 17:15:13
...

本文翻译自：Swift Beta performance: sorting arrays

I was implementing an algorithm in Swift Beta and noticed that the performance was very poor. 我在Swift Beta中实现了一个算法，并注意到性能非常差。 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. 在C ++中，类似的操作在我的计算机上需要0.06秒 。

In Python, it takes 0.6s (no tricks, just y = sorted(x) for a list of integers). 在Python中，它需要0.6秒 （没有技巧，只有y =排序（x）表示整数列表）。

In Swift it takes 6s if I compile it with the following command: 在Swift中，如果我使用以下命令编译它需要6秒 ： 

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: 如果我使用以下命令编译它需要多达88秒 ： 

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

Timings in Xcode with "Release" vs. "Debug" builds are similar. Xcode中的“释放”与“调试”版本的计时相似。

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. 与C ++相比，我可以理解一些性能损失，但与纯Python相比，速度没有降低10倍。

Edit: weather noticed that changing -O3 to -Ofast makes this code run almost as fast as the C++ version! 编辑：天气注意到将-O3更改为-Ofast使得此代码的运行速度几乎与C ++版本一样快！ However, -Ofast changes the semantics of the language a lot — in my testing, it disabled the checks for integer overflows and array indexing overflows . 但是， -Ofast改变了语言的语义 - 在我的测试中，它禁止检查整数溢出和数组索引溢出 。 For example, with -Ofast the following Swift code runs silently without crashing (and prints out some garbage): 例如，使用-Ofast ，以下Swift代码以静默方式运行而不会崩溃（并打印出一些垃圾）： 

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; 所以-Ofast不是我们想要的; 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. 当然，安全网对性能有一些影响，但它们不应该使程序慢100倍。 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. 请记住，Java已经检查了数组边界，并且在典型情况下，减速是一个远小于2的因素。在Clang和GCC中，我们有-ftrapv用于检查（签名）整数溢出，并且它不是那么慢，无论是。

Hence the question: how can we get reasonable performance in Swift without losing the safety nets? 因此，问题是：如何在不丢失安全网的情况下在Swift中获得合理的性能？

Edit 2: I did some more benchmarking, with very simple loops along the lines of 编辑2：我做了一些基准测试，非常简单的循环 

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.) （这里的xor操作只是为了让我可以更容易地在汇编代码中找到相关的循环。我试图选择一个易于发现但也“无害”的操作，因为它不需要任何相关的检查到整数溢出。）

Again, there was a huge difference in the performance between -O3 and -Ofast . 同样， -O3和-Ofast之间的性能差异-Ofast 。 So I had a look at the assembly code: 所以我看了一下汇编代码：

  • With -Ofast I get pretty much what I would expect. 随着-Ofast我得到了我所期望的。 The relevant part is a loop with 5 machine language instructions. 相关部分是一个包含5个机器语言指令的循环。

  • With -O3 I get something that was beyond my wildest imagination. 有了-O3我得到的东西超出了我的想象力。 The inner loop spans 88 lines of assembly code. 内环跨越88行汇编代码。 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". 我没有尝试理解所有这些，但最可疑的部分是13次调用“callq _swift_retain”和另外13次调用“callq _swift_release”。 That is, 26 subroutine calls in the inner loop ! 也就是说， 内循环中有26个子程序调用 ！

Edit 3: In comments, Ferruccio asked for benchmarks that are fair in the sense that they do not rely on built-in functions (eg sort). 编辑3：在评论中，Ferruccio要求提供公平的基准，因为他们不依赖于内置函数（例如排序）。 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: 结果在这里 - 与-Ofast相比，Swift -O3损失了近500倍：

  • C++ -O3: 0.05 s C ++ -O3： 0.05秒
  • C++ -O0: 0.4 s C ++ -O0：0.4秒
  • Java: 0.2 s Java： 0.2秒
  • Python with PyPy: 0.5 s 使用PyPy的Python：0.5秒
  • Python: 12 s Python： 12秒
  • Swift -Ofast: 0.05 s Swift -Ofast：0.05秒
  • Swift -O3: 23 s Swift -O3： 23秒
  • Swift -O0: 443 s Swift -O0：443秒

(If you are concerned that the compiler might optimize out the pointless loops entirely, you can change it to eg x[i] ^= x[j] , and add a print statement that outputs x[0] . This does not change anything; the timings will be very similar.) （如果您担心编译器可能会完全优化无意义循环，您可以将其更改为例如x[i] ^= x[j] ，并添加一个输出x[0]的print语句。这不会改变任何内容;时间将非常相似。）

And yes, here the Python implementation was a stupid pure Python implementation with a list of ints and nested for loops. 是的，这里的Python实现是一个愚蠢的纯Python实现，带有一个int列表和嵌套for循环。 It should be much slower than unoptimized Swift. 它应该比未优化雨燕慢得多 。 Something seems to be seriously broken with Swift and array indexing. 使用Swift和数组索引似乎严重破坏了某些东西。

Edit 4: These issues (as well as some other performance issues) seems to have been fixed in Xcode 6 beta 5. 编辑4：这些问题（以及一些其他性能问题）似乎已在Xcode 6 beta 5中得到修复。

For sorting, I now have the following timings: 为了排序，我现在有以下时间：

  • clang++ -O3: 0.06 s clang ++ -O3：0.06 s
  • swiftc -Ofast: 0.1 s swiftc -Ofast：0.1秒
  • swiftc -O: 0.1 s swiftc -O：0.1秒
  • swiftc: 4 s swiftc：4秒

For nested loops: 对于嵌套循环：

  • clang++ -O3: 0.06 s clang ++ -O3：0.06 s
  • swiftc -Ofast: 0.3 s swiftc -Ofast：0.3秒
  • swiftc -O: 0.4 s swiftc -O：0.4 s
  • swiftc: 540 s swiftc：540秒

It seems that there is no reason anymore to use the unsafe -Ofast (aka -Ounchecked ); 似乎没有理由再使用unsafe -Ofast （aka -Ounchecked ）; plain -O produces equally good code. plain -O产生同样好的代码。

#1楼

参考：https://stackoom.com/question/1d7xO/Swift-Beta性能-排序数组

#2楼

From The Swift Programming Language : 来自The Swift Programming Language ：

The Sort Function Swift's standard library provides a function called sort, which sorts an array of values of a known type, based on the output of a sorting closure that you provide. Sort函数Swift的标准库提供了一个名为sort的函数，它根据您提供的排序闭包的输出对已知类型的值数组进行排序。 Once it completes the sorting process, the sort function returns a new array of the same type and size as the old one, with its elements in the correct sorted order. 完成排序过程后，sort函数返回一个与旧数组相同类型和大小的新数组，其元素按正确的排序顺序排列。

The sort function has two declarations. sort函数有两个声明。

The default declaration which allows you to specify a comparison closure: 允许您指定比较闭包的默认声明： 

func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]

And a second declaration that only take a single parameter (the array) and is "hardcoded to use the less-than comparator." 第二个声明只接受一个参数（数组），并且“硬编码使用less-than比较器”。 

func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }

I tested a modified version of your code in a playground with the closure added on so I could monitor the function a little more closely, and I found that with n set to 1000, the closure was being called about 11,000 times. 我在操场上测试了你的代码的修改版本，并添加了闭包，这样我可以更接近地监视函数，并且我发现当n设置为1000时，闭包被调用大约11,000次。 

let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
let y = sort(x) { $0 > $1 }

It is not an efficient function, an I would recommend using a better sorting function implementation. 它不是一个有效的功能，我建议使用更好的排序功能实现。

EDIT: 编辑：

I took a look at the Quicksort wikipedia page and wrote a Swift implementation for it. 我看了一下Quicksort*页面并为它编写了一个Swift实现。 Here is the full program I used (in a playground) 这是我用过的完整程序（在操场上） 

import Foundation

func quickSort(inout array: Int[], begin: Int, end: Int) {
    if (begin < end) {
        let p = partition(&array, begin, end)
        quickSort(&array, begin, p - 1)
        quickSort(&array, p + 1, end)
    }
}

func partition(inout array: Int[], left: Int, right: Int) -> Int {
    let numElements = right - left + 1
    let pivotIndex = left + numElements / 2
    let pivotValue = array[pivotIndex]
    swap(&array[pivotIndex], &array[right])
    var storeIndex = left
    for i in left..right {
        let a = 1 // <- Used to see how many comparisons are made
        if array[i] <= pivotValue {
            swap(&array[i], &array[storeIndex])
            storeIndex++
        }
    }
    swap(&array[storeIndex], &array[right]) // Move pivot to its final place
    return storeIndex
}

let n = 1000
var x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = Int(arc4random())
}

quickSort(&x, 0, x.count - 1) // <- Does the sorting

for i in 0..n {
    x[i] // <- Used by the playground to display the results
}

Using this with n=1000, I found that 使用n = 1000，我发现了

  1. quickSort() got called about 650 times, quickSort（）被召唤约650次，
  2. about 6000 swaps were made, 大约6000掉期交易，
  3. and there are about 10,000 comparisons 并且有大约10,000个比较

It seems that the built-in sort method is (or is close to) quick sort, and is really slow... 似乎内置的排序方法是（或接近）快速排序，而且非常慢......

#3楼

tl;dr Swift 1.0 is now as fast as C by this benchmark using the default release optimisation level [-O]. tl; Dr Swift 1.0现在使用默认版本优化级别[-O]通过此基准测试与C一样快。

Here is an in-place quicksort in Swift Beta: 这是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: 在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 : 对于n = 10_000 ， [-Onone]的时间以秒为单位 ： 

Swift:            0.895296452
C:                0.001223848

Here is Swift's builtin sort() for n=10_000 : 这是Swift的内置排序（），用于n = 10_000 ： 

Swift_builtin:    0.77865783

Here is [-O] for n=10_000 : 对于n = 10_000，这是[-O] ： 

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

As you can see, Swift's performance improved by a factor of 20. 如您所见，Swift的性能提高了20倍。

As per mweathers' answer , setting [-Ofast] makes the real difference, resulting in these times for n=10_000 : 根据mweathers的回答 ，设置[-Ofast]会产生真正的差异，导致n = 10_000的这些时间： 

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

And for n=1_000_000 : 对于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 : 为了比较，对于n = 1_000_000 ，这是[-Onone] ： 

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. 因此，在这个基准测试中，没有优化的Swift在开发的这个阶段比C慢了近1000倍。 On the other hand with both compilers set to [-Ofast] Swift actually performed at least as well if not slightly better than C. 另一方面，两个编译器都设置为[-Ofast] Swift实际上至少表现得好，如果不是比C略好一点。

It has been pointed out that [-Ofast] changes the semantics of the language, making it potentially unsafe. 已经指出[-Ofast]改变了语言的语义，使其可能不安全。 This is what Apple states in the Xcode 5.0 release notes: 这就是Apple在Xcode 5.0发行说明中所说的：

A new optimization level -Ofast, available in LLVM, enables aggressive optimizations. LLVM中提供的新优化级别-Ofast可实现积极的优化。 -Ofast relaxes some conservative restrictions, mostly for floating-point operations, that are safe for most code. -Ofast放松了一些保守的限制，主要用于浮点运算，对大多数代码都是安全的。 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. 这是否明智我不能说，但从我可以说的是，如果你没有进行高精度浮点运算并且你确信没有整数或者一个版本，那么在一个版本中使用[-Ofast]似乎是合理的。您的程序中可能存在数组溢出。 If you do need high performance and overflow checks / precise arithmetic then choose another language for now. 如果您确实需要高性能和溢出检查/精确算术，那么现在就选择另一种语言。

BETA 3 UPDATE: BETA 3更新：

n=10_000 with [-O] : n = 10_000，带[ - 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. 一般来说Swift有点快，看起来Swift的内置排序已经发生了很大变化。

FINAL UPDATE: 最终更新：

[-Onone] : [-Onone] ： 

Swift:   0.678056695
C:       0.000973914

[-O] : [-O] ： 

Swift:   0.001158492
C:       0.001192406

[-Ounchecked] : [-Ounchecked] ： 

Swift:   0.000827764
C:       0.001078914

#4楼

TL;DR : Yes, the only Swift language implementation is slow, right now . TL; DR：是的，只有雨燕语言的实现是缓慢的， 就是现在 。 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. 从我在SIL和LLVM IR中看到的情况来看，似乎他们需要一堆优化来删除保留和释放，这可能在Clang （针对Objective-C）中实现，但他们还没有移植它们。 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: 这就是我要去的理论（现在......我仍然需要确认Clang对此做了些什么），因为在这个问题的最后一个测试用例上运行的探查器产生了这个“漂亮”的结果：

Swift Beta性能：排序数组Swift Beta性能：排序数组

As was said by many others, -Ofast is totally unsafe and changes language semantics. 正如许多其他人所说的那样， -Ofast完全不安全并且改变了语言语义。 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. -O3给我们带来了一堆swift_retain和swift_release调用，老实说，看起来他们不应该在这个例子中。 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. 优化器应该将它们（大部分）省略为AFAICT，因为它知道有关该数组的大部分信息，并且知道它（至少）有一个强引用。

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 ). 它也知道整数永远不会超过10k，因此可以优化溢出检查（不是因为-Ofast怪异，而是因为语言的语义（没有其他任何改变var也无法访问它，并且加起来）对于类型Int ），10k是安全的。

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. 但是，编译器可能无法取消装入数组或数组元素，因为它们已经传递给sort() ，这是一个外部函数，必须得到它所期望的参数。 This will make us have to use the Int values indirectly, which would make it go a bit slower. 这将使我们必须间接使用Int值，这会使它变得有点慢。 This could change if the sort() generic function (not in the multi-method way) was available to the compiler and got inlined. 如果编译器可以使用sort()泛型函数（不是以多方法方式）并且内联，则可能会发生这种情况。

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. 这是一种非常新的（公开）语言，它正在经历我认为的很多变化，因为有些人（大量）参与Swift语言请求反馈，他们都说语言没有完成，并且会更改。

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")

PS: I'm not an expert on Objective-C nor all the facilities from Cocoa , Objective-C, or the Swift runtimes. PS：我不是Objective-C的专家，也不是Cocoa ，Objective-C或Swift运行时的所有工具。 I might also be assuming some things that I didn't write. 我也可能会假设一些我没写过的东西。

#5楼

I decided to take a look at this for fun, and here are the timings that I get: 我决定看看这个很有趣，以下是我得到的时间： 

Swift 4.0.2           :   0.83s (0.74s with `-Ounchecked`)
C++ (Apple LLVM 8.0.0):   0.74s

Swift 迅速 

// Swift 4.0 code
import Foundation

func doTest() -> Void {
    let arraySize = 10000000
    var randomNumbers = [UInt32]()

    for _ in 0..<arraySize {
        randomNumbers.append(arc4random_uniform(UInt32(arraySize)))
    }

    let start = Date()
    randomNumbers.sort()
    let end = Date()

    print(randomNumbers[0])
    print("Elapsed time: \(end.timeIntervalSince(start))")
}

doTest()

Results: 结果：

Swift 1.1 Swift 1.1 

xcrun swiftc --version
Swift version 1.1 (swift-600.0.54.20)
Target: x86_64-apple-darwin14.0.0

xcrun swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 1.02204304933548

Swift 1.2 Swift 1.2 

xcrun swiftc --version
Apple Swift version 1.2 (swiftlang-602.0.49.6 clang-602.0.49)
Target: x86_64-apple-darwin14.3.0

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.738763988018036

Swift 2.0 Swift 2.0 

xcrun swiftc --version
Apple Swift version 2.0 (swiftlang-700.0.59 clang-700.0.72)
Target: x86_64-apple-darwin15.0.0

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.767306983470917

It seems to be the same performance if I compile with -Ounchecked . 如果我使用-Ounchecked编译它似乎是相同的性能。

Swift 3.0 Swift 3.0 

xcrun swiftc --version
Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-800.0.38)
Target: x86_64-apple-macosx10.9

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.939633965492249

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Elapsed time: 0.866258025169373

There seems to have been a performance regression from Swift 2.0 to Swift 3.0, and I'm also seeing a difference between -O and -Ounchecked for the first time. 似乎从Swift 2.0到Swift 3.0的性能回归，我也看到了-O和-Ounchecked之间的第一次差异。

Swift 4.0 Swift 4.0 

xcrun swiftc --version
Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38)
Target: x86_64-apple-macosx10.9

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.834299981594086

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Elapsed time: 0.742045998573303

Swift 4 improves the performance again, while maintaining a gap between -O and -Ounchecked . Swift 4再次提高了性能，同时保持-O和-Ounchecked之间的差距。 -O -whole-module-optimization did not appear to make a difference. -O -whole-module-optimization似乎没有什么区别。

C++ C ++ 

#include <chrono>
#include <iostream>
#include <vector>
#include <cstdint>
#include <stdlib.h>

using namespace std;
using namespace std::chrono;

int main(int argc, const char * argv[]) {
    const auto arraySize = 10000000;
    vector<uint32_t> randomNumbers;

    for (int i = 0; i < arraySize; ++i) {
        randomNumbers.emplace_back(arc4random_uniform(arraySize));
    }

    const auto start = high_resolution_clock::now();
    sort(begin(randomNumbers), end(randomNumbers));
    const auto end = high_resolution_clock::now();

    cout << randomNumbers[0] << "\n";
    cout << "Elapsed time: " << duration_cast<duration<double>>(end - start).count() << "\n";

    return 0;
}

Results: 结果：

Apple Clang 6.0 Apple Clang 6.0 

clang++ --version
Apple LLVM version 6.0 (clang-600.0.54) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.0.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.688969

Apple Clang 6.1.0 Apple Clang 6.1.0 

clang++ --version
Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.670652

Apple Clang 7.0.0 Apple Clang 7.0.0 

clang++ --version
Apple LLVM version 7.0.0 (clang-700.0.72)
Target: x86_64-apple-darwin15.0.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.690152

Apple Clang 8.0.0 Apple Clang 8.0.0 

clang++ --version
Apple LLVM version 8.0.0 (clang-800.0.38)
Target: x86_64-apple-darwin15.6.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.68253

Apple Clang 9.0.0 Apple Clang 9.0.0 

clang++ --version
Apple LLVM version 9.0.0 (clang-900.0.38)
Target: x86_64-apple-darwin16.7.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.736784

Verdict 判决书

As of the time of this writing, Swift's sort is fast, but not yet as fast as C++'s sort when compiled with -O , with the above compilers & libraries. 截至撰写本文时，Swift的排序速度很快，但与使用上述编译器和库编译时使用-O编译时的C ++排序速度相-O 。 With -Ounchecked , it appears to be as fast as C++ in Swift 4.0.2 and Apple LLVM 9.0.0. 使用-Ounchecked ，它似乎与Swift 4.0.2和Apple LLVM 9.0.0中的C ++一样快。

#6楼

As of Xcode 7 you can turn on Fast, Whole Module Optimization . 从Xcode 7开始，您可以启用Fast, Whole Module Optimization 。 This should increase your performance immediately. 这应该会立即提高您的表现。

Swift Beta性能：排序数组

相关标签： swift performance sorting xcode6 compiler-optimization

上一篇： 归并算法

下一篇： 算法与数据结构（3）—— 归并排序

推荐阅读