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
}

(这里的异或操作只是为了让我能够更容易地找到汇编代码中的相关循环,我试图选择一个易于识别的操作,但也是“无害”的,因为它不需要任何相关的检查到整数溢出。)

再次,-O3和之间的表现有很大的差异-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和数组索引的东西似乎被严重破坏了。


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

为了排序,我现在有以下时间:

  • 铛++ -O3:0.06秒
  • swiftc – 快:0.1秒
  • swiftc -O:0.1秒
  • swiftc:4秒

对于嵌套循环:

  • 铛++ -O3:0.06秒
  • swiftc – 快:0.3秒
  • swiftc -O:0.4 s
  • 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

下面是[-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],则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

TL; DR:是的,只有雨燕语言的实现是缓慢的,现在。如果你需要快速,数字(和其他类型的代码,大概是)代码,只需要与另一个代码。将来,你应该重新评估你的选择。尽管如此,对于大多数应用程序代码来说,它可能已经足够了。

从我在SIL和LLVM IR中看到的情况看来,他们似乎需要一系列优化来删除保留和释放,这可能会在Clang(Objective-C)中实现,但是他们还没有移植它们。这就是我正在使用的理论(现在…我仍然需要确认Clang是否做了些什么),因为在这个问题的最后一个测试案例上运行一个分析器会产生这个“相当”的结果:



正如许多人所说,-Ofast完全不安全,改变了语言的语义。对我来说,就是在“如果你要使用这个,就用另一种语言”的阶段。如果它改变,我会在稍后重新评估这个选择。

-O3得到我们一堆,swift_retain然后swift_release打电话,说实话,看起来他们不应该在这个例子。优化器应该已经消除了(大部分)AFAICT,因为它知道大部分有关数组的信息,并且知道它至少有一个强烈的引用。

当它甚至不调用可能释放对象的函数时,它不应该释放更多的保留。我不认为一个数组构造函数可以返回一个小于要求的数组,这意味着大量的检查是无用的。它也知道整数将永远不会超过10k,所以溢出检查可以被优化(不是因为-Ofast古怪,而是因为语言的语义(没有别的是改变那个var也不能访问它,并且加起来10k是安全的类型Int)。

但编译器可能无法解开数组或数组元素,因为它们正在被传递sort(),这是一个外部函数,必须得到它期望的参数。这将使我们不得不Int间接使用这些值,这会让它变慢一点。如果sort()通用函数(而不是多方法的方式)可用于编译器并被内联,这可能会改变。

这是一个非常新的(公开)的语言,它正在经历什么,我认为有很多的变化,因为其中会涉及与雨燕语言的人(严重)寻求反馈,他们都表示,语言是不是完成,更改。

使用的代码:

import Cocoa

let swift_start = NSDate.timeIntervalSinceReferenceDate();
let n: Int = 10000
let x = Int[](count: n, repeatedValue: 1)
for i in 0..n {
    for j in 0..n {
        let tmp: Int = x[j]
        x[i] = tmp
    }
}
let y: Int[] = sort(x)
let swift_stop = NSDate.timeIntervalSinceReferenceDate();

println("\(swift_stop - swift_start)s")

PS:我不是Objective-C的专家,也不是来自Cocoa,Objective-C或Swift运行时的所有设备。我也可能会假设一些我没有写的东西。

 

添加评论

友情链接:蝴蝶教程