我在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生成同样好的代码。
为了好玩，我决定看看这个，以下是我得到的时间:
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++一样快。
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编写。
