我在Swift Beta中实现了一个算法，并注意到性能非常差。在深入研究之后，我意识到瓶颈之一就像排序数组一样简单。有关部分如下:
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
在c++中，类似的操作在我的电脑上需要0.06秒。
在Python中，它需要0.6秒(没有技巧，只是y = sorted(x)对于一个整数列表)。
在Swift中，如果我用以下命令编译它，它需要6s:
xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`
如果我用下面的命令编译它，它需要88s:
xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`
Xcode中“Release”和“Release”的计时。“调试”构建也类似。
这里出了什么问题?与c++相比，我可以理解一些性能损失，但与纯Python相比，我不能理解10倍的性能下降。
编辑:weather注意到，将-O3更改为-Ofast使得这段代码几乎和c++版本一样快!然而，- ofast极大地改变了语言的语义——在我的测试中，它禁用了对整数溢出和数组索引溢出的检查。例如，使用-Ofast，下面的Swift代码会无声地运行而不会崩溃(并打印出一些垃圾):
let n = 10000000
print(n*n*n*n*n)
let x = [Int](repeating: 10, count: n)
print(x[n])
所以-Ofast不是我们想要的;Swift的全部意义在于我们有适当的安全网。当然，安全网对性能有一定的影响，但它们不应该使程序变慢100倍。请记住，Java已经检查了数组边界，在典型情况下，放缓的因素远小于2。在Clang和GCC中，我们有-ftrapv用于检查(有符号的)整数溢出，它也不是那么慢。
因此，问题来了:我们如何才能在不失去安全网的情况下在Swift中获得合理的性能?
编辑2:我做了更多的基准测试，使用非常简单的循环
for i in 0..<n {
x[i] = x[i] ^ 12345678
}
(这里有xor操作，这样我可以更容易地在程序集代码中找到相关的循环。我试图选择一个容易发现但“无害”的操作，因为它不需要任何与整数溢出相关的检查。)
同样，-O3和-Ofast在性能上存在巨大差异。所以我看了一下汇编代码:
很快我就得到了我想要的。相关部分是一个包含5条机器语言指令的循环。
对于-O3，我得到的结果超出了我的想象。内部循环包含88行汇编代码。我没有试图理解它的全部，但最可疑的部分是“callq _swift_retain”的13次调用和“callq _swift_release”的另外13次调用。也就是说，在内部循环中有26个子例程调用!
编辑3:在评论中，Ferruccio要求基准测试是公平的，因为它们不依赖于内置函数(例如sort)。我认为下面的程序是一个相当好的例子:
let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
for j in 0..<n {
x[i] = x[j]
}
}
没有算术，所以我们不需要担心整数溢出。我们唯一要做的就是大量的数组引用。结果如下:swift -O3与-Ofast相比损失了近500倍:
c++ -O3: 0.05 s
c++ -O0: 0.4 s
Java: 0.2秒
Python与PyPy: 0.5秒
Python: 12秒
Swift -Ofast: 0.05 s
Swift -O3: 23秒
Swift -O0: 443 s
(如果你担心编译器可能会完全优化掉毫无意义的循环，你可以把它改为例如x[i] ^= x[j]，并添加输出x[0]的print语句。这不会改变任何事情;时间将非常相似。)
是的，这里的Python实现是一个愚蠢的纯Python实现，有一个int类型的列表和嵌套的for循环。它应该比未优化的Swift慢得多。Swift和数组索引似乎严重破坏了一些东西。
编辑4:这些问题(以及其他一些性能问题)似乎在Xcode 6 beta 5中已经修复。
对于排序，我现在有以下时间:
clang++ -O3: 0.06 s
swiftc -Ofast: 0.1秒
swiftc -O: 0.1秒
Swiftc: 4秒
对于嵌套循环:
clang++ -O3: 0.06 s
swiftc -Ofast: 0.3秒
swiftc -O: 0.4 s
540秒
似乎没有理由再使用不安全的-Ofast(又名- unchecked);纯-O生成同样好的代码。
TL;DR:是的，目前唯一的Swift语言实现速度很慢。如果您需要快速的数字代码(或者其他类型的代码)，那就使用另一种代码。在未来，你应该重新评估你的选择。不过，对于在更高级别上编写的大多数应用程序代码来说，这可能已经足够好了。
从我在SIL和LLVM IR中看到的情况来看，他们似乎需要一堆优化来删除保留和释放，这可能会在Clang中实现(针对Objective-C)，但他们还没有移植它们。这就是我的理论(现在……我仍然需要确认Clang对此做了一些事情)，因为在这个问题的最后一个测试用例上运行的分析器产生了这个“漂亮”的结果:
正如许多人所说，-Ofast是完全不安全的，并且改变了语言语义。对我来说，这是在“如果你要使用这种语言，那就使用另一种语言”的阶段。我以后会重新评估这个选择，如果它改变了。
-O3为我们提供了一堆swift_retain和swift_release调用，老实说，它们看起来不应该出现在这个例子中。优化器应该已经省略了(大部分)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).
不过，编译器可能无法解方框数组或数组元素，因为它们被传递给sort()，这是一个外部函数，必须获得它所期望的参数。这将使我们不得不间接使用Int值，这将使它运行得有点慢。如果sort()泛型函数(不是以多方法的方式)对编译器可用并内联，则这可能会改变。
这是一种非常新的(公开的)语言，我认为它正在经历很多变化，因为有很多人(大量)参与Swift语言的工作，他们都说语言还没有完成，而且会改变。
代码使用:
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")
附注:我不是Objective-C的专家，也不是Cocoa、Objective-C或Swift运行时的所有工具的专家。我可能还假设了一些我没有写的东西。
func partition(inout list : [Int], low: Int, high : Int) -> Int {
let pivot = list[high]
var j = low
var i = j - 1
while j < high {
if list[j] <= pivot{
i += 1
(list[i], list[j]) = (list[j], list[i])
}
j += 1
}
(list[i+1], list[high]) = (list[high], list[i+1])
return i+1
}
func quikcSort(inout list : [Int] , low : Int , high : Int) {
if low < high {
let pIndex = partition(&list, low: low, high: high)
quikcSort(&list, low: low, high: pIndex-1)
quikcSort(&list, low: pIndex + 1, high: high)
}
}
var list = [7,3,15,10,0,8,2,4]
quikcSort(&list, low: 0, high: list.count-1)
var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quikcSort(&list2, low: 0, high: list2.count-1)
var list3 = [1,3,9,8,2,7,5]
quikcSort(&list3, low: 0, high: list3.count-1)
这是我的博客关于快速排序- Github样本快速排序
您可以在partitioning the list中查看Lomuto的分区算法。用Swift编写。
摘自Swift编程语言:
Swift的标准库提供了一个名为
类对已知类型的值数组进行排序
所提供的排序闭包的输出。一旦它完成
排序过程中，sort函数返回一个相同的新数组
类型和大小与旧的一样，其元素在正确的排序
秩序。
排序函数有两个声明。
允许你指定比较闭包的默认声明:
func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]
第二个声明只接受一个参数(数组)，并且“硬编码以使用小于比较器”。
func sort<T : Comparable>(array: T[]) -> T[]
Example:
sort( _arrayToSort_ ) { $0 > $1 }
我在一个操场上测试了您代码的修改版本，添加了闭包，以便我可以更密切地监视函数，我发现当n设置为1000时，这个闭包被调用了大约11000次。
let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
x[i] = random()
}
let y = sort(x) { $0 > $1 }
这不是一个有效的函数，我建议使用更好的排序函数实现。
编辑:
我看了一下维基百科的Quicksort页面，并为它写了一个Swift实现。以下是我在操场上使用的完整程序
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
}
当n=1000时，我发现
quickSort()被调用了大约650次，
大约进行了6000次互换，
大约有10,000个比较
似乎内置的排序方法是(或接近)快速排序，并真的很慢…
为了好玩，我决定看看这个，以下是我得到的时间:
Swift 4.0.2 : 0.83s (0.74s with `-Ounchecked`)
C++ (Apple LLVM 8.0.0): 0.74s
斯威夫特
// 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()
结果:
斯威夫特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
斯威夫特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
斯威夫特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
如果我使用-Ounchecked编译，它似乎是相同的性能。
斯威夫特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
从Swift 2.0到Swift 3.0的性能似乎出现了倒退，而且我还第一次看到-O和-Ounchecked之间的差异。
斯威夫特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再次提高了性能，同时保持了-O和-Ounchecked之间的间隔。-O -整个模块优化似乎没有什么不同。
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;
}
结果:
苹果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
苹果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
苹果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
苹果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
苹果叮当 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
判决
在写这篇文章的时候，Swift的排序速度很快，但还没有c++的排序速度快，当用-O编译时，用上面的编译器和库。使用- unchecked，它看起来和Swift 4.0.2和Apple LLVM 9.0.0中的c++一样快。
