Swift性能:排序数组
我正在Swift实现一个算法,注意到性能非常差。在深入挖掘之后,我意识到瓶颈之一就像排序数组一样简单。相关部分在这里:
let n = 1000000 let x = Int[](count: n,repeatedValue: 0) 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中,如果我使用以下命令编译它需要6秒: xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx` 如果我用下面的命令编译它需要88秒的时间: xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx` “Xcode”中的“发布”与“调试”构建的时间是类似的。 这里有什么问题?我可以理解一些性能损失与C相比,但不是一个10倍的放缓与纯Python相比。 编辑:mweathers注意到,将-O3更改为-Ofast使此代码运行几乎与C版本一样快!但是,-Ofast很多地改变了语言的语义 – 在我的测试中,它禁用了对整数溢出和数组索引溢出的检查。例如,使用-Ofast,以下Swift代码静默运行而不会崩溃(并打印出一些垃圾): let n = 10000000 println(n*n*n*n*n) let x = Int[](count: n,repeatedValue: 10) println(x[n]) 所以 – 快速不是我们想要的; Swift的整个观点是我们有安全网。当然,安全网对性能有一些影响,但它们不应该使程序慢100倍。记住,Java已经检查了数组边界,在典型的情况下,减速的大小要小于2.在Clang和GCC中,我们有-ftrapv用于检查(有符号)整数溢出,而不是那么慢。 因此,问题:我们如何在不失去安全网的情况下在Swift中获得合理的性能? 编辑2:我做了更多的基准,有非常简单的循环 for i in 0..n { x[i] = x[i] ^ 12345678 } (这里的xor操作只是为了我可以更容易找到相关的循环在汇编代码。我试图选择一个容易发现的操作,但也“无害”的意义上,它不应该要求任何检查相关到整数溢出。) 同样,-O3和-Ofast之间的性能有很大的不同。所以我看了汇编代码: >用-Ofast我几乎得到了我的期望。相关部分是一个带有5个机器语言指令的循环。 编辑3:在评论中,Ferruccio要求公平的基准,他们不依赖于内置函数(例如排序)。我认为以下程序是一个相当好的例子: let n = 10000 let x = Int[](count: n,repeatedValue: 1) for i in 0..n { for j in 0..n { x[i] = x[j] } } 没有算术,所以我们不需要担心整数溢出。我们做的只是很多数组引用。结果是这里 – Swift -O3损失的因子差不多500与相比-Ofast: > C-O3:0.05s (如果你担心编译器可能会完全优化无意义的循环,你可以把它改成例如x [i] ^ = x [j],并添加一个输出x [0]的print语句。 ;时间将非常类似。) 是的,这里的Python实现是一个愚蠢的纯Python实现与一列int和嵌套for循环。它应该比未优化的Swift慢得多。一些似乎严重破坏与Swift和数组索引。 编辑4:这些问题(以及一些其他性能问题)似乎已经修复在Xcode 6 beta 5。 对于排序,我现在有以下定时: > ang -O3:0.06s 对于嵌套循环: > ang -O3:0.06s 似乎没有理由再使用不安全的-Ofast(a.k.a. -Ounchecked); plain -O产生同样好的代码。
tl; dr Swift现在使用默认发布优化级别[-O],这个基准使用的速度与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,2] quicksort_swift(&a_swift,a_swift.count) quicksort_c(&a_c,CInt(a_c.count)) // [-1,1234] // [-1,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,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的内置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 为了比较,对于n = 1_000_000使用[-Onone] Swift: 142.659763258 C: 0.162065333 Swift_sort: 114.095478272 因此,在这个基准测试中,Swift在没有优化的情况下比C的性能差了近1000倍。另一方面,两个编译器都设置为[-Ofast] Swift实际上至少执行,如果不是稍好于C. 已经指出,[-Ofast]改变语言的语义,使其可能不安全。这是苹果在Xcode 5.0发行说明中说的:
他们都提倡。无论是聪明还是不,我不能说,但从我可以告诉它似乎足够合理的使用[-Ofast]在一个版本,如果你不做高精度浮点运算,你没有信心没有整数或阵列溢出可能在您的程序。如果你需要高性能和溢出检查/精确算术,现在选择另一种语言。 BETA 3更新: n = 10_000,其中[-O]: Swift: 0.019697268 C: 0.000718064 Swift_sort: 0.002094721 Swift通常有点快,看起来Swift的内置排序已经发生了很大的变化。 最终更新: [-在一个]: Swift: 0.678056695 C: 0.000973914 [-O]: Swift: 0.001158492 C: 0.001192406 [-Ounchecked]: Swift: 0.000827764 C: 0.001078914 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |