小编典典

Swift Beta 性能:对数组进行排序

all

我在 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.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++ 相比,我可以理解一些性能损失,但与纯 Python 相比,速度不会下降 10 倍。


编辑: weather 注意到更改-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 相比,-O3 损失了近 500 倍:

  • C++ -O3: 0.05 秒
  • C++ -O0:0.4 秒
  • 爪哇: 0.2 秒
  • 使用 PyPy 的 Python:0.5 秒
  • 蟒蛇: 12 秒
  • Swift -Ofast:0.05 秒
  • 斯威夫特 -O3: 23 秒
  • 斯威夫特 -O0:443 秒

(如果您担心编译器可能会完全优化无意义的循环,您可以将其更改为 eg x[i] ^= x[j],并添加一个输出的 print
语句x[0]。这不会改变任何内容;时间将非常相似。)

是的,这里的 Python 实现是一个愚蠢的纯 Python 实现,带有一个整数列表和嵌套的 for 循环。它应该 未优化的 Swift
慢得多。Swift 和数组索引似乎严重破坏了某些东西。


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

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

  • 铿锵++ -O3:0.06 秒
  • swiftc -Ofast:0.1 秒
  • swiftc -O:0.1 秒
  • 快速:4 秒

对于嵌套循环:

  • 铿锵++ -O3:0.06 秒
  • swiftc -Ofast:0.3 秒
  • swiftc -O:0.4 秒
  • 快速:540 秒

似乎没有理由再使用 unsafe -Ofast(aka -Ounchecked); plain-O产生同样好的代码。


阅读 163

收藏
2022-02-28

共1个答案

小编典典

tl;dr Swift 1.0 现在使用默认发布优化级别 [-O] 在此基准测试中与 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] for n=10_000 的时间(以秒为单位) :

Swift:            0.895296452
C:                0.001223848

这是 Swift 的内置 sort() 用于 n=10_000

Swift_builtin:    0.77865783

这是n =10_000的* [-O]*

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
放宽了一些保守的限制,主要是针对浮点运算,这对大多数代码都是安全的。它可以从编译器中获得显着的高性能优势。

他们几乎都提倡它。这是否明智我不能说,但据我所知,如果您不进行高精度浮点运算并且您确信没有整数或程序中可能出现数组溢出。如果您确实需要高性能
溢出检查/精确算术,那么现在选择另一种语言。

测试版 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

[-未经检查]

Swift:   0.000827764
C:       0.001078914
2022-02-28