我在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.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中具有“发布”与“调试”构建的时序是相似的。
怎么了 与C ++相比,我可以理解一些性能损失,但与纯Python相比,却不能降低10倍。
编辑: 天气注意到更改-O3为-Ofast使此代码运行几乎与C ++版本一样快!但是,-Ofast它极大地改变了语言的语义- 在我的测试中,它 禁用了对整数溢出和数组索引溢出的检查 。例如,-Ofast下面的Swift代码以静默方式运行而不会崩溃(并打印出一些垃圾):
-O3
-Ofast
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检查了(有符号的)整数溢出,但也没有那么慢。
-ftrapv
因此产生了一个问题:如何在Swift中获得合理的性能而又不损失安全网?
编辑2: 我进行了一些基准测试,其中的循环非常简单
for i in 0..<n { x[i] = x[i] ^ 12345678 }
(这里只有xor操作,以便我可以更容易地在汇编代码中找到相关的循环。我试图选择一个易于发现但又“无害”的操作,因为它不需要任何相关的检查。到整数溢出。)
同样,-O3和之间的性能存在巨大差异-Ofast。所以我看了一下汇编代码:
有了-Ofast我,我得到了我所期望的。相关部分是一个包含5条机器语言指令的循环。
随着-O3我得到的东西,出乎我的想象。内部循环跨越88行汇编代码。我没有试图理解所有内容,但是最可疑的部分是“ callq _swift_retain”的13个调用和“ callq _swift_release”的另外13个调用。也就是说, 内部循环中有26个子例程调用 !
编辑3: 在评论中,费鲁奇奥要求提供不违反内置函数(例如排序)的公平基准。我认为以下程序是一个很好的示例:
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倍:
(如果担心编译器可能会完全优化无意义的循环,则可以将其更改为eg x[i] ^= x[j],并添加一个输出输出的print语句x[0]。这不会改变任何内容;时序将非常相似。)
x[i] ^= x[j]
x[0]
是的,这里的Python实现是一个愚蠢的纯Python实现,带有一个整数列表和嵌套的for循环。这应该是 很多 比未优化雨燕慢。Swift和数组索引似乎严重破坏了某些东西。
编辑4: 这些问题(以及其他一些性能问题)似乎已在Xcode 6 beta 5中得到修复。
为了进行排序,我现在有以下时间安排:
对于嵌套循环:
似乎已经没有理由再使用不安全-Ofast(aka -Ounchecked)了;Plain -O会产生同样好的代码。
-Ounchecked
-O
tl; dr使用默认的发行优化级别[-O],在此基准下,Swift 1.0现在与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的回答,设置 [-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],即使实际上不比C稍好,Swift的实际效果也至少一样好。
已经指出,[-Ofast]更改了语言的语义,使其潜在地不安全。这是Apple在Xcode 5.0发行说明中指出的内容:
LLVM中提供了新的优化级别- Ofast,可以进行积极的优化。-Ofast放宽了一些保守的限制,大多数情况下对于浮点运算是安全的,这对大多数代码来说都是安全的。它可以从编译器中获得明显的高性能优势。
他们全都主张。无论是不是明智,我都不能说,但是据我所知,如果您不进行高精度浮点运算并且您确信没有整数或整数,那么在发行版中使用[-Ofast]似乎足够合理。程序中可能发生数组溢出。如果您确实需要高性能 和 溢出检查/精确算术,请立即选择其他语言。
测试版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