Swift Beta性能：排序数组 - HelloWorld开发者社区

问题：

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产生同样好的代码。