我在 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.06s 。
在 Python 中,它需要 0.6s (没有技巧,只是 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 中的时间是相似的。
这里有什么问题?与 C++ 相比,我可以理解一些性能损失,但与纯 Python 相比,速度不会降低 10 倍。
编辑: 天气注意到将
-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
}
(这里的异或操作只是为了我可以更容易地在汇编代码中找到相关的循环。我试图选择一个易于发现但“无害”的操作,因为它不需要任何相关检查到整数溢出。)
同样,
-O3
和 -Ofast
之间的性能存在巨大差异。所以我看了一下汇编代码:-Ofast
我得到了我所期望的。相关部分是一个带有 5 条机器语言指令的循环。 -O3
我得到了超出我想象的东西。内部循环跨越 88 行汇编代码。我没有试图理解所有内容,但最可疑的部分是“callq _swift_retain”的 13 次调用和另外 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 实现,带有一个整数列表和嵌套的 for 循环。它应该比未优化的 Swift 慢 。 Swift 和数组索引似乎严重破坏了某些东西。
编辑 4: 这些问题(以及其他一些性能问题)似乎已在 Xcode 6 beta 5 中得到修复。
对于排序,我现在有以下时间:
对于嵌套循环:
似乎没有理由再使用不安全的
-Ofast
(又名 -Ounchecked
);普通的 -O
产生同样好的代码。
最佳答案
tl;dr Swift 1.0 现在通过使用默认发布优化级别 [-O] 的基准测试与 C 一样快。
这是 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)
}
在 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.
时间以秒为单位 [-Onone] 为 n=10_000 :
Swift: 0.895296452
C: 0.001223848
这是 的 Swift 内置 sort() n=10_000 :
Swift_builtin: 0.77865783
这是 [-O] 为 n=10_000 :
Swift: 0.045478346
C: 0.000784666
Swift_builtin: 0.032513488
如您所见,Swift 的性能提高了 20 倍。
根据 mweathers' answer , 设置 [-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
为了比较,这是与 [-Onone] 为 n=1_000_000 :
Swift: 142.659763258
C: 0.162065333
Swift_sort: 114.095478272
所以在这个基准测试中,没有优化的 Swift 几乎比 C 慢 1000 倍,在它的开发阶段。另一方面,当两个编译器都设置为 [-Ofast] 时,Swift 的实际性能至少与 C 一样好。
有人指出 [-Ofast] 改变了语言的语义,使其具有潜在的不安全性。这是 Apple 在 Xcode 5.0 发行说明中声明的内容:
A new optimization level -Ofast, available in LLVM, enables aggressive optimizations. -Ofast relaxes some conservative restrictions, mostly for floating-point operations, that are safe for most code. It can yield significant high-performance wins from the compiler.
他们几乎都提倡它。我不能说这是否明智,但据我所知,如果您没有进行高精度浮点运算并且您确信没有整数或您的程序中可能会出现数组溢出。如果您确实需要高性能和溢出检查/精确算术,那么现在选择另一种语言。
测试版 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
[-未检查] :
Swift: 0.000827764
C: 0.001078914
关于Swift Beta 性能 : sorting arrays,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24101718/