Swift性能:排序数组

前端之家收集整理的这篇文章主要介绍了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个机器语言指令的循环。
>用-O3我得到的东西,超出了我最疯狂的想象力。内循环跨越88行汇编代码。我没有试图理解所有的,但最可疑的部分是13调用“callq _swift_retain”和另外13个调用“callq _swift_release”。也就是说,在内循环中有26个子程序调用

编辑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
> C-O0:0.4s
> Java:0.2 s
> Python with PyPy:0.5 s
> Python:12秒
>快速快速:0.05秒
> Swift -O3:23秒
> Swift -O0:443 s

(如果你担心编译器可能会完全优化无意义的循环,你可以把它改成例如x [i] ^ = x [j],并添加一个输出x [0]的print语句。 ;时间将非常类似。)

是的,这里的Python实现是一个愚蠢的纯Python实现与一列int和嵌套for循环。它应该比未优化的Swift慢得多。一些似乎严重破坏与Swift和数组索引。

编辑4:这些问题(以及一些其他性能问题)似乎已经修复在Xcode 6 beta 5。

对于排序,我现在有以下定时:

> ang -O3:0.06s
> swiftc -Ofast:0.1 s
> swiftc -O:0.1 s
> swiftc:4秒

对于嵌套循环:

> ang -O3:0.06s
> swiftc -Ofast:0.3 s
> swiftc -O:0.4s
> swiftc:540 s

似乎没有理由再使用不安全的-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发行说明中说的:

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.

他们都提倡。无论是聪明还是不,我不能说,但从我可以告诉它似乎足够合理的使用[-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
原文链接:https://www.f2er.com/swift/321931.html

猜你在找的Swift相关文章