swift资源 - Swift性能:对数组进行排序
swift shell sort (6)
Swift Array性能重新审视:
我写了自己的基准,比较Swift和C / Objective-C。 我的基准计算素数。 它使用以前的素数数组来寻找每个新候选人的素数因子,所以它非常快。 但是,它会进行数组读取,而不会写入数组。
我原先是对Swift 1.2做这个基准的。 我决定更新该项目并针对Swift 2.0运行它。
该项目让您选择使用普通的swift数组和使用数组语义的Swift不安全内存缓冲区。
对于C / Objective-C,您可以选择使用NSArrays或C malloc'ed数组。
测试结果与最快,最小的代码优化([-0s])或最快,最积极(最快(最快)]优化似乎非常相似。
在关闭代码优化的情况下,Swift 2.0的性能仍然很糟糕,而C / Objective-C的性能只是稍微慢一些。
底线是C malloc'd基于数组的计算速度最快,幅度不大
使用最快,最小的代码优化时,带有不安全缓冲区的Swift比C malloc'd数组长1.19X - 1.20X。 与快速,积极的优化相比,差异似乎稍微小一些(Swift比C更长1.18倍到1.16倍。
如果你使用普通的Swift数组,与C的差别稍大 。 (Swift花费大约1.22到1.23。)
普通的Swift数组比DRAMATICALLY
速度上要快于在Swift 1.2 / Xcode 6中的速度。它们的性能非常接近Swift不安全的基于缓冲区的数组,使用不安全的内存缓冲区看起来并不值得麻烦,这很大。
顺便说一句,Objective-C的NSArray性能很糟糕。 如果你打算在两种语言中使用本地容器对象,Swift的运行速度会更快。
您可以在SwiftPerformanceBenchmark上的github上查看我的项目
它有一个简单的用户界面,使收集统计很容易。
有趣的是,Swift中的排序似乎比C中的稍快,但这个素数算法在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倍:
- C ++ -O3: 0.05秒
- C ++ -O0:0.4 s
- Java: 0.2秒
- Python与PyPy:0.5秒
- Python: 12秒
- 迅速 - 快速:0.05秒
- Swift -O3: 23 s
- Swift -O0:443 s
(如果你担心编译器会完全优化无意义的循环,你可以把它改成例如x[i] ^= x[j]
,并添加一个输出x[0]
的打印语句,这并不会改变任何东西;时间将非常相似。)
是的,这里的Python实现是一个愚蠢的纯Python实现,带有ints列表和嵌套for循环。 它应该比未优化的Swift慢得多。 Swift和数组索引似乎严重破坏了某些东西。
编辑4:这些问题(以及一些其他性能问题)似乎在Xcode 6 beta 5中得到了修复。
为了排序,我现在有以下时间:
- 铛++ -O3:0.06秒
- swiftc - 快:0.1秒
- swiftc -O:0.1秒
- swiftc:4秒
对于嵌套循环:
- 铛++ -O3:0.06秒
- swiftc - 快速:0.3秒
- swiftc -O:0.4秒
- swiftc:540秒
看起来没有理由再使用不安全的-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
从Xcode 7开始,您可以打开Fast, Whole Module Optimization
。 这应该立即提高你的表现。
其他人提到的主要问题是, -O3
在Swift中根本就没有做任何事情(所以从来没有),所以编译时它实际上是非优化的( -Onone
)。
选项名称随时间而改变,所以其他一些答案对于构建选项具有过时的标志。 正确的当前选项(Swift 2.2)是:
-Onone // Debug - slow
-O // Optimised
-O -whole-module-optimization //Optimised across files
整个模块优化的编译速度较慢,但可以跨模块内的文件进行优化,即在每个框架内和实际应用程序代码内但不在它们之间。 你应该使用它来表现任何关键性能)
您还可以停用安全检查,以获得更快的速度,但所有断言和前提条件不仅仅是禁用,而是基于它们是正确的进行了优化。 如果你打了一个断言,这意味着你陷入了未定义的行为。 只有在确定速度提升对您有价值时(通过测试),才能非常谨慎地使用。 如果您确实发现它对于某些代码很有价值,我建议将该代码分离到单独的框架中,并且仅对该模块禁用安全检查。
来自The Swift Programming Language
:
Sort函数Swift的标准库提供了一个称为sort的函数,它根据您提供的排序闭包的输出对已知类型的值的数组进行排序。 一旦完成排序过程,排序函数将返回一个与旧排序相同类型和大小的新数组,其元素按正确的排序顺序排列。
sort
函数有两个声明。
默认声明允许您指定比较闭包:
func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]
而第二个声明只需要一个参数(数组),并且“硬编码为使用小于比较器”。
func sort<T : Comparable>(array: T[]) -> T[]
Example:
sort( _arrayToSort_ ) { $0 > $1 }
我在一个操场上测试了代码的修改版本,添加了闭包,所以我可以更密切地监视函数,并且我发现在n设置为1000时,闭包被称为约11,000次。
let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
x[i] = random()
}
let y = sort(x) { $0 > $1 }
这不是一个有效的函数,我会建议使用更好的排序功能实现。
编辑:
我看了一下Quicksort维基百科页面,并为它写了一个Swift实现。 这里是我使用的完整程序(在游乐场)
import Foundation
func quickSort(inout array: Int[], begin: Int, end: Int) {
if (begin < end) {
let p = partition(&array, begin, end)
quickSort(&array, begin, p - 1)
quickSort(&array, p + 1, end)
}
}
func partition(inout array: Int[], left: Int, right: Int) -> Int {
let numElements = right - left + 1
let pivotIndex = left + numElements / 2
let pivotValue = array[pivotIndex]
swap(&array[pivotIndex], &array[right])
var storeIndex = left
for i in left..right {
let a = 1 // <- Used to see how many comparisons are made
if array[i] <= pivotValue {
swap(&array[i], &array[storeIndex])
storeIndex++
}
}
swap(&array[storeIndex], &array[right]) // Move pivot to its final place
return storeIndex
}
let n = 1000
var x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
x[i] = Int(arc4random())
}
quickSort(&x, 0, x.count - 1) // <- Does the sorting
for i in 0..n {
x[i] // <- Used by the playground to display the results
}
使用n = 1000,我发现
- quickSort()被调用约650次,
- 进行了大约6000次掉期交易,
- 并有大约10000个比较
看起来内置的排序方法是(或接近)快速排序,而且非常慢...
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示例快速排序
您可以在分区列表中查看Lomuto的分区算法。 写在Swift中