Swift性能：对数组进行排序
我在Swift中实现了一个算法，并注意到性能非常差。 在深入挖掘之后，我意识到其中一个瓶颈就像排序数组一样简单。 相关部分在这里：
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 =整数列表（x））。
在Swift中，如果使用以下命令编译它，则需要6秒 ：
xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`
如果我使用以下命令编译它，则需要多达88秒的时间 ：
xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`
Xcode中的“发布”与“调试”版本的时间类似。
这里有什么问题？ 与C ++相比，我可以理解一些性能损失，但与纯Python相比，不会减少10倍。
编辑： mweathers注意到将-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之间的性能差异-Ofast 。 所以我看了一下汇编代码：
随着-Ofast我几乎得到了我所期望的。 相关部分是一个包含5条机器语言指令的循环。
用-O3我得到的东西超出了我最疯狂的想象。 内循环跨越88行汇编代码。 我没有试图理解所有这些，但最可疑的部分是13个“callq _swift_retain”调用和另外13个“callq _swift_release”调用。 也就是说， 在内部循环中调用26个子程序 ！
编辑3：在评论中，Ferruccio要求的基准是公平的，因为他们不依赖内置函数（例如排序）。 我认为下面的程序是一个很好的例子：
let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
for j in 0..<n {
x[i] = x[j]
}
}
没有算术，所以我们不需要担心整数溢出。 我们所做的唯一的事情就是大量的数组引用。 结果在这里 - 与-Ofast相比，Swift -O3几乎损失了500倍：
（如果你担心编译器会完全优化无意义的循环，你可以把它改成例如x[i] ^= x[j] ，并添加一个输出x[0]的打印语句，这并不会改变任何东西;时间将非常相似。）
是的，这里的Python实现是一个愚蠢的纯Python实现，它带有ints列表和嵌套for循环。 它应该比未优化的雨燕慢得多 。 Swift和数组索引似乎严重破坏了某些东西。
编辑4：这些问题（以及一些其他性能问题）似乎已经在Xcode 6 beta 5中得到修复。
为了排序，我现在有以下时间：
对于嵌套循环：
看起来没有理由再使用不安全的-Ofast （又名-Ounchecked ）; 平原-O产生同样好的代码。
tl;通过使用默认版本优化级别[-O]的这个基准测试，Swift现在与C一样快。
这是Swift中的一个就地快速排序：
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)
}
和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);
}
两者都有效：
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]
两者都在写入的同一程序中调用。
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();
这将绝对时间转换为秒：
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;
}
以下是编译器优化级别的总结：
[-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.
n = 10_000时用[-Onone] 表示的秒数 ：
Swift: 0.895296452
C: 0.001223848
这里是Swift的内置排序（） n = 10_000 ：
Swift_builtin: 0.77865783
这里是n = 10_000的 [-O] ：
Swift: 0.045478346
C: 0.000784666
Swift_builtin: 0.032513488
正如你所看到的，斯威夫特的表现提高了20倍。
根据mweathers的回答，设置[-Ofast]会产生真正的差异，导致n = 10_000的这些时间：
Swift: 0.000706745
C: 0.000742374
Swift_builtin: 0.000603576
而对于n = 1_000_000 ：
Swift: 0.107111846
C: 0.114957179
Swift_sort: 0.092688548
为了比较，这与n = 1_000_000的 [-Onone] ：
Swift: 142.659763258
C: 0.162065333
Swift_sort: 114.095478272
因此，在这个基准测试阶段，没有优化的Swift比C慢1000倍，在这个阶段它的发展。 另一方面，如果两个编译器都设置为[-Ofast]，Swift的实际执行效果至少与C相比稍好一些。
有人指出[-Ofast]会改变语言的语义，使其可能不安全。 这就是Apple在Xcode 5.0发行说明中所说的：
LLVM中提供的新优化级别-Ofast可实现积极的优化。 -Ofast放宽了一些保守的限制，主要用于浮点操作，对大多数代码都是安全的。 它可以从编译器中获得显着的高性能优势。
他们都提倡它。 无论这是否明智，我都不能说，但从我可以告诉的是，如果您没有进行高精度浮点运算，并且您确信没有整数或数组溢出可能在你的程序中。 如果您确实需要高性能和溢出检查/精确算术，那么现在就选择另一种语言。
BETA 3更新：
n = 10_000与[-O] ：
Swift: 0.019697268
C: 0.000718064
Swift_sort: 0.002094721
总的来说Swift速度更快，看起来Swift的内置排序已经发生了很大的变化。
最终更新：
[-Onone] ：
Swift: 0.678056695
C: 0.000973914
[-O] ：
Swift: 0.001158492
C: 0.001192406
[-Ounchecked] ：
Swift: 0.000827764
C: 0.001078914
TL; DR ：是的，现在唯一的Swift语言实施速度很慢。 如果你需要快速，数字（和其他类型的代码，大概是）代码，那么就去另一个。 将来，你应该重新评估你的选择。 不过，对于大多数应用程序代码而言，它可能已经足够好了。
从我在SIL和LLVM IR中看到的情况看来，他们似乎需要一系列优化来移除保留和释放，这些优化可能会在Clang（Objective-C）中实现，但尚未移植它们。 这就是我正在使用的理论（现在......我仍然需要确认Clang是否做了些什么），因为在这个问题的最后一个测试案例上运行的分析器产生了这个“相当”的结果：
正如许多人所说的， -Ofast是完全不安全的，并改变了语言语义。 对我而言，它是在“如果你要使用它，只是使用另一种语言”阶段。 如果它发生变化，我会在稍后重新评估这一选择。
-O3给我们带来了一堆swift_retain和swift_release调用，说实话，看起来他们不应该在这个例子中。 优化器应该已经消除了AFAICT（大部分），因为它知道大部分关于数组的信息，并且知道它至少有一个很强的参考。
当它甚至不调用可能释放对象的函数时，它不应该释放更多的保留。 我不认为一个数组构造函数可以返回一个比要求的数组小的数组，这意味着很多发出的检查都是无用的。 它也知道整数永远不会超过10k，因此可以优化溢出检查（不是因为-Ofast怪异，而是因为语言的语义（没有其他任何内容正在改变该-Ofast也不能访问它，并且加起来到10k对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")
PS：我不是Objective-C的专家，也不是来自Cocoa，Objective-C或Swift运行时的所有设施。 我可能也会假设一些我没有写的东西。
我决定看看这个有趣的，这里是我得到的时间：
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()
结果：
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
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
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编译，似乎性能相同。
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
似乎从Swift 2.0到Swift 3.0的性能回归，而且我也第一次看到-O和-Ounchecked之间的区别。
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再次提高了性能，同时保持-O和-Ounchecked之间的差距。 -O -whole-module-optimization似乎没有什么区别。
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;
}
结果：
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
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
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
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的排序速度很快，但与使用-O编译时的C ++排序速度相比，还不及上面的编译器和库。 使用-Ounchecked ，它在Swift 4.0.2和Apple LLVM 9.0.0中似乎与C ++一样快。
上一篇: Swift performance: sorting arrays
下一篇: Why should I use a pointer rather than the object itself?